A group of 100 criminal mathematicians (corrupt accountants, sleazy statisticians, etc) arrive together in a special prison. They aren't told how long they'll be there, but they're told how to get out.

On the day of their arrival, each prisoner has a colored spot tattooed in the middle of his back. The tattoo is either black or red. He isn't told which color he has, but he is told that all 100 prisoners have such a spot and both colors are represented; that is, all prisoners having black or all prisoner having red is not an option.

He's then put in an isolated room, where he will spend the rest of his prison term in solitary confinement. The room is filled with physical exercise machines, along with the usual amenities.

One wall of the room contains 99 recessed video monitors and the opposite wall a small video camera. On the morning of the last day of each year served, these will become active. Each prisoner will strip to the waist in front of the camera and face the video screens, where he will find displayed the bare backs of the other 99 prisoners. He's given 1 minute to note the colors of the spots on the backs displayed. The cameras then become inactive and the screens go dark for another year.

His task then, which he well qualified to perform, is to determine the color of his own spot using logic only. Once he knows for a fact what his color is and can prove it logically, he informs the warden and is released from prison that very day.

At the end of the following year served (and every year served), the prisoners will again strip to the waist, back facing the camera, front facing the monitor screens, which will be displaying the tatooed backs of the other prisoners. The monitor screens of any prisoners released the previous year will be blank. Release is the only reason a screen will ever appear blank. Death is not allowed.

Cheating of any kind, which includes guessing, and facing or signaling into the video camera, is punished horribly, though not in such a way that the video camera would see the results the following year. So cheating is simply not done. Discovering the color of one's spot is to be accomplished by logic alone.

Assume that all the prisoners have the goal of getting out of prison as soon as possible.

. . .

So how does this play out? Does anyone ever discover his spot color and go free? If so, when?

Does everyone eventually go free? If so, when does the last one leave?

Explain the logic needed to solve the puzzle.


Solution to the Prisoners puzzle:

Let n be the number red or black spots, whichever is smaller.

  • The first prisoners (those of the minority color) go free at the end of year n.
  • All the rest go free at the end of year n+1.


Explanation:


Assume for this explanation that there are fewer reds than blacks.

Scenario A - There is exactly 1 red spot

End of year 1:
  1. The prisoner with the red spot sees no red spots on any other prisoners and reasons that there is only one red spot and he has it. He informs the warden of this and goes free.

  2. Each of the others sees only one prisoner with a red spot and reasons that either there is only one red spot (on the prisoner he can see with a red spot), or there are two red spots (one on the prisoner he can see with it and the other on himself). There's no way to tell which is the case, at this point.
End of year 2:
  1. Each of the others, noticing that the prisoner with the red spot is now gone and understanding the logic of Year 1 step (1), now knows there was only one red spot to begin with and that therefore he himself must have a black spot. He informs the warden and goes free. Everyone is now gone.

Scenario B - There are exactly 2 red spots

End of year 1:
  1. Each prisoner with a red spot sees exactly one red spot among the other prisoners and reasons that either there is a total of only one red spot and the prisoner he sees with a red spot has it, or there are two red spots: one on the prisoner he can see and one on himself. There's no way to tell which is the case at this point.

  2. Each prisoner with a black spot sees two red spots among the other prisoners and reasons that either there are a total of two red spots, with none on himself, or there are three red spots, including one on himself. There's no way to tell which is the case at this point.

End of year 2:
  1. Each prisoner with a red spot understands that if indeed there had been only one red spot, Scenario A would have applied and the prisoner having the red spot would have left at the end of year one. But since everyone is still present, there must (by his own year-1 reasoning) be a total of exactly two red spots. And since each prisoner with a red spot can see only one other prisoner with a red spot, he knows he must have the second red spot. Both red spot prisoners report to the warden when the viewing is over, explains his reasoning and is released.

  2. Each prisoner with a black spot still sees no one has yet gone (remember, it's still morning at the end of year two, and any freed prisoners won't be released until after the videos are shut off and won't be known about until the morning of the last day of year 3), so the two year-1 possibilities still remain.

End of year 3:
  1. The remaining prisoners see that both the red spot prisoners have gone and understand the red spot prisoner reasoning that led to this: i.e., that there were a total of exactly two red spots. They further understand that since both these are now gone, the remaining prisoners have black spots. All the black spot prisoners report to the warden when the viewing is over, explain their reasoning and go free. Everyone is now gone.

Scenario C - There are exactly 3 red spots

End of year 1:
  1. Each prisoner with a red spot sees exactly two red spots among the other prisoners and reasons that either there is a total of two red spots and the prisoners he sees with red spots have them, or there are three red spots: two on the prisoners he can see and one on himself. There's no way to tell which is the case at this point.

  2. Each prisoner with a black spot sees three red spots among the other prisoners and reasons that either there are a total of three red spots with none on himself, or there are a total of four red spots including one on himself. There's no way to tell which is the case at this point.
End of year 2:
  1. Each red spot prisoner knows that it's too soon to tell whether there are a total of two or three red spots. If there are two, it won't become apparent till year 3 (see Scenario B).

  2. Each prisoner with a black spot sees no one has yet left, so the two year-one possibilities still remain.
End of year 3:
  1. Each red spot prisoner can see that no one has left yet, so there must have been a total of three red spots; if there'd been two, their prisoners would have left at the end of year 2, as per Scenario B. Since each red spot prisoner now knows there are three red spots but can see only two, he knows he himself has the third red spot. Each red spot prisoner reports to the warden when the viewing is over and leaves.

  2. Each prisoner with a black spot sees no one has left yet, so the two year-one possibilities still remain.
End of year 4:
  1. The remaining prisoners notice that all three red spot prisoners have gone and understand the red spot prisoner reasoning that led to this: i.e., that there were a total of exactly three red spots. They further understand that since all three of these are now gone, the remaining prisoners all have a black spot. Each black spot prisoner reports to the warden when the viewing is over, explains the reasoning and goes free. Everyone is now gone.

Scenario D - There are exactly 4 red spots

End of year 1:
  1. Each prisoner with a red spot sees exactly three red spots among the other prisoners and reasons that either there is a total of three red spots and the prisoners he sees with red spots have them, or there are four red spots: three on the prisoners he can see and one on himself. There's no way to tell which is the case at this point.

  2. Each prisoner with a black spot sees four red spots among the other prisoners and reasons that either there are four red spots total with none on himself, or there are five red spots total including one on himself. There's no way to tell which is the case at this point.
End of year 2:
  1. Each red spot prisoner knows that it's too soon to tell whether there are a total of three or four red spots. If there are three, it will, by Scenario C, be the end of year 4 when this becomes apparent.

  2. Each prisoner with a black spot knows that it's too soon to tell whether there are a total of four or five red spots.
End of year 3:
  1. Still too early to tell. No one leaves.
End of year 4:
  1. Each red spot prisoner can see that no one has left yet, so there must have been a total of four red spots; if there'd been three, they would have left at the end of year 3, as per Scenario C. Since there are four red spots but each red spot prisoner can see only three, he knows he has the fourth red spot. Each red spot prisoner reports to the warden when the viewing is over and leaves.

  2. Each prisoner with a black spot sees no one has yet left, so the two year-1 possibilities still remain.
End of year 5:
  1. The remaining prisoners notice that all four red spot prisoners have now gone and understand the red spot prisoner reasoning that led to this: i.e., that there were a total of exactly four red spots. They further understand that since all four of these are now gone, the remaining prisoners all have a black spot. All the black spot prisoners report to the warden when the viewing is over and go free. Everyone is now gone.

Scenario E - There are exactly 5 red spots

And so on. The scenario for this and for every other number n of red spots follows the same reasoning as above. In every case, everyone goes free. All the red-spot prisoners leave at the end of the nth year; all the black-spot prisoners leave at the end of the following year, year n+1.

Notice that if there were 76 reds and 24 blacks and the above procedure counting reds were used, it would be 76 years before the reds went free and 77 years for the blacks. But if blacks were counted instead, the blacks would get out in 24 years and the reds in 25. All prisoners would be aware of this and, wanting to get out as soon as possible, would assume blacks instead of reds in the above scenarios. The logic of the scenarios would generally be applied to the color of the smaller number.

So how does a prisoner find out his color?

The above scenarios are based on an objective knowledge of how many red spots there actually are and work from there. A prisoner, however, would not know how many red (or black) spots there were. So how can he use the logic of the scenarios to discover the color of his spot and know when to leave?

At the end of the first year, everyone counts the spots to see how many there are of each color and notices which color has the lower number.

Let's suppose I am a prisoner and in my first viewing, at the end of my first year there, I count 29 red spots. This means that either:
  1. I have a red spot and see only 29 of the 30 actual red spots, or
  2. I have a black spot and see all 29 of the 29 actual red spots.
But I know two facts from the logic of the scenarios above:
  1. Those having the minority color (the color of which there are fewer) leave first. In this case, there are fewer red spots than black spots, so I know that the reds will leave first.
  2. The minority color will leave in the year corresponding to the actual number of spots having that color — not the perceived number but the actual number. I see 29 red spots; but the actual number, as in (1) and (2) above, could be either 29 or 30. So the reds will be leaving in either year 29 or year 30.
If I'm a black, I don't have to worry; I'll just leave the next year after the reds leave. But what if I'm a red? How will I know when to leave?

By point (1) above, if I'm a red, there are actually 30 reds and so no one will leave till year 30. But if I'm a black, point (2) tells me there are only 29 reds and they will leave in year 29, a year earlier.

So I can use this. Assume that I'm a black. If this assumption is true, then I'll see (in year 30) that all the reds left in year 29. In which case, I declare myself a black and leave in year 30.

But if the year 30 viewing comes around and I see that no one has left in year 29, then I'll know my assumption of blackness was false and that in fact I'm a red. I'll then declare myself a red and leave (still in year 30). The blacks (not that I care) become aware of the departure in year 31 and leave.


But what if there are 50 blacks and 50 reds?

The same plan is followed. The only difference is that everyone leaves the same year, year 50.

If I see 49 reds, then I know that either:
  1. I have a red spot and see only 49 of the 50 actual red spots, or
  2. I have a black spot and see all 49 of the 49 actual red spots. (In which case, of course, we'll not be dealing with a 50-50 split at all but a 49-51 split.)
In either case (as above), I assume I'm a black. If the assumption is true, then I'll see in year 50 that all the reds left in year 49. In which case, I declare myself a black and leave in year 50. But if the year 50 viewing comes around and I see that no one has left in year 49, then I'll know my assumption of blackness is false and that in fact I'm a red. I then declare myself a red and leave (still in year 50).

The blacks meanwhile see 49 blacks in year 1, and, following the same logic, they too all leave in year 50.

It turns out then that the maximum time anyone will stay in prison is 50 years. Or 100 years if there were a total of 200 prisoners. Or 30 years if a total of 60 prisoners, and so on. And each prisoner will know after the very first year how long his stay will be. All he has to do is count the number of spots having the least common color. That number, or one more than that number, will be the total number of year he'll be there.