There is a vampire who lives in a castle with four underground vaults arranged in a line. There's a vampire hunter on the prowl so to avoid her, the vampire sleeps in a different vault every day. But he is bound by a magic spell: he can only choose a vault that is directly adjacent to the vault he slept in the previous day. The vampire hunter can open one vault every day. If she finds the vampire, she'll kill him. If not, she'll have to wait another day.
Is there a sequence of vaults the hunter can choose to guarantee she'll eventually find the vampire? Can you find a strategy for the general problem with n vaults?
Solution
Here is one strategy the vampire hunter, let's call her Mina, can use. First label the vaults 1 to 4 from left to right. Suppose Mina starts by visiting the vaults in sequence, vault 1 on the first day, vault 2 on the second, etc. If she hasn't found the vampire by the time she has visited vault 4, then at some point she and the vampire must have swapped vaults (since both only move one vault at a time). This means that when Mina is in an odd-numbered vault, then the vampire is in an even-numbered vault and vice versa. If Mina now waits two days in vault 4, then she will be in a vault of the same parity (even/odd) as the vampire. Then, if she moves backward one vault at a time, she will definitely find the vampire at some point.
This puzzle was suggested to us by Christian Perfect. You can find great interactive versions of the problem (phrased in terms of a prince and a princess) for different numbers of rooms and a solution to the general problem with n rooms on his blog.
Comments
Alternative Solution
Label the vaults 1 to 4 from left to right.
Let {x(1), x(2), x(3), x(4).....} be a strategy i.e. the person (Mina or the Vampire) will be at vault x(i) on day i
Mina's strategy - {3, 3, 2 , 2, 3}
Vampire's Possible Strategies:
No matter where the Vampire starts, he will be caught.
Did I miss anything?
No I don't think so, I got
No I don't think so, I got the same strategy but the other round 2, 2, 3, 3, 2 . So teffectivelyhe same.
I do not think so, I got the
I do not think so, I got the same strategy but just on the opposite side
2 twice meaning he must be in 3 or 4 because if he was in 1 he would have had to move to 2
3 twice this means he must be in 1 if he's not dead yet because to survive he'd have to move to 2 the first time you check 3, and then 1 the second time
so check 2 as that is the only place he can move to.
So effectively the same as yours just mirrored in symmetry of the numbers.
A more efficient solution.
Instead of going 1, 2, 3, 4, 4, 3, 2, 1.
It would be simpler and faster to go 2, 3, 3, 2.