All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Logic
Hats and alligators (Posted on 2006-07-15) Difficulty: 4 of 5
A group of prisoners is under sentence of death and the warder decides to give them a test to gain their freedom. He tells them, "I will place a red or blue hat on each of your heads and then I'm going to arrange you in random order in a row so that no prisoner will be able to see his own hat but each one will see all the hats in front of him. Starting with the guy at the back each of you in turn must loudly say what color hat you think you have. Correct answers will go free, incorrect ones will be thrown to the alligators in the moat. I will give you time for a brief meeting before we start, so you can plan your optimum strategy."

What strategy can the prisoners - there are N of them - adopt to improve their odds above 50:50?

Hint: They need to agree on a strategy which allows each person to identify his/her own hat while simultaneously providing as much information as possible for all those in front.

No Solution Yet Submitted by JayDeeKay    
Rating: 4.4000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution (this is clearly right) | Comment 14 of 19 |
The prisoners agree in advance that the first prisoner will count the number of Reds (Blue would work, as long as they agree on the convention.  We'll go with Red.)

IF there are an even number of Reds, he'll say Red; otherwise he'll say Blue.

The next prisoner can see everything but his own hat.  He counts the Reds, and then he uses what he sees plus the initial Red/Blue to deduce what he has.  Example: He counts an even number of Reds.  If the initial prisoner said Red, he knows he has Blue, which preserves the even count of Reds, and says Blue.  If the initial prisoner said Blue, he knows there's an odd count of Reds, so he has Red, and says Red.

Each subsequent prisoner can count what his predecessors said and combine that information with what he sees to make the equivalent deduction.

Therefore, all but the first prisoner chosen are guaranteed to survive, and the first prisoner has a 50/50 chance.

  Posted by Bob on 2006-07-21 00:13:43
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information