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.

Back to puzzle