Kittens For All

OK, time to solve the hat problem from last time. So, first it is easiest to solve the two person, two hat colours case. When we have two people with only black or white hats, the solution is as follows:
Person 1: guess the hat colour you can see on person 2

Person 2: guess the hat colour opposite to the one you can see on person 1

More simply, person 1 assumes both hat colours are the same, person 2 assumes they are different, one of them will be correct.

Its also interesting to note that either individual has a 50% chance to be right (this is trivial since hat colours are independent), but there is no way both will be right. Thus, let event A be "person 1 is right", event B be "person 2 is right", so P(A)=1/2=P(B), and the probability that at least one of them is right is given by
P(A or B) = P(A) + P(B) - P(A and B) = 1 - P(A and B)

So we see that by minimizing P(A and B) to zero, we guarantee that one of them will be right.

This idea generalizes, in the seven person case, it is sufficient and necessary to find a solution that no two people can ever be correct at the same time, and you guarantee that one of them will be correct.

I will show the full solution using modular arithmetic. All math in the following solution will be done mod 7:
Number the hat colours 0 through 6, and number the people 0 through 6. There exists a number S which is the sum of everybodys hat colour (but none of the players have enough information to fully calculate S). Person n is to assume that the value of S is n, this gives them only one choice of hat colour to guess.

Each person assumes that the sum of the hats is a different number mod 7, and one of them will be right, also never will two of them be right.

This idea of making sure that no two people are right at the same time, so that you don't waste any extra "rightness" has uses in other logic problems, I'll probably point it out when it comes up or something.

No comments: