Not something that's not about hats
Not gonna talk about that! Instead, let's go into unnecessary detail to solve a hat puzzle.
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.
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.
I confess the first time watching this, I skipped to 4:17 as suggested, but that left me confused around 5:33 where he refers to a previously-stated suboptimal solution. I mean, 3/4 of the prisoners? I know a solution that saves all but half of one! That is, the best solution saves n-1 of the n prisoners half the time, and the remaining one the other half of the time. (Turns out he didn't want to spoil the puzzle for people who'd never seen it before.) Keep this quantity in mind.
Then I was confused again when at 7:05, he claimed to have a solution that risks two or three prisoners, and that it depended on whether the remaining prisoners knew who survived. This felt strange because the first puzzle's answer extends to arbitrarily large n, so I had to wonder if the second puzzle's answer extended all the way down. As it turns out, no.
Consider the case of two prisoners in three hats. The solution Matt vaguely refers to would risk both their lives. But there's an easy way to save one prisoner, plus the other half the time. If the back prisoner sees 1, he guesses 3; if he sees 2, he says 1; if he sees 3, he says 2. Then the coded guess uniquely tells the front prisoner what hat she's wearing. (There's a symmetric solution where the back prisoner says the other possibility in all three cases, but I chose this one to set up the next answer.)
Now what of three prisoners wearing four hats? Matt says that without learning who dies, all three are at risk. But since that's not true for two prisoners, I was sure I could save at least 1 1/2 again, or even 2 1/2. I was even more certain when I found the general solution, but at first, all I could do was make a table.
There are 24 possible ways for three of the four hats to be worn, with the mastermind, abbreviated W for "warden," keeping the remainder, thus:
F: 111111222222333333444444
M: 223344113344112244112233
B: 342423341413241412231312
W: 434232434131424121323121The prisoner in the Back has no less than a 50/50 chance of dying, because whichever two hats he sees, he could be wearing one of the two remaining hats. In other words, across these 24 permutations, he only ever sees 12 ordered pairs of hats. But I propose that the group can select 12 of these permutations so that after the Back prisoner makes his constrained guess, the other two will (once it's their turn) know exactly which ordered pair he saw.
For starters, at least if the Front prisoner is wearing 4, the situation reduces to the two-prisoner solution, where the Middle prisoner is now the one guaranteed to survive.
Unassigned Chosen Rejected
F: 111111222222333333 444 444
M: 223344113344112244 123 123
B: 342423341413241412 312 231
W: 434232434131424121 231 312Now suppose the group agrees to a strategy that includes this. If the Front prisoner heard 2 from the Back and 3 from the Middle, she should probably choose 4. But what if she instead hears 3 from the Back and 2 from the Middle? She can't say 4, because that corresponds to the Rejected 4231 permutation. So the only conclusion is that she's wearing 1, which she says. Similar reasoning shows that along with 1234, the prisoners should Choose 2314 and 3124.
Unassigned Chosen Rejected
F: 111122223333 123444 123444
M: 334411442244 231123 231123
B: 242334131412 312312 444231
W: 423243314121 444231 312312And actually, this assignment is almost complete. For suppose the Back prisoner sees the Front one wearing 1 and the Middle one wearing 4. She might be wearing 3, but guessing so would doom the Middle one to guessing 2. Her only option for communication is guessing 2 herself. Similarly, if Front is wearing 1 and Middle is wearing 3, she should guess 4. (Yes, I changed pronouns, but these prisoners are ordered randomly.) That takes care of all cases where 1 is in Front, and perfect analogies finish the 2's and 3's.
Chosen Rejected
F: 111222333444 111222333444
M: 234134124123 234134124123
B: 342413241312 423341412231
W: 423341412231 342413241312
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?
Then I remembered my Galois Theory course.
Oh, right. The alternating group.
Now what is that? Well, first consider an ordered set of n elements, and take as a group all n! ways to permute them in some (not necessarily new) order. The elements in this group can be combined in a way known as "composition," by arranging the elements by one permutation, then by another. (For instance, starting with ABCDE, applying (12)(34) gives BADCE, then applying (2354) gives BCAED. We can say (2354)o(12)(34) = (132)(45). But now I'm just wasting time.)
It's easy to see that we can reach any permutation by swapping some pairs of elements in some order; for instance, getting from ABCDE to BCADE can be done by swapping (23), then (45), then (13). Less obvious is that if the permutation can be done in an even number of swaps, it cannot be done in an odd number of swaps, and vice versa. So we call these permutations "even" and "odd," respectively.
(If you're unconvinced, consider any permutation on n elements. Count the number of disjoint cycles plus the number of fixed points (which could be considered cycles of length 1). Then if you want to be sure you get a number matching the parity of the permutation, subtract this sum from n. This number will always be greater than or equal to zero, but the relevant point is that any swap changes this number by 1; swapping two numbers in the same cycle makes two cycles, and swapping two numbers from two cycles gives a single cycle.)
So to finally answer the question, the alternating group on a set of size n is the set of all even permutations on the set (with the composition operator, but that's not necessary for the solution). If you look again at my answer for three prisoners, you should be able to verify that the Chosen permutations are all even and the Rejected permutations are all odd. My construction even has the parity principle embedded within; every time I swap two hats from a Chosen arrangement, I Reject the new one and immediately swap a different pair to decide which new arrangements to assign as Chosen. And if you're worried that the mastermind won't be entirely random and might pick an odd permutation so as to at least kill one of you, well, he knows he gains nothing. The set of odd permutations is equally good, so you can choose randomly whether you use even permutations or odd permutations.
Then again, if you're not all perfect logicians, or if the mastermind changes his mind, the lot of you are in trouble.
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.
Click to viewBecause 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.
I confess the first time watching this, I skipped to 4:17 as suggested, but that left me confused around 5:33 where he refers to a previously-stated suboptimal solution. I mean, 3/4 of the prisoners? I know a solution that saves all but half of one! That is, the best solution saves n-1 of the n prisoners half the time, and the remaining one the other half of the time. (Turns out he didn't want to spoil the puzzle for people who'd never seen it before.) Keep this quantity in mind.
Then I was confused again when at 7:05, he claimed to have a solution that risks two or three prisoners, and that it depended on whether the remaining prisoners knew who survived. This felt strange because the first puzzle's answer extends to arbitrarily large n, so I had to wonder if the second puzzle's answer extended all the way down. As it turns out, no.
Consider the case of two prisoners in three hats. The solution Matt vaguely refers to would risk both their lives. But there's an easy way to save one prisoner, plus the other half the time. If the back prisoner sees 1, he guesses 3; if he sees 2, he says 1; if he sees 3, he says 2. Then the coded guess uniquely tells the front prisoner what hat she's wearing. (There's a symmetric solution where the back prisoner says the other possibility in all three cases, but I chose this one to set up the next answer.)
Now what of three prisoners wearing four hats? Matt says that without learning who dies, all three are at risk. But since that's not true for two prisoners, I was sure I could save at least 1 1/2 again, or even 2 1/2. I was even more certain when I found the general solution, but at first, all I could do was make a table.
There are 24 possible ways for three of the four hats to be worn, with the mastermind, abbreviated W for "warden," keeping the remainder, thus:
F: 111111222222333333444444
M: 223344113344112244112233
B: 342423341413241412231312
W: 434232434131424121323121The prisoner in the Back has no less than a 50/50 chance of dying, because whichever two hats he sees, he could be wearing one of the two remaining hats. In other words, across these 24 permutations, he only ever sees 12 ordered pairs of hats. But I propose that the group can select 12 of these permutations so that after the Back prisoner makes his constrained guess, the other two will (once it's their turn) know exactly which ordered pair he saw.
For starters, at least if the Front prisoner is wearing 4, the situation reduces to the two-prisoner solution, where the Middle prisoner is now the one guaranteed to survive.
Unassigned Chosen Rejected
F: 111111222222333333 444 444
M: 223344113344112244 123 123
B: 342423341413241412 312 231
W: 434232434131424121 231 312Now suppose the group agrees to a strategy that includes this. If the Front prisoner heard 2 from the Back and 3 from the Middle, she should probably choose 4. But what if she instead hears 3 from the Back and 2 from the Middle? She can't say 4, because that corresponds to the Rejected 4231 permutation. So the only conclusion is that she's wearing 1, which she says. Similar reasoning shows that along with 1234, the prisoners should Choose 2314 and 3124.
Unassigned Chosen Rejected
F: 111122223333 123444 123444
M: 334411442244 231123 231123
B: 242334131412 312312 444231
W: 423243314121 444231 312312And actually, this assignment is almost complete. For suppose the Back prisoner sees the Front one wearing 1 and the Middle one wearing 4. She might be wearing 3, but guessing so would doom the Middle one to guessing 2. Her only option for communication is guessing 2 herself. Similarly, if Front is wearing 1 and Middle is wearing 3, she should guess 4. (Yes, I changed pronouns, but these prisoners are ordered randomly.) That takes care of all cases where 1 is in Front, and perfect analogies finish the 2's and 3's.
Chosen Rejected
F: 111222333444 111222333444
M: 234134124123 234134124123
B: 342413241312 423341412231
W: 423341412231 342413241312
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?
Then I remembered my Galois Theory course.
Oh, right. The alternating group.
Now what is that? Well, first consider an ordered set of n elements, and take as a group all n! ways to permute them in some (not necessarily new) order. The elements in this group can be combined in a way known as "composition," by arranging the elements by one permutation, then by another. (For instance, starting with ABCDE, applying (12)(34) gives BADCE, then applying (2354) gives BCAED. We can say (2354)o(12)(34) = (132)(45). But now I'm just wasting time.)
It's easy to see that we can reach any permutation by swapping some pairs of elements in some order; for instance, getting from ABCDE to BCADE can be done by swapping (23), then (45), then (13). Less obvious is that if the permutation can be done in an even number of swaps, it cannot be done in an odd number of swaps, and vice versa. So we call these permutations "even" and "odd," respectively.
(If you're unconvinced, consider any permutation on n elements. Count the number of disjoint cycles plus the number of fixed points (which could be considered cycles of length 1). Then if you want to be sure you get a number matching the parity of the permutation, subtract this sum from n. This number will always be greater than or equal to zero, but the relevant point is that any swap changes this number by 1; swapping two numbers in the same cycle makes two cycles, and swapping two numbers from two cycles gives a single cycle.)
So to finally answer the question, the alternating group on a set of size n is the set of all even permutations on the set (with the composition operator, but that's not necessary for the solution). If you look again at my answer for three prisoners, you should be able to verify that the Chosen permutations are all even and the Rejected permutations are all odd. My construction even has the parity principle embedded within; every time I swap two hats from a Chosen arrangement, I Reject the new one and immediately swap a different pair to decide which new arrangements to assign as Chosen. And if you're worried that the mastermind won't be entirely random and might pick an odd permutation so as to at least kill one of you, well, he knows he gains nothing. The set of odd permutations is equally good, so you can choose randomly whether you use even permutations or odd permutations.
Then again, if you're not all perfect logicians, or if the mastermind changes his mind, the lot of you are in trouble.