wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Single file hat execution variation
        
(Message started by: Trebla on Mar 10^th, 2005, 2:23pm)

Title: Single file hat execution variation
Post by Trebla on Mar 10^th, 2005, 2:23pm

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.

Title: Re: Single file hat execution variation
Post by Icarus on Mar 10^th, 2005, 5:55pm

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.

Title: Re: Single file hat execution variation
Post by Leonid Broukhis on Mar 10^th, 2005, 6:59pm

No surprise you could not find it: the default search options do not look farther than a year.

Here is the thread:

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1028010706

Title: Re: Single file hat execution variation
Post by Guessed on Mar 18^th, 2005, 9:17am

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".

Title: Re: Single file hat execution variation
Post by Leonid Broukhis on Mar 21^st, 2005, 6:37pm

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.