Logic Puzzles vs. Hat Problem II
This is closer to the unsolved hat problem I have previously discussed than the solved hat problem I discussed. It made the rounds on a “Math Enthusiasts” mailing list I’m on today.
There are n people who have been given a challenge: tomorrow, a hat will be placed on each of their heads. There are n different colors of hats, and colors can be repeated (or not used at all). Everyone will be able to see the hats on everyone else’s head but not their own. No one is allowed to communicate in any way while looking at each others’ hats. Then everyone is lead away into separate rooms and each person is asked the color of their own hat. If at least one person answers correctly, the group as a whole wins (unlike the unsolved hat problem mentioned above, no one is penalized for an incorrect guess). The people can discuss strategy amongst themselves before the challenge starts, but cannot communicate in any way once anyone gets a hat.
What strategy can they use to guarantee that the group wins?
and for the pedants out there: all participants are told all possible hat colors before the challenge starts (no need to guess what the unseen colors might be), and n is small enough that all colors can be distinguished on sight (it uses less than a million different shades of blue, for instance).
I’m assuming the participants know what the possible colors are…?
Oh. Might help to read the whole thing.
Suppose the challenger chooses the hat colors randomly and independently.
Because they’re independent, the information a participant gets on the other hats’ colors has no bearing on their own hat’s. Because there’s no communication, they have no other information on their hat’s color.
Because its color is random, any choice they make is incorrect with P=(n-1)/n. So by using this randomness strategy, the challenger ensures there is a ((n-1)/n)^n > 0 probability that the group fails — by being random the challenger has washed away all effects of the group’s strategy.
What am I missing?
Your train of thought is correct, but the solution does not involve random guessing.
My argument didn’t posit random guessing. :-) It applies to an arbitrary strategy by the participants.
Any given person will only guess correctly 1/n of the time. However, there is a way to evenly distribute correct guesses and to ensure that at least one person always guesses correctly. Quick corollary: since we need 1 person to always guess correctly and on average only 1/n guesses can be correct, the solution must guarantee 1 correct guess and n-1 incorrect guesses for any hat combination.
As a quick example, here’s the solution for n=2 people: person A guesses he’s wearing the same color hat as person B, but person B guesses that she’s wearing a different color hat than person A. Exactly one of them will be right every time. Now, extrapolate to n people. :-)
Ahhh, I see the independence part of my argument was faulty. A’s guess is independent of their hat color, as is B’s, but their correctness probabilities can be made dependent. That’s what I was missing.
(rot13 for spoiler protection. Is there a way to do on-click on on-highlight spoiler protection in LJ comments?)
Rapbqr gur pbybef nf gur ahzoref 0, …, a-1. Cnegvpvcnag v pubbfrf v zvahf gur fhz bs nyy gur ung ahzoref gurl frr zbq a. Yrg gur fhz bs nyy gur ung ahzoref zbq a or k va [0, a-1]. Cnegvpvcnag k pubbfrf gurve bja ung ahzore.
Bingo.
Very nice puzzle. The dependence used is quite subtle, but makes all the difference. Could be useful in probability class about how careful you have to be when making independence arguments! :-)
I’m assuming the participants know what the possible colors are…?