How to beat Count Dracula, part 3

This is a follow-up to "How to beat Count Dracula" and to "How to beat Count Dracula, part 2".

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 five coffins that are respectively numbered $1,\ldots,5$, together with five golden lockets that are respectively engraved with the numbers $1,\ldots,5$.

2. Count Dracula puts the lockets into the coffins, so that every coffin contains exactly one locket. Every possible assignment of the five lockets is used with equal probability. (That's important: the count does not pick the assignment.) 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.

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 uses a random generator to pick an integer $N$ with $1\le N\le5$, and announces $N$ to Jonathan. Every possible value for $N$ is picked with probability $1/5$.

6. Jonathan is allowed to choose one coffin and to open it.

• If Jonathan Harker finds the locket with number $N$ in the opened coffin, 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 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 coffins simply at random, then the team Harker & Van Helsing has a $1/5$ probability of winning the game. What is the best probability of success that Harker & Van Helsing can reach?

• At the moment (considering the proposed solutions) seems that it is not required for Dracula to make a "fair choice". I am not completely sure if this remains true even when Dracula has seen what Van Helsing has done, but if the strategy between Helsing and Harker is unknown to Dracula, they can choose a random permutation which would harden their strategy against an unfair DRNG (Dracula Random Number Generator). – MariusSiuram May 30 '16 at 13:50

Here's a possibly suboptimal strategy which achieves a probability of 71/150 ≈ 47%.

van Helsing's strategy:

• If all lockets match the coffin they are in, do nothing.

• If there exist two coffins which contain each other's lockets, switch them (if there are two such pairs, choose one at random).

• Otherwise, pick a locket which doesn't match its coffin (at random, if there are several choices), and switch that locket to its matching coffin.

Harker's strategy is to look in coffin number $N$, the number Dracula chose.

The following table outlines the calculation of the success probability. Every locket distribution breaks into "cycles." For example, if locket 1 was in coffin 4, and 4 was in 5, and 5 was in 1, this would be a cycle of length 3. The "cycle type" of a distribution is a list of the lengths of its cycles.

Van Helsing's switch replaces a 2-cycle with two 1-cycles, if there are any 2-cycles. Otherwise, it replaces a k-cycle with a 1-cycle and a (k-1)-cycle. Harker finds the correct locket if and only if he picks a locket in a 1-cycle. $$\begin{array}{r|ccc} \text{Cycle type}& 1,1,1,1,1 & 2,1,1,1 & 2,2,1 & 3,2 & 3,1,1 & 4,1 & 5\\ \text{P(occuring)} &\frac1{120} & \frac{10}{120} & \frac{15}{120} & \frac{20}{120} & \frac{20}{120} & \frac{30}{120} & \frac{24}{120}\\ \text{After switch} & 1,1,1,1,1 & 1,1,1,1,1 & 2,1,1,1& 3,1,1 & 2,1,1,1 & 3,1,1 & 4,1\\ \text{ P(winning)} & 1 & 1 &\frac35 & \frac25 & \frac35 & \frac25 & \frac15\\ \end{array}$$ Multiplying the two probabilities in each column, then adding these up, gives the advertised answer.

One can do slightly better than the strategy proposed by Mike Earnest and obtain a $\frac{143}{300}\approx 48\%$ chance of success, which is $\frac{1}{300}$ more likely to succeed than the linked strategy. The strategy is as follows:

Let $f(N)=\max(1,N-1)$. Van Helsing should look to see if that are any two coffins $c_1$ and $c_2$ such that lockets $N_1$ and $N_2$ inside each respectively have $f(N_1)=c_2$ and $f(N_2)=c_1$. If so, he should switch $N_1$ and $N_2$. Otherwise, if there is any coffin $c$ with a locket $N$ inside such that $f(N)\neq c$, but such that there is some locket $N'$ with $f(N')=c$, he should switch $N'$ and $N$. He should do nothing if neither of those conditions are met.

After hearing the number $N$ which Dracula announces, Jonathan will open the coffin labelled $f(N)$.

Examples: If Van Helsing looked through the coffins numbered $1$ to $5$ and found lockets $1,\,3,\,5,\,4,\,2$ in that order, he would switch lockets $5$ and $4$ to get $1,\,3,\,4,\,5,\,2$, since now locket $4$ is in coffin $f(4)=3$ and locket $5$ is is coffin $f(5)=4$. In fact, every locket except $2$ is in the appropriate coffin, so Jonathan will find the proper locket with probability $4/5$. If the lockets were $1,\,2,\,3,\,4,\,5$, then Van Helsing would switch lockets $2$ and $3$ (or various other possibilities), since it is not possible to switch a pair of lockets into their rightful place, but it is possible to switch locket $3$ into the coffin $2=f(3)$. This leaves the arrangement $1,\,3,\,2,\,4,\,5$, where only two lockets are in the appropriate place, so Jonathan succeeds with probability $2/5$ - exactly when $1$ or $3$ is called. The last possibility is that Van Helsing does nothing, which would happen in an arrangement like $2,\,3,\,4,\,5,\,1$, where each coffin contains an appropriate locket. Note that locket $1$ is still out of place, but switching it with locket $2$ would move locket $2$ out of place, so makes no improvement. Jonathan again succeeds with probability $4/5$ here.

This succeeds with probability $\frac{143}{300}$. We will show this and that it is optimal below the horizontal line.

In particular, let us work through this game backwards. We can see that Jonathan only knows one number $N$, so his strategy is characterized by the function $f(N)$ which tells him which coffin to open given $N$.

Van Helsing's goal is therefore to maximize the number of $N$ such that the locket numbered as $N$ is in fact in the coffin labelled $f(N)$. His optimal strategy can easily be seen to be to act as follows, where he looks at only the first case below whose conditions are satisfied:

• If there exist two lockets $N_1$ and $N_2$ such that $N_1$ is in coffin $f(N_2)$ and $N_2$ is in coffin $f(N_1)$, he should switch lockets $N_1$ and $N_2$, improving the probability of success by $2/5$.

• Otherwise, if there exists a coffin $c$ containing a locket $N$ such that $f(N)\neq c$, but there is some $N'$ with $f(N')=c$, he should switch lockets $N$ and $N'$, improving the probability of success by $1/5$.

• Otherwise, every coffin $c$ in the image of $f$ contains a locket $N$ with $f(N)=c$. In this case, the probability cannot be improved, so Van Helsing should do nothing.

Let us say that the first case happens with probability $P_1$, the second with probability $P_2$ and the third with probability $P_3$. Note the the probability of success if Van Helsing did nothing is $\frac{1}5$ since then the locket in the chosen coffin would be distributed uniformly randomly. Adding this baseline to the expected improvement in the probability due to Van Helsing gives the probability of success as $$\frac{1}5 + \frac{1}5P_2 + \frac{2}5P_1.$$ Note that, as $P_2$ is not natural to calculate, we may use the relation $P_1+P_2+P_3=1$ and various simplifications to rewrite the probability of success as $$\frac{2-P_3+P_1}{5}$$

To calculate $P_1$, let us define the function $S(c)=|f^{-1}[\{c\}]|$. That is, $S(c)$ is the number of lockets $N$ which Jonathan will search coffin $c$ for. This is the only aspect of $f$ that matters.

Let us first calculate the probability of a given pair of coffins $c_1$ and $c_2$ containing lockets $N_1$ and $N_2$ such that swapping the lockets puts both in their proper place. That is, we want to know the probability that $f(N_1)=c_2$ and $f(N_2)=c_1$. This probability may be seen to be $S(c_1)S(c_2)/20$.

As we are interested in the probability of this being the case for any coffins, it is useful to consider the probability that both the pairs of coffins $(c_1,c_2)$ and $(c_3,c_4)$ could be switched to the same advantage. This probability will be $S(c_1)S(c_2)S(c_3)S(c_4)/120$, since we are determining that four locations must contain elements of disjoint groups. Usefully, since a set of four coffins $\{c_1,c_2,c_3,c_4\}$ may be partitioned into two groups of two in $3$ ways, the sum of the probabilities of there being two good switches among these four coffins is $S(c_1)S(c_2)S(c_3)S(c_4)/40$.

Obviously, having only $5$ coffins, one cannot have three possible pairs of good switches, as pairs of switches may not overlap. Thus, using the inclusion-exclusion principle, we calculate $P_1$ as follows $$P_1=\frac{\sum\limits_{\{c_1,c_2\}}S(c_1)S(c_2)}{20}-\frac{\sum\limits_{\{c_1,c_2,c_3,c_4\}}S(c_1)S(c_2)S(c_3)S(c_4)}{40}$$ where the sums run over the subsets of the coffins in the image of $f$ of the desired size.

We may calculate $P_3$ in a similar manner. In particular, if one enumerates the coffins $c_i$ in the image of $f$ as $c_1,c_2,\ldots,c_n$, then the probability of each coffin $c_i$ containing an $N_i$ with $f(N_i)=c_i$ will be $\frac{S(c_1)S(c_2)\ldots S(c_n)}{5\cdot 4 \cdot \ldots \cdot (5-n+1) }$.

If $f$ is a bijection, then $S(c)=1$ for every $c$, so we calculate that $P_1=\frac{{5\choose 2}}{20}-\frac{{5\choose 4}}{40}=\frac{15}{40}$ and $P_3=\frac{1}{5!}$ so that the overall probability of success is $\frac{71}{150}$. This choice corresponds exactly to Mike Earnest's strategy, where essentially $f(n)=n$ was used.

However, we get a better value if we have $f$ have an image of size $4$ - then, Jonathan will only ever look in four coffins, where $S$ takes the values of $1,\,1,\,1,\,2$. We then get $P_3=\frac{2}{5!}$ and $P_1=\frac{9}{20}-\frac{2}{40}=\frac{2}5$ yielding a rate of success of $\frac{143}{300}$.

Lacking a clever argument to rule out $f$ with smaller images, note that when $f$ has an image of $3$ coffins and $S$ takes the values of $1,\,1,\,3$ or $1,\,2,\,2$, then $P_1$ is the same as in the case of $f$ having an image of $4$, but $P_3$ is larger, decreasing the rate of success. If the image of $S$ is no more than two coffins, it's easy to see that $P_1$ will be at most $\frac{3}{10}$, which necessarily gives a lower probability of success than the other strategies. Thus, we settle on $f$ having an image of size $4$ to get the best success rate.

• van Helsing doesn't know the value of $N$ – JMP May 30 '16 at 5:01
• @JonMarkPerry Is there anywhere in my answer that I say he does? Maybe it's confusing that I've just used $N$ to refer to the number on the lockets in general, not the particular locket announced. – Milo Brandt May 30 '16 at 5:05
• he's supposed to know how $f$ is defined, which requires knowledge of $N$. – JMP May 30 '16 at 5:06
• @JonMarkPerry $f$ is a function independent of the number announced; Van Helsing can certainly know things like "Jonathan will always choose the coffin numbered the same as the locket he is supposed to find" or "Jonathan will always look in the coffin numbered $\max(1,N-1)$ if he's looking for the $N^{th}$ locket". That is, the information $f$ carries is what Jonathan would do in various situations, but it doesn't tell us what Jonathan will do, since everything is contingent on "If $N$ is a announced, Jonathan will look in the coffin $f(N)$" – Milo Brandt May 30 '16 at 5:12
• Could you give an actual example of your strategy? I feel like I am understanding the general idea, but I lack to see exactly what you mean with the f(N) – MariusSiuram May 30 '16 at 8:50