How to beat Count Dracula

Question

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 1

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).

Answer 2

Source: TheDarkTruth's answer

There are 3 parts to this answer:

The algorithm to find the locket marked with number N(1)

Ignoring the fact that he has to stop after 500 coffins, this is the algorithm Jonathan Harker uses to find the locket which we mark as N(1):

• Jonathan Harker opens coffin N(1), from which he extracts locket N(2)
• Jonathan Harker opens coffin N(2), from which he extracts locket N(3)
• Jonathan Harker opens coffin N(3), from which he extracts locket N(4)
• ...
• Jonathan Harker opens coffin N(k), from which he extracts locket N(k+1)

Up to this point we have opened k-1 coffins with matching lockets, the coffin N(1) and the locket N(k+1). The locket N(k+1) will either match coffin N(1), ending the loop (and the algorithm) or match a new coffin, adding another step in the algorithm. Since the lockets and coffins are never repeated, there can be at most 1000 steps in the loop, but there can be less. The trick is that if Jonathan Harker starts with the coffin N(x), he knows that the locket N(x) is in that loop and will eventually be reached.

Defeating the algorithm

It's easy to see that what locket Count Dracula chooses inside a loop makes no difference. The only thing that matters is how many steps are in the loop. Thus Count Dracula's choice is not which locket to pick, but which loop to pick.

So in order to defeat the algorithm, when Count Dracula picks the locket to be found, has to choose a loop with more than 500 steps. Thus when placing the lockets at the beginning of the game, he must ensure that such a loop exists.

Ensuring success

Van Helsing's part in the story is now clear. He must ensure that when Count Dracula picks the loop, there will be none with more than 500 steps to choose. Since there are 1000 coffins, if more than 500 are in a loop, there are less than 500 coffins left, not enough for another loop larger than 500 steps. This means there is at most one loop with more than 500 steps (from now on called LOOP).

What Van Helsing needs to do to ensure the success is to turn LOOP into two loops with less than 500 steps each.

Supposing LOOP has L steps, Van Helsing needs to choose a random coffin C(1) in the loop and the one farthest from it in both directions, coffin C(L/2). If he switches the two lockets, he turns LOOP with L steps into two loops with L/2 steps.

Putting it all together

• Count Dracula places the lockets so a huge loop is formed
• Van Helsing breaks the huge loop into two smaller loops
• Count Dracula choose any locket in the largest loop
• Jonathan Harker iterates through the loop, eventually finding the locket

Answer 3

Van Helsing and Harker can improve their chances by

moving locket 1 to coffin 1. This leaves 999 coffins in an undetermined state, and then their chances are 500/999, which is 50.05%.

I am sure someone will come up with a better solution with higher survival probability, but this shows you can get at least minimal improvement.

Of course, if Dracula is stupid enough to choose locket #1 as the one Harker needs to find, then they have a 100% chance of survival, since Jonathon will know exactly where that locket is.

Answer 4

I've decided to visualize components of TheDarkTruth's answer, and hopefully clarify some misunderstanding about his solution.

First of all, I found the best way to think of the problem was as a sort of modified linked list/directed graph. Each numbered coffin is a node and each locket is a pointer/directed edge to another node.

The rules I deduced:

1. Each node must point to another node (a node can point to itself), as each coffin has a locket.
2. No two edges can point to the same node (lockets are uniquely numbered).
3. No node can have more than one outgoing edge (only one locket per coffin).
4. Every node has an edge directed to it (lockets are numbered 1 to 1000, as are coffins, so each coffin must have a corresponding locket).

Here's an example of what you might see:

Here are examples of violations of the rules:

1. Coffin with two lockets (you can't exit a cycle from inside).

2. Two lockets with the same number (you can't enter a cycle from outside).

3. A coffin with no locket inside (there are no terminating nodes).

4. A coffin such that no locket exists with the same number (there are no nodes without a pointer to it).

Since these lists can't terminate and can't branch, then they must form cycles.

Finally, a crudely drawn example of the locket swap.

Answer 5

Van Helsing should count the even numbers that are located in a coffin numbered by another even number. he should than pick that number and place it in coffin nr 1. Now when Harker enters the tomb, he will look into the first coffin. When he knows the number of even numbers in even numbered coffins, he can easily calculate the number of even numbers in uneven coffins, uneven numbers in uneven numbered coffins and uneven numbers in even numbered coffins. This way he can increase his chances of finding the correct number by searching in even/uneven numbered coffins depending on N.

Example, Dracula places his the lockets randomly in every coffin. Van Helsing counts the even numbered lockets placed in even numbered coffins and finds that they are 333. He than switched the number in the first coffin with coffin containing 333. Harkels than enters the Tomb and Dracula declares the number to be 777. Harkel opens the first coffin ands finds locket nr 333. From this information he concludes that there are 333 even numbers in even coffins. 167 even numbers in uneven coffins(500 - 333), 333 uneven numbers in uneven coffins( we have 333 uneven coffins left for our uneven numbers), and 167 uneven numbers in even coffins (167 even coffins left for our uneven numbers). Now that Harkel knows that N is 777, an uneven numbers, and there are 333 uneven numbers in uneven coffins, he wil strictly search in eneven numbered coffins, if he has searched 333 uneven coffins and found uneven numbers, and not found N, he than knows that his N is in a even numbered coffin and will from than on only search even numbered coffins. This should enhance his chance of finding N by some margin.