Hacker News new | ask | show | jobs
by mschireson 5253 days ago
Very good! Now how about the hard version?
1 comments

It's trivially at least 50%, and I can't see how it can get above that.

This problem can be represented mathematically as a function f: X->Y, where:

X = {-1,1}^16 represents the set of hats the Mathematicians are actually wearing. Say -1 is a white hat and 1 is a black hat.

Y = {-1,0,1}^16 represents the guesses made by the Mathematicians, where -1 is a white hat, 1 is a black hat, and 0 is an "I don't know."

We can also write f(x_0,x_1,...,x_15) -> (y_0,y_1,...,y_15) . Then for the fixed set f(a_0,...,a_15) = (b_0,...,b_15), the function f is a correct guess if and only if

1. For all k, b_k = 0 or a_k .

2. For at least one k, b_k != 0.

Assume f(a_0,...,a_15) = (b_0,...,b_15) is a correct guess. There must be some b_k != 0 where b_k = a_k, so we can assume WLOG that b_0 = 1 = a_0. Now note that if f(1,a_1,...,a_15) = (b_0,b_1,...,b_15) and f(-1,a_1,...,a_15) = (c_0,c_1,...,c_15), then b_0 = c_0 . This is because mathematician 0 must make his guess based only on the colors of the other mathematicians' hats. Thus f(-1,a_1,...,a_15) is an incorrect guess.

Thus for every set (x_0,...,x_15) where f is a correct guess, we can come up with at least one set where f is an incorrect guess. Thus f cannot be correct more than 50% of the time.

...so, what am I missing?

yes, each mathematician guesses incorrectly as often as they guess correctly. but that is not the same as saying that there is a 50% chance the group "wins" on any given round. remember with the possibility of passing the number of guesses on a round need not be uniform...

Hope that helps get you on the right track,

-- Max (the original poster)