# 10 prisoners and 10 lists of numbers [duplicate]

10 prisoners are held captive by a cruel warden. One day he gathers them in the prison hall and tells them about a new game he wants to play:

"Tomorrow, I will assign each one of you a random single digit number known only to me, for you knuckleheads: that's zero to nine! Each one of you will get a number independently of others - for all I care everyone of you is a zero. I will then put you in isolated cells, and through the food slot give each of you a list. This list will contain all of the other prisoners numbers in a random order. One by one, I will then remove every prisoner from his dirty cell and ask him what number he thinks he was assigned. I will then put him back in isolation. Don't think for a second you'll hear his guess, the isolation cells are sound proof. If at least one of you miserable lowlifes guesses his own number correctly, you are all free to leave. But if not, you will be denied of food until you die horribly. Don't think for a second I will tolerate any form of communication between yourselves after put in isolation. I will personally execute anyone who dares break this rule. You may discuss your strategy until tomorrow. Goodbye for now"

He then shuts the door of the hall close and leaves them be.

One of the prisoners then shouts out loud:

"I have a strategy that will get us all out for sure!"

Assuming his statement was true, can you explain what might this strategy be?

• "for all I care everyone of you is a zero." there's your answer :) – Nobody Mar 1 '18 at 9:50
• When prisonners are taken out of their cells to make their guess, do they know if they are the first, second, or tenth to do so ? – Evargalo Mar 1 '18 at 10:29
• No, because the only thing that happens is they guess their number and get returned immediately back into their cell. No extra information is given to them. – yotabyte Mar 1 '18 at 10:32
• The stupid mathematician reasonning: if we just answer at random, each of us has 0.1 proba of guessing right. So our chances to survive this is 1-0.9^1=0.65.. Since our numbers are totally independantly chosen, the list I recieve cannot help me making a right guess. Since our numbers are totally independantly chosen, no collective strategy can help us ( because P(A is right | B is wrong)=P(A is right) - maybe that's where my mistake lies, or at least where the problem seems paradoxal). So, almost 2 chances out of 3 is not so bad, let's enjoy dinner in case it's our last ever, and good night! – Evargalo Mar 1 '18 at 10:38
• @Danikov exactly! – yotabyte Mar 1 '18 at 11:49

The strategy is:

The $i$-th prisoner ($i$ numbered from $0$ to $9$) sums the numbers on the list, and picks a number $X$ as his guess such that $(sum + X)\equiv i\pmod{10}$.

This $i$ is predetermined, each prisoners must agree who has $i = 0$, $i = 1$, and so on.

Why it works:

We are actually trying to find the sum of all actual numbers modulo $10$.
There are $10$ possibilities: from $0$ to $9$, and the $i$-th prisoner tries the $i$.

Note that the possible value of $X$ is only one for each prisoner.

For example:

Ordered from $0$-th to $9$-th, prisoners are assigned on these rooms: $1, 4, 6, 6, 1, 7, 3, 8, 2, 6$.
Sum of these rooms is $44$.

The $0$-th prisoner got $4, 6, 6, 1, 7, 3, 8, 2, 6$ whose sum is $43$.
He will pick $X = 7$ as $43 + 7 \equiv 0\pmod{10}$.

The $1$-th prisoner got $1, 6, 6, 1, 7, 3, 8, 2, 6$ whose sum is $40$.
He will pick $X = 1$ as $40 + 1 \equiv 1\pmod{10}$.

The $2$-th prisoner got $1, 4, 6, 1, 7, 3, 8, 2, 6$ whose sum is $38$.
He will pick $X = 4$ as $38 + 4 \equiv 2\pmod{10}$.

The $3$-th prisoner got $1, 4, 6, 1, 7, 3, 8, 2, 6$ whose sum is $38$.
He will pick $X = 5$ as $38 + 5 \equiv 3\pmod{10}$.

The $4$-th prisoner got $1, 4, 6, 6, 7, 3, 8, 2, 6$ whose sum is $43$.
He will pick $X = 1$ as $43 + 1 \equiv 4\pmod{10}$.

The $5$-th prisoner got $1, 4, 6, 6, 1, 3, 8, 2, 6$ whose sum is $37$.
He will pick $X = 8$ as $37 + 8 \equiv 5\pmod{10}$.

...

At the end, the prisoner who answer correctly is only the $i$-th prisoner where $i$ is the sum of actual numbers modulo $10$, which is $44\equiv4\pmod {10}$.
As you can see, the $4$-th prisoner got his number right (room $1$).

• You should add that i is predetermined before and has nothing to do with order of passage – Untitpoi Mar 1 '18 at 10:41
• I'm not sure I understand how or why this works, or am I just being an idiot? – F1Krazy Mar 1 '18 at 10:47
• @F1Krazy, Try applying this solution for a smaller base...for example 3 prisoners with 3 numbers, maybe it'll give you more intuition. – yotabyte Mar 1 '18 at 10:49
• That's amazing! I wrote a prolog program to modelize your solution. Just change the numbers assigned to any prisoner you like and run prisonerRight(P). to know who gets his number right with this solution! – Rafalon Mar 1 '18 at 11:31
• Given 3 prisoners assigned [1,2,1] (in their i'th order), the first prisoner will guess (2+1+0) mod 3 = 0, the second prisoner will guess (1+1+1) mod 3 = 0, and the third will guess (1+2+2) mod 3 = 2. All prisoners will be wrong. – Danikov Mar 1 '18 at 11:35

If everyone says the lowest number on the list, they will all say the same number, and at least one of them will be right. Alternatively, they could all say the highest number.

• This won't work if they all have a different number - They'll never get their own number (note the question mentions that they get a list which will contain all of the other prisoners numbers) – Lolgast Mar 1 '18 at 9:41
• The list does not contain the prisoner's own number. – Bass Mar 1 '18 at 9:42
• Imagine for example the numbering of the prisoners is cyclic: 0,1,2,3,4,5,6,7,8,9. not even one prisoner will guess correctly according to your solution! so it is not guaranteed to free them. – yotabyte Mar 1 '18 at 9:42
• Ah yes, thanks all! I forgot about that part. – Tom Mar 1 '18 at 9:47