strategy - How to beat Count Dracula

Abraham Van Helsing and Jonathan Harker play a game against Count Dracula. The three players agree on the following rules:

1. 
   

   Count Dracula and Van Helsing enter the crypt, while Jonathan Harker has to wait outside. The crypt contains 1000 coffins that are numbered from 1 up to 1000, together with 1000 golden lockets that are engraved with the numbers from 1 to 1000. Each of the numbers from 1 to 1000 occurs on exactly one coffin and on exactly one locket.

   
   


2. 
   

   Count Dracula puts the lockets into the coffins, so that every coffin contains exactly one locket. Van Helsing observes this, and knows exactly which locket is in which coffin.

   
   


3. 
   
   

   Now it is Van Helsing's turn: Van Helsing may (but does not have to) pick a pair of coffins and switch the lockets in these two coffins. Dracula observes the action of Van Helsing.

   
   


4. 
   

   Van Helsing now leaves the crypt through the back door. Jonathan Harker (who has gained no additional knowledge over the choices of Dracula and Van Helsing in the first three steps) enters the crypt.

   
   


5. 
   

   Count Dracula chooses an integer $N$ with $1\le N\le1000$, and announces $N$ to Jonathan.

   
   


6. 
   

   Jonathan is allowed to perform 500 search steps of the following form: Jonathan chooses a coffin, opens it, and checks whether the locket in this coffin carries the number $N$.

   
   
   


7. 
   
   
   
   • If Jonathan Harker finds the locket with number $N$ during his 500 search steps, then he and Van Helsing have won the game. In this case, they are allowed to drive a wooden stake through Dracula's heart.
   
   
   • If Harker does not manage to find the locket with number $N$, then Count Dracula is allowed to drink Van Helsing's and Harker's blood to the last remaining drop.
   
   
   
   

Harker and Van Helsing discuss their options and want to agree on a good strategy. If Harker chooses his 500 coffins simply at random, then the team Harker & Van Helsing has a 50% probability of winning the game. Is there a strategy that would guarantee them an even better probability of success?

Answer

The lockets and coffins are always found in loops.

1. open a coffin


2. look at the number of the locket in the coffin


3. go to the coffin with the same number as the locket


4. open the coffin


5. repeat from 2

At one point you will definitely find the locket of the coffin you first opened

To prove this lets look at the other possibility and try to enter a loop without the first coffin in it.

This is impossible, as any locket which would be needed to enter that second loop would have to be included in the second loop itself and therefore can't be used to enter it.

Now that we know that all coffins are ordered in one or more loops we can easily define a strategy for 100% success:

Van Helsing:

Find (if it exists) a loop that contains more than 500 coffins (there can be at most one such loop since we only have 1000 coffins) and switch two lockets in that loop so that two new loops with each 500 or less coffins are created.

Jonathan Harker:

Start with the coffin with the number N as stated by Dracula and follow the loop until you find the locket with the number N. As no loop will have more than 500 coffins it doesn't matter which number dracula chooses.

To understand splitting of loops:

Imagine 4 coffins 1,2,3,4 with the lockets 2,3,4,1 (in that order).

We now have a loop of size 4.

If we now switch the lockets of coffin 2 and 4 we get coffins 1,2,3,4 with lockets 2,1,4,3 (in that order).

So now we have two loops of size 2 (namely 1,2 and 3,4).