Author |
Topic: Single file hat execution variation (Read 5104 times) |
|
Trebla
Newbie
Gender: 
Posts: 16
|
 |
Single file hat execution variation
« on: Mar 10th, 2005, 2:23pm » |
 Quote  Modify
|
Saw this somewhere else, couldn't find it here and thought it might be interesting for y'all.
Same premise as Single File Hat Execution, you have 10 prisoners, each gets a black or white hat placed randomly on their head, they meet the night before the execution to devise a strategy. However...
The prisoners are arranged in a circle and every prisoner can see every hat except their own. At a predetermined moment in time, each prisoner must simultaneously call out "Black" "White" or "Don't Know" (they all shout at the same time). If at least one person is correct and none are wrong, they "win" and are all released ("Don't know" is not a wrong answer), if even a single person is wrong, they are all executed. I think it's fair to assume you only have the off/on/neutral bit to communicate, and no gestures or speech are allowed at any point during the process (except of course when it's time to claim your hat color).
And the obligatory... generalize for k different colored hats and n prisoners where 2 <= k <= n.
|
| « Last Edit: Mar 10th, 2005, 2:24pm by Trebla » |
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Single file hat execution variation
« Reply #1 on: Mar 10th, 2005, 5:55pm » |
Quote Modify
|
What process? what communication? Are you sure you have this stated correctly, because the way it reads, they simply sit down, and all at once they must declare their hat color. There is even no description of what happens if they all shout "Don't know". Does another round occur?
Assuming so: since there is no other communication allowed, they must all shout "Don't know" at the first round, or chance being wrong. But since this response is required of everyone alike, no one can learn from it, so they are in no better shape for a second round, and must do the same. I see no way to break this deadlock without someone guessing. Which makes me believe the puzzle is misstated.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Guessed
Guest
|
|
Re: Single file hat execution variation
« Reply #3 on: Mar 18th, 2005, 9:17am » |
Quote Modify
 Remove
|
I don't see how you can beat the best case of three hat-wearers, with a 0.75 chance of them guessing correctly, as in the original puzzle. Assuming it is possible to designate three guessers, you could just have those three ignore the other seven hats and guess based on the colour of their own hats only, with the remaining seven people saying "don't know".
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Single file hat execution variation
« Reply #4 on: Mar 21st, 2005, 6:37pm » |
Quote Modify
|
There is no requirement that all hat-wearers must follow the same algorithm. They can assign themselves unique bit numbers, then each considers the hat color assignment as an N bit long Hamming code capable of correcting one error with one corrupted bit (oneself) and guesses the color that will result in an invalid Hamming code if the combination of the remaining bits belongs to a valid code, and remains silent otherwise. Only the codes that are 2^n-1 bits long are "perfect", that is every bit combination is either a valid code, or is one bit flip away from a valid code. Therefore for 10 guessers, 3 must always remain silent and the other 7 ignore them.
This way if the hat color configuration is a valid Hamming code, everybody will guess incorrectly, and if it is not, one person will guess correctly.
As longer Hamming codes constitute less than 25% of all possible bit configurations (in other words, they have more than 2 error correcting bits), the probability of winning grows beyond 3/4. For 7 to 14 participants it is 7/8; for 15 to 30 it is 15/16, etc.
The simplest Hamming code is a 3-bit code capable of correcting one error: 000 means 0, 111 means 1 - exactly the case of 3 hats.
[e] Corrected HTML tags.
|
| « Last Edit: Mar 21st, 2005, 6:39pm by Leo Broukhis » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print