57
$\begingroup$

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

    • 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?

$\endgroup$
  • $\begingroup$ So Van Helsing can switch the lockets in only one pair of coffins? I didn't understand that bit. $\endgroup$ – Anees Rao Oct 15 '15 at 2:52
  • $\begingroup$ @Anees Rao: Yes, Van Helsing can switch the lockets in at most one pair of coffins. $\endgroup$ – Gamow Oct 15 '15 at 8:31
76
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ But, if Dracula pre-splits the 1000 coffins into closed loops of 100 or so, reminiscent of your 4 coffin loop, then Van Helsings change only affects 2 of the potential closed loops, and Dracula can choose any of the unaffected loops to throw a wrench in the works. Once Harker runs through the closed loop that Dracula starts him in, then he has to guess at a coffin.... $\endgroup$ – APrough Oct 13 '15 at 13:37
  • 3
    $\begingroup$ A loop of coffins as defined by me has to contain the same numbers on lockets as it contains numbers on coffins, otherwise it would not be a loop. Therefore the loop which you start at coffin N must at some point contain locket N. $\endgroup$ – The Dark Truth Oct 13 '15 at 13:40
  • 3
    $\begingroup$ Why does Dracula need to make it a single 1000 coffin loop though? I don't understand that part of this comment string. Why could he not, for example, put lockets 1 - 50 onto coffins 1 - 50 in a random order, and 51-100 into 51-100 in a random order, and so on. $\endgroup$ – rStyskel Oct 13 '15 at 15:17
  • 3
    $\begingroup$ I think the only thing this answer needs is the explanation that when starting from Coffin N in a loop of size K, after exactly K steps you will find Locket N. $\endgroup$ – Tibos Oct 13 '15 at 15:56
  • 10
    $\begingroup$ This answer is right, but the presentation is very unclear and unconvincing unless you already know it's right. $\endgroup$ – R.. Oct 14 '15 at 4:25
16
$\begingroup$

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
$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How would Jonathan know that locket #1 is in coffin #1? . That coffin is as undetermined to Jonathan as the 999 others. [...] Jonathan Harker (who has gained no additional knowledge over the choices of Dracula and Van Helsing in the first three steps) enters the crypt. [...] $\endgroup$ – Matias Cicero Oct 13 '15 at 20:52
  • 3
    $\begingroup$ @MatiCicero They are able to make a plan before hand. "Harker and Van Helsing discuss their options and want to agree on a good strategy" And the coffins and lockets are all labeled. $\endgroup$ – APrough Oct 13 '15 at 21:00
  • 1
    $\begingroup$ @MatiCicero they decide on that strategy before entering the crypt. This means that Van Helsing is deliberately not acting on the information he gains from watching Dracula place the lockets, instead following a set strategy chosen without that knowledge. $\endgroup$ – gatherer818 Oct 13 '15 at 21:00
  • 1
    $\begingroup$ @gatherer818, >! They agree beforehand that Van Helsing will ensure locket #1 is in crypt #1. That is the strategy in this case. If Dracula puts locket #1 in crypt #1, Van Helsing does nothing. If Dracula puts it anywhere else, say, crypt #320, Van Helsing swaps the locket in crypt #1 with locket #1 in crypt #320. This gives Jonathan a $500\over 999$ chance for 999 choices Dracula could make, and a 100% chance for 1 choice he could make, for a ${500\over 999}{999\over 1000}+1{1\over 1000}$$=50.1\%$ chance overall. $\endgroup$ – MichaelS Oct 14 '15 at 5:20
  • $\begingroup$ @MichaelS Since Dracula is able to pick his number with knowledge of Van Helsing's actions, I think it's fair to assume there's a 0% chance he will pick amulet #1 in this case (or will pick the number of one of the amulets Van Helsing swapped, in the general case). $\endgroup$ – Brilliand Oct 14 '15 at 20:38
6
$\begingroup$

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:

Generic cycle

Here are examples of violations of the rules:

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

List item

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

List item

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

enter image description here

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

enter image description here

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

Finally, a crudely drawn example of the locket swap.

enter image description here

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Definitely increases his chances for success! $\endgroup$ – Trenin Oct 14 '15 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.