Two prisoners and the prison ward

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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$