New optimal solution for the prisoner hat riddle?

At Gloc Media we love riddles. They have nothing to do with our work or digital marketing, but since we like them so much today we want to move away from the digital universe and talk about riddles for one day :)

We recently came across the prisoner hat riddle via TED, they posted this video below on their social media channels a while ago.

We really enjoyed thinking about this riddle and solving it. However, we didn’t end up fully satisfied with the solution they offer… so we decided to create our own – and we believe it might bring some value to the table! Probably not in a strict, mathematical way, but perhaps in a common-sense, logical way. Now if you don’t want me to spoil the riddle for you, do not continue reading beyond this line because I’m going to talk about the solution!

According to the solution in the second part of the video, there is an optimal solution in which you can save 9 of the prisoners, with the remaining one prisoner having a 50/50 chance.

Now, the key of the solution presented here (and I’m paraphrasing the video narrator) is that the person at the back of the line who can see everyone else’s hats can use the word (black or white) to communicate some coded information. The rest is very well explained in the video; assigning the total [black/white] hats number’s parity to a colour, etc. So as a result, as said above, in an optimal scenario you can save 9 prisoners, and the prisoner #1 who spoke first will have a 50/50 chance.

But what if we could optimise that 50/50 chance of prisoner #1? After all, a 50% survival rate is not that great! What if prisoner #1 could, just by saying the word [black/white] communicate some coded information to save all other 9 prisoners AND increase his chances of getting his colour right at the same time? Well, we tried to go about it based on the assumption that encountering a balanced distribution of the hats is slightly more probable than a polarised distribution (e.g. 5 black hats & 5 white hats is a tiny bit more probable than 9 black hats & 1 white hat).

We came up with an idea to make his survival rate higher by leveraging this assumption while still saving all other 9 prisoners.

The key of the original solution is the strategy they agree upon:

Once prisoner #1 is placed on the line, he will look at the parity of the number of [black/white] hats, and if it’s odd he will say [Colour X] while if it’s even he will say [Colour Y]

That’s the statement, the strategy used for the solution in the video above.

If this statement would be different, the meaning of the key word [black/white] would change too. And so would the consequences. Let’s try with this different, a bit more complex statement:

Once prisoner #1 is placed on the line he will see 9 hats, therefore there must be more X coloured hats than Y coloured hats or vice versa, meaning there will be a predominant colour (more frequent). Prisoner #1 will look at the difference in number between the predominant and the less frequent colour. It is a fact that this difference will be an odd number, since he can see 9 hats. This number can only be 1, 3, 5, 7 or 9. Now, if the predominant colour is superior by:

– One, five or nine, then he will say the less frequent colour

– Three or seven, then he will say the predominant colour

What happens if they go with this statement? Go ahead and test it yourself with different scenarios. Not only all other 9 prisoners are saved, but the chances of survival of prisoner #1 go slightly above 50%. Why? Let’s have a look first at how it would play out:

Example scenario:

Let’s have a look at what each prisoner can see in the example above with blue and red hats:

Prisoner #1 can see 9 hats, 5 red and 4 blue. Since the difference it’s just one hat down for the blues, he will have to say the less frequent colour. He says blue.

Prisoner #2 can see 8 hats, 5 red and 3 blue. Since the difference it’s 2 hats down for blues, if his own hat was red, the difference prisoner #1 would have seen would have been 3, and therefore he would have said red, the predominant colour. However prisoner #1 said blue, meaning the difference was just one hat. Therefore prisoner #2 must be blue. He says blue.

Prisoner #3 can see 7 hats, 4 red and 3 blue, and also knows for a fact that prisoner #2 is blue. So 4 for each colour. If his hat was blue, the predominant colour prisoner #1 would have seen would have been blue by only 1 hat up for the blues, and as a result he would have said red. But he said blue, therefore prisoner #3 must be red. He says red.

Prisoner #4 can see 6 hats, 3 red and 3 blue, and also knows for a fact that prisoner #2 is blue and prisoner #3 is red. So 4 for each colour. If his hat was blue, the predominant colour prisoner #1 would have seen would have been blue by only 1 hat up for the blues, and as a result he would have said red. But he said blue, therefore prisoner #4 must be red. He says red.

Prisoner #5 can see 5 hats, 3 red and 2 blue, and also knows for a fact that prisoner #2 is blue and prisoners #3 and #4 are red. In total, 5 red and 3 blue. Since the difference it’s 2 hats down for blues, if his hat was red, the difference prisoner #1 would have seen would have been 3, and therefore he would have said red, the predominant colour. However prisoner #1 said blue, meaning the difference was just of one hat. Therefore prisoner #5 must be blue. He says blue.

Same logic can be applied to the rest of the prisoners and this logic works with all scenarios.

However, what does this new solution bring to the table? Why does prisoner #1 have a survival rate greater than 50% with this model? We can at least agree that this solution is as valid as the original one, since it saves all other 9 prisoners. What about prisoner #1? Are his chances really better now?

Well, as discussed earlier, it seems to us that things in nature tend to be balanced and in general in an equilibrium, and therefore a rather balanced distribution of the hats seems more plausible. Thus, if prisoner #1 says the non-predominant colour, his chances of getting it right should be slightly higher. But is a balanced distribution of the hats really more probable? Well, not necessarily, especially because we are operating at a theoretical level, but in practice, in nature things seem to tend to be that way. When we look at the human sex ratio in the world, we see that we are almost exactly 50% males and 50% females. Like most other species on Earth. If you flip a coin 100 times you won’t probably get 50 times side A and 50 times side B. However, it is much more likely to get, let’s say, 55-45 than 95-5. Even something closer to 80-20 would be pretty rare, but reasonable. But 95-5? How low are the chances? Any statistician around? What about 99-1? Even the total amount of energy on the universe balances itself out and the result seems to be zero. If we accept the balanced nature of the universe, the tendency to equilibrium and the natural way in which entropy seems to avoid extremes and polarities, then it will make more sense to think that it is just slightly more probable to encounter a balanced scenario with some black hats and some white hats, rather than a polar scenario with all hats being black/white.

If we can accept that polarities are less likely than more balanced scenarios, then perhaps we can agree that it is slightly more probable being lined up in a scenario where the colours are balanced. In other words, it seems more likely there will be 6 black hats vs. 4 white hats rather than this scenario being 9-1 or 10-0. If we can accept that it is (even if very slightly) more probable to be placed in a scenario where the number of colours is balanced rather than polar, then prisoner #1 has more chances of guessing his hat colour by saying the non-predominant colour. In all certainty we won’t increase his chances by much, but bottom line is, since this is all theoretical, it doesn’t really matter how much we increase his survival rate, as long as we do increase it.

And our solution does exactly that: prisoner #1 will in most cases say the non-predominant colour, therefore increasing his survival rate

Note: Some might argue that by this logic, the increased survival rate prisoner #1 gains when the difference in number between the predominant and the less frequent colour is 1, 5 or 9, he will lose it when the difference is 3 or 7. However, there are two reasons why his final survival rate is still higher:

1) There are three scenarios where prisoner #1 will say the less frequent colour, which will increase his survival chances: when the difference in number between the predominant and less frequent colour is 1, 5 and 9. On the other hand, there are only two scenarios where he will have to say the predominant colour, which will go against his odds.

2) The difference between the predominant and the less frequent colour being 1 is the most probable scenario in the first place if we accept that balanced distributions are more plausible, therefore even leaving aside the first reasoning above, the outcome is still favourable to prisoner #1 even considering that both scenarios are possible.

Now, obviously we are aware that this principle of balanced distribution has no scientific value whatsoever and won’t be applicable from a mathematical point of view. In the first place, because we are told at the beginning of the riddle that the distribution of hats is totally random. However, we had so much fun thinking of this alternate solution and would love to hear the thoughts of other riddle enthusiasts like us!

Iñigo Etxebeste, August 29, 2017