5
$\begingroup$

The riddle goes like this:

$\qquad$ There are $100$ prisoners standing in line, each with a number on their back. The numbers are all different, and range from $1$ to $101$ (i.e. one number is missing). The person in the back of the line can see all 99 prisoners ahead of him's numbers. The prisoner in the front of the line sees no numbers. Starting with the prisoner in the back, each prisoner must shout the number on their own back, but each number can be said aloud only once.

$\qquad$The first prisoner clearly only has a $50$% chance of guessing his number correctly. However, once he has guessed his number correctly, the remaining 99 prisoners have a $100$% chance of correctly guessing the number on their backs.

What is their strategy to achieve this?

Update:

I have been given a hint that the solution "does not just involve modulo sums." There is more to the solution than just a modular trick.

$\endgroup$
  • $\begingroup$ To be clear, I don't know the solution. I was given the riddle and am seeing if anyone else knows it. $\endgroup$ – BrianW Apr 26 '16 at 1:58
  • 1
    $\begingroup$ So each prisoner can shout multiple numbers? What do you mean by "once he has guessed his number correctly"? Or should it be "If he guess his number correctly"? $\endgroup$ – Ove Ahlman Apr 26 '16 at 6:00
  • $\begingroup$ So you are saying if the first one guesses his numbers correctly, other ones will be able to guess their and be 100% sure about it? So you are assuming they heard his correct guess, and now person $99$ knows all numbers in front of him, including the number that the person $100$ behind him guessed correctly? This leaves two numbers unknown for person $99$, his own and the missing one. Doesn't this leave him in the same situation as the person $100$? And what do you mean "once he guessed his number..." How many guesses then they have? I think you need to be more clear about certain things here. $\endgroup$ – Vepir Apr 26 '16 at 7:59
  • $\begingroup$ @Matta, not necessarily -- the first prisoner can base which of her 2 options she picks based on which numbers she sees in front of her. This way, she can communicate information to the other prisoners. (In fact, with 2 players and 3 numbers, the game is quite easy: the first prisoner shouts the number she sees in front of her, minus 1 modulo 3, and the prisoner in front of her can invert that.) $\endgroup$ – Mees de Vries Apr 26 '16 at 8:01
  • $\begingroup$ @Ove yes, he only gets one guess to shout his number so it should be corrected to if. $\endgroup$ – BrianW Apr 26 '16 at 12:29
2
$\begingroup$

The back prisoner imagines another behind with the missing number. He then guesses the number that will make the list an even permutation of the numbers $1$ to $101$. The person in front of him (assuming the first guess is correct) knows all the numbers but two and can select the one that makes the permutation even. Each prisoner in turn has just two choices (assuming the previous shouts are correct) and one of those will make the permutation even.

Second solution: back person shouts the number on the front person. As he has failed to state his number correctly, there is no requirement that the others are correct.

$\endgroup$
1
$\begingroup$

I can think of a strategy that works if the whole bunch of people are allowed to make at most one error (a reasonable assumption, I think, given that no matter what strategy he uses, the last guy gets the answer correct with probability at most 0.5): have the last guy shout out the sum modulo 101 of the two missing numbers. Then every person in front of him will have to choose between 3 missing numbers (having eliminated the ones that have already been shouted out), and they just need to see which two of the three numbers, when summed, give the one that the last person shouted out. This leaves them with only one possibility, which they shout out. Note: this only works because for any 3 distinct numbers (a,b,c), the sum of any two distinct pairs of them cannot be the same (even if the sum is modulo some integer).

$\endgroup$
  • $\begingroup$ The odds of the sum modulo 101 of the two missing numbers being one of the two numbers not that the last person doesn't see is very unlikely, though. A prisoner isn't allowed to say a number that he can see in front of him. $\endgroup$ – BrianW Apr 29 '16 at 3:14
  • $\begingroup$ @BrianW: : "A prisoner isn't allowed to say a number that he can see in front of him. " was not part of the problem. I was trying a solution where the back person would say a number known to be wrong in some cases. He would always shout $1$, even if somebody else had that number. It failed, but I didn't think it outside the rule. $\endgroup$ – Ross Millikan Apr 29 '16 at 4:04
  • $\begingroup$ My apologies for not including that in the original post. I have edited it so that it now includes that information. $\endgroup$ – BrianW Apr 29 '16 at 14:03

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.