There is a vampire who lives in a castle with four underground vaults arranged in a line. A vampire hunter is on the prowl and 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 go to 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 rooms?
This puzzle was suggested to us by Christian Perfect. He was told about it by David Cushing who traced it back to Mathoverflow.
Comments
Maximum 5 days?
Let's note the vaults 1, 2, 3, 4.
Day 1: Visit vault 2
Day 2: Visit vault 2
Day 3: Visit vault 3
Day 4: Visit vault 3
Day 5: Visit vault 2
Having applied the
Having applied the abovementioned strategy, you'll get the vampire on day 3 (at the worst case).
of course, not in three days
not in three days; the worst case is in 5 days
mina 2-2-3-3-2
vampire 4-3-2-1-2
4 days shoud be enough
The worst case is in 4 days
mina 2-3-3-2
vampire 3-2-1-2 or 1-2-1-2
is it right? Or did I forget a case?
3 Days Or 4 days
Let's call the vaults as A,B,C,D
assuming you cannot return back to A from D
Day 1, check vault B, the vampire must be in A,C,D
Day 2, check B again, the vampire must be in D, since if it was in A it must go to B, if it was in C it can only go to B or D.
Day 3, check C, and KILL.
IF you can return from D-A, but not A-D
Day 1, check B, the vampire must be in A,C,D
Day 2, check B again, the vampire must be in D.
Day 3, check C, the vampire must be in A
Day 4, check B, and KILL. :P
Correction ...
Day 2, if it was in D previous day, then now it is in C ;)
2n-2 days
If there are n holes,then
sequence of inspection should be,
Part 1: 2,3,4...,(n-1);
followed by
Part 2: (n-1),(n-2),...2.
if vampire started in an even numbered hole, then it will be found in part 1.
otherwise
if vampire started in odd numbered
hole , then it will be found in part 2.
Proof: The end holes 1 and n are not checked because, before being caught in these end holes, vampire will be found in hole 2 or hole n-1. in both parts we are traversing from one end to other and parity of our movement is different in part 1 and part 2. Hence hermit will be caught in whichever part our parity matches with that of vampire.
Thanks
??
couldn't the hunter just do 1313 or 2424
no, you couldn't just check
no, you couldn't just check 1313 as if the vampire was in 2 when you checked 1, he could then move to 1 when you checked 3 and back to 2 again when you checked 1.
Kill the vampire
2 days tops. 50% chance 1st day 100% 2nd
kill the vampire
put a trap in each vault each day then when the vampire goes to that one KABOOM he's dead
WHY NOT WAIT ??
Why doesn't the just hunter wait in any one of the rooms till the vampier eventually shows up??
Kill the Vampire
Hunter can do 2233, eventually she will get the vampire.