Welcome to MindCipher, a social repository of the world's greatest brain teasers, logic puzzles and mental challenges.

Black and White Hats

There are 100 prisoners in jail. Their guards decide to play a game with them. Here's what happens:

1) The prisoners are lined up in a single file, front to back, such that the prisoner at the back of the line can see the 99 prisoners ahead of him, the prisoner immediately ahead of him can see the 98 prisoners in front of him and so on.

2) A randomly selected hat is placed on each prisoner's head. The hat may be black or white.

3) Starting from the back of the line (i.e. starting from the prisoner that can see 99 prisoners in front of him), a guard asks each prisoner what the colour of their hat is. If the prisoner answers correctly, he lives, otherwise, he is killed.

The prisoners are given these rules and then given 15 minutes to strategize before the game begins. What is the strategy that maximizes the expected value of the number of them that survive?

FAQ:

  • Can the prisoners take off their hats and look at them? No.

  • Do we know in advance how many of each colour hat there is? No.

  • Can the prisoners communicate with the other prisoners in any way apart from responding to the guard's question after the strategizing time is over? No.

  • Is an expected value of 75 survivors the best that can be achieved? Nope :)

Here's the strategy that gives an expected value of 99.5 survivors:

  • The prisoner at the back counts the number of white hats. If he sees an even number of white hats, he says "white" when asked by the guard, if he sees an odd number of white hats, he says "black" when asked by the guard.

  • The next prisoner to be asked (the one that can see 98 prisoners in front of him) can count the number of white hats ahead of him and, based on what the first prisoner said, determine whether he is wearing a white or black hat. Specifically, suppose the first prisoner answered "black", indicating that there is an odd number of white hats. Then, if the second prisoner's count is also odd, he must be wearing a black hat. If the second prisoner's count is even, he must be wearing a white hat.

  • Based on the previous responses, keeping track of whether they should expect an odd or even number of white hats in front of them, every prisoner can determine whether they are wearing a black or white hat.

  • Since the first prisoner is the only one who's response is up to chance, he has a 50/50 chance of survival. Everyone else has a 100% chance of survival, so we expect 99.5 of them to survive.

This is related to the concept of a parity bit used for error detection in computers.

Comments


Ali Ali

Hi, I have a scenario that disproves the theory.

What if number 100(last one in the line) is wearing a black hat and there is only one other person also wearing a black hat ?

He would then see 98 white hats (even number) and 1 black hat (odd)....so hence he would say white and die....

please explain if I missed something.

  

Jeremiah Visaya

50/50 shot he is wearing black or white.....what everyone else is wearing will not determine whether he lives or dies, chance will determine that.


viswa

the first person who responded to prisoner will have 50-50 chances right.


SavageFred

Is the prisoner killed immediately? In other words, do the remaining prisoners know if the prisoners behind them answered correctly?

  

Aakash

Good question. No, the other prisoners don't need to know whether each prisoner answered correctly.


Tarun245

They should take of their hats, look at it, and then put it back on. There is no rule that prohibits that.

  

Aakash

You're right - I've updated the puzzle :)

  

eid lla ew

Also no rule prohibiting the use of mirrors


Kaushik Nayak

Altruistic prisoner!


Anand Kumar

Another Solution can be : The prisoner makes decision on basis of next two prisoner hat. If next two wear w,w or w,b he says white and if it is b,b or b,w he says it as b. Now after that 99th prisioner know which color hat is he wearing and henceforth.

so here also only 100th prisioner is in danger of 50-50. while rest are correct;

  

Aakash

Hey Anand, that scheme won't work. Consider this scenario starting from the back: BWBB...

According to what you've described, the first prisoner (wearing a black hat), will say "white" and be killed. The second prisoner (wearing a white hat) has to say "black" because the two prisoners in front of him are wearing black. Since he is wearing white, he is killed as well. As such, more than just 1 prisoner is at risk in this design.


Víctor Ortiga

Nope. If we have 30 white hats and 70 black hats; the last prisoner sees either 70 or 69 black hats in front of him; then, if he supposes the chances of getting each color was 50/50 he will say "white", on the other hand, if he supposes the chances of getting black were greater than the ones of getting white he would say "black" (you don't specify if they know the chances of each color nor which are those chances), and the same goes for every prisoner so, essentially, they survival chances depend on how many hats of each color there are and what do the prisoners suppose about the hats' color chances.

The fact is that you said that we don't know how many hats of each color we have but you give a solution for 50 white and 50 black (it's the only way talking about an odd or even number makes any sense) in which case the rate of survival is 100%, not even the first one is up to chance (by first you mean the first on line or the first saying the color?) as they all see or know the color of 99 hats.

  

Víctor Ortiga

my bad:

*their

  

Aakash

Hey Victor, thanks for the comment. If you take a closer look at the solution, you'll see that it works for any number of white and black hats. Try it for the extreme case 0 black hats followed and 100 white hats.

They key thing to remember is the third part in the solution: spoiler Based on the previous responses, keeping track of whether they should expect an odd or even number of white hats in front of them, every prisoner can determine whether they are wearing a black or white hat.


Atul Joshi

Take the case with 99 black and the last one is wearing white.. What would he say .. because it is not given equal number of white and black hats ..

  

Atul Joshi

ok got it... :)


Nikola Ratinac

Since it doesn't say that the prisoners can't move, here's the design. It is pretty easy for them to arrange them selves in the next way: w, w, w, . . . ., w, b,. . ., b, b, b.(Google's dwarf problem) So starting from the left the guards asks, the prisoner answers the color of what he sees in front of him meanwhile every prisoner counts the number of hats and what color are they in front and memorizes the number of the hats and color behind him . 100 of them are saved !


OverDivine

there is no strategy because every hat is randomly selected it's pure luck really there aren't 50 black hats and 50 white hats it's like each prisoner has to flip a coin and tails gets to live


Joep

Parity (odd or even) is the only mathematical criteria changing every single time you add one hat and is therefore key to the answer. The first prisoner says black if there is an odd number of black hats, white if it's an even number of white hats.

Check out other puzzles:
Random  

Like this? You might also like:
Non-Adaptive 12 Identical Balls
The Sinking Island
Boys and Girls
Submitted by
Aakash
over 3 years ago
Likes
Difficulty 8.9 ?

Tags
logic prisoners hats


Back