Two prisoners and the prison ward
Two prisoners are imprisoned at opposite ends of the prison. They cannot meet, nor exchange any kind of information. However, one day they are brought together by the ward who tells them:
"I shall give you a chance for getting free. In one hour you'll be separated again, and one of you will go back to his cell, while the other one will stay here. I shall show the former six different numbers randomly chosen among the positive integers $ 1, ...., 245 $. He may think about the numbers and then will have to reject one of the six numbers and tell me the other five. I shall write these five numbers down on a piece of paper, in one line and in the same order as I hear them. Then this guy will have to leave the room. The other man will be called in. I show him my piece of paper with the five numbers, and he must say a number. If he says the rejected number, then the two of you will be free. "
How can these two guys get free?
mathematics strategy game
D.A.G.D.A.G.
$\begingroup$ 'in one line' - does this mean that the second person won't know if 345 is 34, 5 or 3, 45 or 3, 4, 5.... Or that he will know what the different numbers are? $\endgroup$ – Ben Feb 24 '16 at 10:57
$\begingroup$ Sounds like the Fitch Cheney card trick $\endgroup$ – Julian Rosen Feb 24 '16 at 14:19
(1) We observe that $245=5\times49$. Instead of working with the integers $1,\ldots,245$, we will use the integers $1,\ldots,49$ in the five colors red, blue, yellow, green and orange.
(2) Among the six numbers randomly chosen by the ward, there will be at least two of the same color, say integers $x$ and $y$ both in color red. Modulo $49$, exactly one of $x-y$ and $y-x$ is in the range $1,\ldots,24$; assume that $y-x$ is in the range $1,\ldots,24$. Then we reject $y$, and put $x$ as the first number on the list. With this, the second prisoner knows that the rejected number has the same color as the first number $x$ on the list and is one of $x+1,x+2,\ldots,x+24$ (taken modulo $49$).
(3) There are $4!=24$ permutations of the other four integers. This is enough to communicate the value of $y-x$ to the other prisoner. (The two prisoners just have to agree on a bijection between permutations of four objects and the numbers $1,2,\ldots,24$.)
Hugh Meyers
22.2k4242 silver badges162162 bronze badges
GamowGamow
$\begingroup$ This is brilliant, but I think it needs to be expanded to include the code for part 3, because they only have one hour to agree it and they also need to be able to encode and decode it relatively easily. $\endgroup$ – jhabbott Feb 25 '16 at 15:51
$\begingroup$ @jhabbott Label four objects ABCD. Put their 24 permutations in alphabetical order. The first permutation (ABCD) is 1, the second permutation (ABDC) is 2, and so on. $\endgroup$ – f'' Feb 25 '16 at 16:58
$\begingroup$ @jhabbott - see my post where I explain how to encode 1-120 from permulations of 5 integers. For 4 integers, just drop $a_5$ and $d_4$, and you can encode 1-24. $\endgroup$ – Paul Sinclair Feb 25 '16 at 17:18
This doesn't work. I will leave it in case someone can use it to create a real solution. The problem is this:
Consider the sequence 121, 122, 123, 124, 125. Whatever scheme I came up with, it was possible to add a number to that sequence that would defeat the strategy. Try adding 120, 126, 1 or 245 as the sixth number and by my reckoning one of those should be unreachable by strategies like the one below. The idea of using permutations to indicate a number between 1 and 120 is valid and Paul Sinclair has given an elegant explanation in his post.
The prisoner who is to leave announces that his strategy will be
To reject either the largest or the smallest number given. Of the remaining five numbers, if there are fewer numbers larger than the largest remaining numbers, then the largest was rejected. Likewise for smaller. In case of a tie, the rejected number is smaller. Thus no more than (245 - 5) / 2 = 120 numbers remain.
The prisoners then agree on the following numbering system:
The base ordering of the five numbers is largest to smallest. This represents the number 1. If the final two numbers are permuted, this represents the number 2. If the third and fifth numbers are permuted, this represents 3 and so on. The number of permutations is 5!, exactly enough to solve the worst case.
Hugh MeyersHugh Meyers
$\begingroup$ I'm afraid I don't understand the second half of your explanation -- how does the permutation represent a number? $\endgroup$ – Fund Monica's Lawsuit Feb 24 '16 at 13:40
$\begingroup$ @QPaysTaxes - I added an answer (too long for a comment) explaining a scheme for representing the number as a permutation. I am not sure if it the scheme that Hugh Meyers intended, but it does the job. $\endgroup$ – Paul Sinclair Feb 24 '16 at 14:25
$\begingroup$ As far as I understand it this doesn't work. If I understand you right the second person should compare the range of numbers that are larger than the largest remaining one and the range of thos that are smaller than the smallest remaining one and depending on which is smaller should focus the second step on this range. However given for example the initial numbers [3, 119, 120, 121, 242, 244] the first person can't make such a situation happen. If he removes the 244 the second person will focus on the range [1, 2] and if he removes the 3 the second person will focus on the range [245]. $\endgroup$ – The Dark Truth Feb 24 '16 at 14:39
$\begingroup$ @TheDarkTruth - Don't reject the largest or smallest, unless they have equal ranges - then reject one of them to make the ranges unequal. If they are already unequal, reject some middle number. The 2nd person uses the smaller range. Everything else proceeds as Hugh Meyers said. $\endgroup$ – Paul Sinclair Feb 24 '16 at 14:46
$\begingroup$ @PaulSinclair I don't think your proposal works - if the second person sees 10 as their smallest number and 225 as their largest, how do they know if 225 was the largest number given to the first person (and thus they rejected some middle number), or if the first person rejected 235? $\endgroup$ – Dan Staley Feb 24 '16 at 19:24
Arrange the numbers from 1 to 245 clockwise around a circle, and mark the locations of the six numbers on it. Consider the gaps left between the marked numbers. There are six gaps, with a total length of 245. Each gap is at least 1, so the largest possible sum of two gaps is 241, and the second-largest gap is at most 120.
Find the largest gap (or possibly one that is tied for largest). The number that will be removed is the one on the clockwise edge of this gap. The next gap clockwise (before the number is removed) is at most 120, so its length can be encoded by the order of the five numbers to be written.
The other prisoner receives the five numbers and similarly plots them on a circle. They will necessarily find that one of the five gaps is larger than any of the others. The removed number comes from this gap, and its value can be found by converting the order of the five numbers back into a value from 1 to 120, and counting that many places counterclockwise from the clockwise edge of the gap.
f''f''
$\begingroup$ Really nice solution if you can write on paper and you don't have to remember much details $\endgroup$ – Falco Mar 1 '16 at 12:37
Not an answer, but too long to add as a comment to Hugh Meyer's answer. I don't completely follow his scheme for converting a permutation to a number either, but here is one that works:
Let $a_1, a_2, a_3, a_4, a_5$ be the five numbers in the order given. Then for $k = 1, 2, 3, 4$ define $d_k$ to be the count of numbers $a_1, ..., a_k$ which are less than $a_{k+1}$. So for example, $$\begin{align}d_1 &= \begin{cases} 0 & \text{if }a_2 < a_1\\1&\text{if }a_2 > a_1\end{cases}\\d_2 &= \begin{cases} 0 & \text{if }a_3 < a_1, a_2\\1&\text{if }a_1 < a_3 < a_2\text{ or }a_2 < a_3 < a_1\\2& \text{if }a_1, a_2 < a_3\end{cases}\end{align}$$
Similarly, $d_3$ is between $0$ and $3$, and $d_4$ is between $0$ and $4$.
Then the number wanted is $1 + d_1 + 2\times d_2 + 6\times d_3 + 24 \times d_4$
Paul SinclairPaul Sinclair
Not the answer you're looking for? Browse other questions tagged mathematics strategy game or ask your own question.
Variation of 100 prisoners light problem
10 Prisoners, 10 Keys, and 7 Years
A generalization of Tyler Seacrest's "Three voting prisoners" puzzle
The Unknown Prison of Unknown Size
23 Clones and Two Lightbulbs
Three mathematicians are forever in Prison
The Greedy Box (Or: Another crazy guard offering his prisoners freedom)
100 prisoners' names in boxes, against smart warden