## November 14th, 2016

Back in March, I saw a video featuring two puzzles about prisoners wearing hats. I subscribed to Matt Parker's channel either shortly before or shortly after; I don't remember which. Anyway, here's a series of LiveJournal cuts.

**( Here's the video!Collapse )**

Because he already gave a non-bumbling explanation, so I shouldn't have to go through all that work. Also, I will be referring to this video, so even if I'd summarized the puzzle, this is required viewing.

**( Here's my immediate thought, and a grinding derivation of the solution for 3 prisoners in 4 hats!Collapse )**

But I admit I didn't actually write down this table, or construct it in my head. Not sure if that makes my hitting upon the general solution more or less impressive, but there you go.

Without writing anything down, I felt stuck. How could I code twelve possible ordered pairs (much less 60 triples, 360 quadruples, or more longer permutations) into one binary guess? And I knew it had to be binary, because not only would guessing anything other than a possible hat 100% doom the Back prisoner, the rule of not repeating a guess would doom whoever was really wearing that hat.

Of course, the puzzle never said the guess had to be in the range of possible hats. One commenter suggested that the Back prisoner add up all 999 numbers of the other prisoners, and this would absolutely save 999.0 prisoners. But I remained certain that with the right approach, I could save 999.5. If no one gave an answer they knew was impossible, then everyone would have two possible hats when it was their turn, and one hat would always be their real hat. Just, how could I choose permutations that were sensitive to every slight rearrangement, communicated that sensitivity only by alternating the Back prisoner between two equally risky guesses, and could be extended to any arbitrary group of prisoners?

**( And the answer!Collapse )**

Then again, if you're not all perfect logicians, or if the mastermind changes his mind, the lot of you are in trouble.

- Current Mood: exhausted
- Current Music:The Stand-up Maths theme