Evil Wizard Kidnaps your Dog
Inquire Problems
We have recently started posting some fun problems on Instagram. Here is one of them. We will post solutions or some directions you can take here on our Substack. Our first problem is given below:
Here is a text version:
An evil wizard has kidnapped your dog. You are on a mission to rescue him.
The Wizard's house has four doors (A, B, C and D) and your cute dog is imprisoned behind one of them. The wizard decides to play a game with you. You have to rescue the dog within 4 days or he will skin the dog alive and feed it to his pet tiger. He allows you to check one door per day and he moves the dog every day.To add a twist, the wizard can read your mind and tell what you are going to do in the future. So, he will always try to make sure that the dog is not behind the door you are going to go to.However, to give you a fighting chance, he will only move to an adjacent door the next day. If he was behind Door B on day 1, he could either be behind Door A or Door C on day 2. If he was behind Door A on day 3, he would have to be behind Door B on day 4 since Door B is the only door adjacent to Door A.
Can you find a way that no matter what the wizard does, even if he knows what you are thinking, you will be able to rescue the dog within 4 days, each day checking exactly one door with the rules given earlier?
Extracting learnings by solving simpler problems
Something a mathematician would do here would be to try and simplify the problem, and try to solve the simpler problem - hopefully that will throw light on the harder problem.
Suppose there was only one room. Well, that is a trivial case. If there is only one room, you will rescue the dog on the first day.
So, let us take the case of two rooms, A and B. Suppose we keep switching rooms on alternate days, A → B → A → B …. In that case, the wizard will move the dog B → A → B → A …, and you will fail to rescue the dog. Suppose we repeat any of the doors twice, say A → A. In that case, if the dog was in room B on the first day, he would be in room A on the second, and you will rescue him.
So, what have we learned from this case - one possible learning is that repetition is helpful.
Let us now take the case of three rooms, A, B, and C, and use this principle. Suppose we keep repeating door A. That doesn’t work since the wizard can keep switching the dog between rooms B and C. Similar problems arise with room C.
How about room B? If we repeat room B just twice, we rescue the dog. Why is that? Suppose the dog started in room A. Then, the next day, he would be caught in room B. Suppost the dog started in room C. Once again, he would be caught the next day in room B.
What have we learned from this case - maybe that the middle door is especially useful.
Transferring learnings from the simple problems
Let us apply these two learnings to the case with four doors, A, B, C, and D. This time, there is no middle door. So, let us start by picking one of the two middle doors, for example door B. If we repeat door B again and again, that doesn’t work. The wizard will just move between doors C and D.
Maybe, we need to use both the central doors. Let us start with door B. Now, we can either repeat door B or try door C (since we are sticking to the principle that we stay on the central doors). Let us try repeating door B. If the dog started in doors A or B, you have rescued it. So, we have restricted it to doors C and D, giving us some information.
Repeating door B for the third time makes no sense. Why? Since it doesn’t give us any additional information. The dog can keep shuttling between C and D, and you don’t know where it is. So, let us try door C on the third day. Now, we can rule out that he was behind door D on the second day. So, he must have been behind door C.
The next day, he could be behind door D or door B. We have a choice now. Either we repeat door C or move to door B. Let us try repeating door C. The reason for that is that it allows us to eliminate two things:
The dog moving to door D on day 3, meaning that it must move to door B
The dog moving to door C from door B on day 4, meaning it must move to door A
So, this restricts the dog to exactly door A on day 4. That means we know where it will be on day 5 - door B. So, we can rescue the dog from door B on day 5.
Now, the question did ask us to do this in four days. We have done it in five - BBCCB. Can we do it in four?
Optimizing the number of days
There were two times we made choices in the procedure above:
On the second day, when we chose to repeat door B
On the fourth day, when we decided to repeat door C
Let us take the second choice first. Suppose we had switched to door B rather than repeating door C. Would we have rescued the dog on the fourth day? Clearly not - the wizard would have just taken the dog to door C on day 4.
How about the first choice? Suppose that rather than repeating door B, we went directly to door C. So, rather than BBCCB, we did BCCB. Does that work?
It does - I will leave it to you to convince yourself. So, this is a solution to the problem in four days.
Can we do better?
Can we do three days? No, but why? I will leave this to you as an exercise. Think about all possible choices of middle doors and write them out. You will see that three days is impossible.
Generalizing the problem
Now, suppose we had five doors, or six, or 7,000,045. Can you figure out a procedure to always rescue the dog? How long would it take?
Base it on the learnings so far:
Do not focus on the extreme doors (I am rewriting the learning that we should focus on the middle doors).
Repetition is important, but you do not need to repeat every door.
Figuring out a way to restrict the dog to an extreme door is how we can find a solution since the wizard only has one choice from that point (as opposed to any other door, where the wizard has two choices.
Post your solutions to the general problem in the comments below.