Log in

No account? Create an account

Previous Entry Share Next Entry
Colored Hat Puzzle - Last Call
Bar Harbor
No one has yet messaged me with a correct answer to the Colored Hat Puzzle, so here's Hint #3.

[Spoiler (click to open)]Although it's easier to solve this for 2 prisoners/colors than for 10, solving for 10 is actually easier than solving for 9.

I'll probably post the answer early next week.

  • 1
I have more hints if anyone wants.

[delete huge post providing proof that it is impossible, because I discovered the answer when writing up the truth table]

Okay, now to figure out how to expand it to more than 2 prisoners.

How much time do the prisoners get to develop their strategy? I got the answer for N=2, tried N=3 and quickly hit a dead end, and now am trying N=4.

So far:[Spoiler (click to open)]1 goes free if all hats are different, 2 goes free if 1&2 are same and others different, 3 goes free if 1&3 are same and others different, 4 goes free if 1&4 are same and others different. I also found a way for 1 to go free half the time when 2&3 are same and others different, but can't think of how to make 4 go free the other half of the time.

Any hints on how to simplify things by combining cases? And is it necessary to number the colors, or am I missing something easier?

Edited at 2013-01-13 06:53 pm (UTC)

I'll semi-arbitrarily say that the prisoners have 3 hours to strategize.

[Spoiler (click to open)]Numbering the colors is one route to combining cases to simplify. It isn't *strictly* necessary to do so, but for N=10, I can't think of any other way that doesn't require that the prisoners effectively all have eidetic memory. (or they make huge complex cheat-sheets, which probably take more than 3 hours to prepare.)

After spending hours and hours making insanely complicated rules for each prisoner (based on how many duplicate colors they see and where they see them), I think I've finally found the correct answer (but my brain is too fried to properly test it).

[Spoiler (click to open)]Number the prisoners 0 to N-1, and number the colors 0 to N-1. Each prisoner calculates what color his hat needs to be in order that the sum of all hats (including his own) modulo N equals his prisoner number.

I may have had an easier time reaching this point if you hadn't given me hint #3 (I wouldn't have been so willing to give up on N=3).

  • 1