mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   Classic: Hats puzzle (https://www.mersenneforum.org/showthread.php?t=4846)

 fetofs 2005-10-15 12:53

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.

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 :wink:

 S80780 2005-10-15 15:48

[spoiler]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.[/spoiler]

 Citrix 2005-10-16 02:08

[QUOTE=fetofs] The monster will then place black or white hats on their heads randomly
[/QUOTE]

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. :rolleyes: :bounce:

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

 axn 2005-10-16 05:03

General Strategy - N people. K colors

[left][spoiler]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![/spoiler]
[/left]

 Citrix 2005-10-16 05:21

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

 Wacky 2005-10-16 11:23

Devise the optimal strategy that these poor natives could use to maximize their survival rate.[/QUOTE]
[QUOTE=citrix]What if the people united to fight the monster.
Anyway for the probability of being eaten is here, based on position[/QUOTE]

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 2005-10-16 11:33

[QUOTE=Citrix]I have a variant of this question:
What algorithm should the monster use?
[/QUOTE]

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

[spoiler] 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. [/spoiler]

 fetofs 2005-10-16 11:45

[QUOTE=Wacky]If the monster has no control over the placement of the individuals in the line, his only strategy to improve his odds is:

[spoiler] 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. [/spoiler][/QUOTE]

[spoiler]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 :) )[/spoiler]

 All times are UTC. The time now is 15:32.