Logic Puzzles vs. Hat Problem II

[big_bad_al]

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

Comments

[ext_227579]

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?

[big_bad_al]

Your train of thought is correct, but the solution does not involve random guessing.

[ext_227579]

My argument didn't posit random guessing. :-) It applies to an arbitrary strategy by the participants.

[big_bad_al]

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. :-)

[ext_227579]

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.