mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2005-10-15, 12:53   #1
fetofs
 
fetofs's Avatar
 
Aug 2005
Brazil

2×181 Posts
Default Classic: Hats puzzle

Many people already know this puzzle, but others might find it interesting, at least.

There is an island with 10 inhabitants. One day a monster comes and says that he intends to eat every one of them but will give them a chance to survive in the following way:
In the morning, the monster will line up all the people - single file so that the last person sees the remaining 9, the next person sees the remaining 8, and so on until the first person that obviously sees no one in front of himself. The monster will then place black or white hats on their heads randomly (they can be all white, all black or any combination thereof).
The monster will offer each person starting with the last one (who sees everyone else's hats) to guess the color of his/her own hat. The answer can only be one word: "white" or "black". The monster will eat him on the spot if he guessed wrong, and will leave him alive if he guessed right. All the remaining people will hear both the guess and the outcome of the guess. The monster will then go on to the next to last person (who only sees 8 people), and so on until the end.
The monster gives them the whole night to think.

The Task:
Devise the optimal strategy that these poor natives could use to maximize their survival rate.

Assumptions:
1) All the 10 people can easily understand your strategy, and will execute it with perfect precision.
2) If the monster suspects that any of the people are giving away information to any of the remaining team members by intonation of words when answering, or any other signs, or by touch, he will eat everyone.

Most people know this puzzle by the "prisioner" version:

10 straight-jacketed prisoners are on death row. Tomorrow they will be arranged in single file, all facing one direction. The guy in the front of the line (he can't see anything in front of him) will be called the 1st guy, and the guy in the back of the line (he can see the heads of the other nine people) will be called the 10th guy. An executioner will then put a hat on everyone's head; the hat will either be black or white, totally random. Prisoners cannot see the color of their own hat. The executioner then goes to the 10th guy and asks him what color hat he is wearing; the prisoner can respond with either "black" or "white". If what he says matches the color of the hat he's wearing, he will live. Else, he dies. The executioner then proceeds to the 9th guy, and asks the same question, then asks the 8th guy ... this continues until all of the prisoners have been queried.

This is the night before the execution. The prisoners are allowed to get together to discuss a plan for maximizing the number of lives saved tomorrow. What is the optimal plan?

P.S: After you try to solve it by the "black and white" case, assume the 7 rainbow colors are used. After that, generalize it to N people and K colors of hats. Good luck
fetofs is offline   Reply With Quote
Old 2005-10-15, 15:48   #2
S80780
 
Jan 2003
far from M40

53 Posts
Default

Obviously, the 10th person has a 50% chance to survive, as noone
except the monster can see his/her hat's colour. Nonetheless, the person is
able to see all the other 9 hats. As 9 is odd, there must be an odd number
of either white or black hats remaining. So, by "guessing" the color which
appears an odd number of times, the 10th person survives with 50% chance
and gives away all information needed to save the remaining 9.
The (2n+1)th person survives by confirming his/her neighbour's choice, if
that colour appears an even number of times among the remaining 2n hats,
and altering it otherwise.
The 2nth person survives by confirming his/her neighbour's choice, if that
colour appears an odd number of times among the remaining (2n-1) hats,
and altering it otherwise.

If there were an odd number of inhabitants, the one who's asked first would
have to "guess" a pre-agreed-upon colour, if his/her neighbour's hat has the
colour that appears an odd number of times among the remaining ones,
excluding his/her neighbour.
S80780 is offline   Reply With Quote
Old 2005-10-16, 02:08   #3
Citrix
 
Citrix's Avatar
 
Jun 2003

1,579 Posts
Default

Quote:
Originally Posted by fetofs
The monster will then place black or white hats on their heads randomly
Since the monster is putting the hats randomly there is no real solution, there is nothing to mathematically or logically think about. Standing anywhere is equivalent. The main factor will be luck, which is again random. Or as some say "chance favors the prepared mind". What if the people united to fight the monster.

Anyway for the probability of being eaten is here, based on position
#10=50%
#9=33%
....
Since the person standing first in the line has the lowest probability of being eaten, standing there is the best thing. They will avoid the monster the longest. But again it is based on luck and anything can happen.

Citrix

Last fiddled with by Citrix on 2005-10-16 at 02:10
Citrix is offline   Reply With Quote
Old 2005-10-16, 05:03   #4
axn
 
axn's Avatar
 
Jun 2003

3·1,619 Posts
Default General Strategy - N people. K colors

Assign the colors numbers from 0 thru K-1.

Person(N) sums up the colors of all the people in front of him modulo K,
and announces the corresponding color. He will survive with probability 1/K.

Person(N-1) also sums up the colors in front of him modulo K
and then subtracts the color announced by person(N) (again modulo K).
He survives!!

Repeat!


Last fiddled with by axn on 2005-10-16 at 05:04
axn is offline   Reply With Quote
Old 2005-10-16, 05:21   #5
Citrix
 
Citrix's Avatar
 
Jun 2003

62B16 Posts
Default

I have a variant of this question:

If the monster wanted to eat a person. Say the name of one of the persons their was XYZ and the monster wanted to eat him for some personal reasons. Then how should the monster place the hats such that it is most likely that he will be having XYZ for dinner tonight.
What algorithm should the monster use?

Citrix
Citrix is offline   Reply With Quote
Old 2005-10-16, 11:23   #6
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

44116 Posts
Default

Quote:
Originally Posted by fetofs
The Task:
Devise the optimal strategy that these poor natives could use to maximize their survival rate.
Quote:
Originally Posted by citrix
What if the people united to fight the monster.
Anyway for the probability of being eaten is here, based on position
Citrix,
This collaboration is implied by the statement of the task. However, you are looking at the individuals rather than the collective group. I believe that you should be seeking a solution that maximizes the expected number of survivors. Perhaps you should consider the idea of sacrificing one individual to save the majority of the group.
Wacky is offline   Reply With Quote
Old 2005-10-16, 11:33   #7
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

Quote:
Originally Posted by Citrix
I have a variant of this question:
What algorithm should the monster use?
If the monster has no control over the placement of the individuals in the line, his only strategy to improve his odds is:

CHEAT (change the rules) -- Assuming that the group is capable of determining and executing the optimum strategy, the odds of survival are independent of the actual color placements.
Wacky is offline   Reply With Quote
Old 2005-10-16, 11:45   #8
fetofs
 
fetofs's Avatar
 
Aug 2005
Brazil

2·181 Posts
Default

Quote:
Originally Posted by Wacky
If the monster has no control over the placement of the individuals in the line, his only strategy to improve his odds is:

CHEAT (change the rules) -- Assuming that the group is capable of determining and executing the optimum strategy, the odds of survival are independent of the actual color placements.
Or to listen to the prisioner's strategy and place the hats such that the sum mod k of the first won't be the color of his hat (at least he needs something to eat :) )
fetofs is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Classic problem: Four 4's Ken_g6 Puzzles 105 2016-10-20 20:36
Suggestions for the "Classic Summary" page davieddy PrimeNet 26 2011-06-13 09:38
"Classic" (colourful) Status report davieddy PrimeNet 6 2009-10-04 08:33
Dot puzzle nibble4bits Puzzles 37 2006-02-27 09:35
Classic puzzle JuanTutors Puzzles 24 2005-08-28 23:46

All times are UTC. The time now is 05:21.

Sat Mar 6 05:21:15 UTC 2021 up 93 days, 1:32, 0 users, load averages: 0.97, 1.46, 1.64

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.