Why is a raven like a writing-desk? Final Part

May 23, 2007 22:32

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 )

puzzles, mathematics, hat puzzle, math, np-complete, hat, hat problem, dominating set

Leave a comment

Comments 2

dhalps May 24 2007, 07:24:06 UTC
It's not clear to me that you can do things like "have someone guess if everyone passes". What if there's exactly one configuration where everyone passes. Then flipping any hat implies someone would guess, and therefore no one can tell that we're in a configuration where everyone passes.

Reply

big_bad_al May 24 2007, 08:12:54 UTC
Suppose that we have a strategy containing a hat configuration where everyone passes, and suppose without loss of generality that in this configuration, person X has a blue hat. If person X observes everyone else's hats to be consistent with this all-pass configuration, the group loses nothing when person X guesses his hat is red. If his hat was blue, they were going to lose anyway. If his hat is red, he guessed right and cannot hurt the team's performance. In this latter case, it is possible that someone else will also guess correctly and that our correct guesses are bunching up on top of each other. But person X will never hurt the team by guessing that they're not in a losing configuration.

Reply


Leave a comment

Up