Prisoners with hats in a line 2

Logic Level 3

7 prisoners stand in a line such that they can only see the prisoners in front of them. Each prisoner randomly gets either a great haircut or bad haircut (without them knowing which). Starting from the back of the line, each prisoner must either guess her own hair situation or pass.

In order to win, at least one prisoner must guess correctly, and no prisoners can guess incorrectly .

They can strategize in advance. What is the optimal strategy? How likely is it to work?

50%-75% 0%-50%
99%
75%-90% 90%-99%

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Julian Poon
Sep 21, 2015

Strategy:

For the first person to be asked: If there are 1 1 or more people with a bad haircut in front of him, pass. If there are 0 0 people in front of him with a bad haircut, say that he himself has a good haircut.

The second person to be asked: If the person before him says that he has a good haircut, pass. If the person before him says pass, and there are 0 0 people with a bad haircut in front of him, say that he has a good haircut. If the person before him says pass, and there are 1 1 or more people in front of him with a bad haircut, say pass.

The third, fourth, fifth, sixth and seventh person would follow the same algorithm as the second person.

The idea for this is that should anybody say that he has a good haircut, and that he isn't the first person, it means that he sees 0 0 person in front of him with a good haircut and the guy before him has seen 1 person in front of him with a good haircut, and this indicates that he is the one with a good haircut.

The only way for this not to work is when the first person sees 0 0 people with a bad haircut, causing him to guess his own haircut. The probability of everybody else having a bad haircut is 1 2 6 \frac{1}{2^{6}} , and the probability for the first person to guess it wrong is 1 2 \frac{1}{2} .

Therefore, the probability that this would work is 1 1 2 6 × 1 2 = 99.219 % 1-\frac{1}{2^{6}} \times \frac{1}{2}=99.219\text{\%}

Melissa Quail
Sep 13, 2015

The prisoner at the back states the haircut of the person directly in front of them. The person directly in front of them then guesses the same haircut so assuming the person at the back is telling the truth and isn't blind, they will be correct. Therefore, the strategy is almost certain to work so the answer is >99%.

This strategy doesn't quite work - they lose if anyone makes an incorrect guess, so if the prisoner in the back is wrong, they lose! Therefore, this strategy ensures success 50% of the time.

Maggie Miller - 5 years, 9 months ago

Log in to reply

Yes you're right I didn't notice that clause when I solved the question - maybe the wording of the question has changed since I wrote the solution.

Melissa Quail - 5 years, 9 months ago
Lee Isaac
Sep 11, 2015

The last prisoner (who can see everyone) guesses first. He picks any one in front of him (Lets call that person Calvin) , and looks if Calvin's haircut is good or bad. He then guesses that his haircut is the same (good or bad) as Calvin.

If Calvin has a good haircut, the prisoner at the back says he has a good haircut.

If Calvin has a bad haircut, the prisoner at the back says he has a bad haircut.

Next, everyone else guesses the same as the last prisoner.

Calvin will definitely guess his hairstyle correctly.

Since this is certain (unless Calvin tries to sabotage everyone) the probability is 100%, so the best option to pick is ">99%".

But why would Calvin end up in prison? More importantly, What if some prisoners do not like ramen?

Edit: whoops this solution is wrong sorry guys

What if Calvin and the last prisoner have different hairstyles ? Then the last prisoner would have made a wrong guess

Vibhor Agarwal - 5 years, 9 months ago

Log in to reply

Sorry guys I didn't see "no prisoners can guess incorrectly"!

Well at least I got the answer right ;)

Lee Isaac - 5 years, 8 months ago

Log in to reply

har har har

Julian Poon - 5 years, 8 months ago

@Vibhor Agarwal makes a good point. This strategy will work only if every prisoner has the same hairstyle, giving a 1.6% chance of success.

Maggie Miller - 5 years, 9 months ago

See, as u say the person at the back of calvin tells his style of haircut. But now Calvin would be in a dilemma becoz if he utters his haircut, the person in front of him will be in trouble and if he would help him, he himself would be in trouble. If u want the real strategy, feel free to contact me. -Tanay Gaurav.

tanay gaurav - 5 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...