Interesting Stuff

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

Steamboat Steven gave me this gem. Unlike my previous discussion of a hat problem, this one can be solved in a reasonably short amount of time.

There are n people on a staircase facing downstairs when a hat is placed on each person’s head. There are c different hat colors, and each hat has a 1/c chance of being each color (that is to say, the color of each hat is independent; some of the c colors might not be used anywhere, while others may be very common). Each person can see the color of every hat downstairs from her, but not the color of her own hat or any hat upstairs. Starting at the top of the stairs and working down to the bottom, each person guesses the color of her own hat. Each person can hear all previous guesses.

The group as a whole gets 1 point for every correct guess, and nothing for incorrect guesses. If the group is allowed to discuss and to agree upon a strategy ahead of time, how many correct guesses can they guarantee?

One naïve strategy would be to have people 1, 3, 5, &c simply say the color of the hat in front of them, and have people 2, 4, 6, &c repeat that color, guaranteeing n/2 correct guesses. It turns out you can do a lot better. How?

I think that I’m going to give up trying to solve the Hat Problem, though I’ve come pretty far (for background, see my original description and its follow-up post). I’ve now solved the N=5 version (with surprising results!), and gotten a pretty good framework around the problem: My final analysis of the Hat Problem, including a reduction to the Minimum Dominating Set problem, source code for a better program to search for solutions, and an optimal strategy for N=5 →

Yesterday, I wrote about the Hat Problem. I figured out some more late last night, but haven’t had a chance to post until now. I cancelled my brute-force program because I figured out the solution to the 4-person version: have 1 person pass all the time, and have the other 3 people pretend it’s the 3-person problem. I know this because I got an upper bound on the best strategy: with N people, you can never do better than winning N out of N+1 times (so the solutions based on Hamming codes are always optimal). If you add up all the non-pass responses over all possible hat configurations, you need an equal number of correct and incorrect answers (otherwise, the chances that your own hat is red are not independent of the colors of everyone else’s hat, and probability is broken). The best you can bunch up the wrong answers is to have everyone guess wrong at the same time, and the best you can spread out the right answers is to have each right answer in its own hat configuration. So, for every time the group loses, you can have at most N wins, and the best chances you can ever get are N in N+1.

How does this help in the N=4 situation? We now know that best you can do is win 80% of the time. Moreover, there are 16 distinct hat configurations. Winning 13 of them would be more than 80%, so we must win fewer than that many. However, we can win 12 of them by reducing ourselves to the N=3 version, so we know that’s the optimal solution. For N=5, there are 32 distinct hat combinations, and the optimal strategy will win at least 24 and at most 26 of them (but I don’t know the exact answer). For N=6, the optimal strategy will win at least 48 and at most 54 of the 64 possible configurations. The brute-force method won’t finish within our lifetimes for N>4, so I can’t try that again. Any other ideas on how to progress? FWIW, I’ve found a second way to get 75% success when N=6.

(Edit: see part 3 for more on the problem)

I recently learned about The Hat Puzzle, which is a surprisingly tough little conundrum that goes like this:

N people walk into a room and a hat is placed on each person’s head. Each hat is either red or blue, and the chances that any given hat is red are 1 in 2. Each person can see the colours of everyone else’s hat, but not the colour of their own. While in the room with the hats, no one is allowed to communicate with each other in any way at all. Everyone is then lead into separate rooms, and asked the colour of his or her own hat. Each person can choose to answer or to pass. If at least one person answers correctly and no one answers incorrectly, the whole group wins. How do you maximize your chances of winning?

The naive solution (before entering the room, pick one person who will guess Red and have everyone else pass; chances of winning are 50%) seems easy enough, but there are more complicated solutions that do better. For instance, with 3 people, you can win 75% of the time: if your comrades have the same colour hat on, guess the other colour. If they have different colour hats, pass. The only time you lose is when everyone has the same colour hat. Note that a person who chooses to guess the colour of their hat is still wrong half the time (i.e. probability isn’t broken), but we’ve spread out the occurrences of correct answers and bunched all the wrong answers on top of each other. Apparently you can use Hamming Codes to win with odds N out of N+1 when N is 1 less than a power of 2, but I haven’t seen an explanation of how that works yet.

Apparently, this is an unsolved problem for all other N, though. I have written a Java program to use a brute force method to find the solutions, and it easily verified that the best you can do when N=3 is 75% (using the strategy described above). The problem with this brute force solution is that its running time is O(2^n * 3^(n*2^n)), which makes it rather unwieldy. I’ve started running the program to solve the N=4 case, and I hope it will finish by tomorrow afternoon. edit: I dramastically misunderestimated the time needed to run this program. It will hopefully be done by Thursday. I will not use it to find the solution for N=5.

As usual for subtle and tricky topics, the Wikipedia page is wrong in subtle and tricky ways (at least, it was when I wrote this), so don’t bother looking for more information there.

(Edit: I continue working on this in part 2)