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.
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. :-)
(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.
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! :-)
Comments 10
Reply
Reply
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?
Reply
Reply
Reply
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. :-)
Reply
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.
Reply
Reply
Reply
Leave a comment