Solutions and discussion of yesterday's logic puzzles
This post is for discussion and solutions to the hard logic puzzles in my previous post. I recommend reading that one first, especially if you want to think about the puzzles without spoilers.
1. The 100 prisoners and boxes puzzle
The naive strategy of everyone opening 50 boxes at random gives success odds of only 0.5^100, which is about 1 in 10^30. It's possible to do much better.
I got nowhere with this by myself (in 2006) and had to be told the answer.
The strategy is that the prisoners number themselves 1 to 100, and each prisoner starts by opening the nth box, where n is his own number. If he finds his own name, he's succeeded; otherwise, he opens the mth box, where m is the number of the prisoner whose name he just found, and so on, until he's either found his own name and hence succeeded, or opened 50 boxes without finding his own name and hence failed.
The reason this works is because the permutation of 100 names into 100 boxes forms one or more cycles. An example of a cycle would be (1 42 69 5), which means that box 1 contains the name of prisoner 42, box 42 contains the name of 69, box 69 contains the name of 5, and box 5 contains the name of 1. If this is the case, then prisoners 1, 42, 69 and 5 will each find their own names in 4 moves using the above strategy.
It is possible for the random permutation of all 100 boxes to form one single long cycle of length 100, but the odds of this are actually quite low (about 0.01); it's more likely that there will be lots of cycles of different sizes (possibly including one or more cycles of length 1, where someone's name is in their own box).
The strategy succeeds if all cycles are no longer than 50. If any one cycle (and it could only be one cycle) is longer than 50, it fails. But that turns out to give success odds of about 30%, which feels like a realistic chance and is vastly better than the random approach.
(In the comments on yesterday's post, simont suggests an interesting variant, where the prisoners have an accomplice who can go into the room beforehand and switch the contents of two boxes. This allows them to guarantee success.)
2. The chessboard puzzle
This seems impossible because there seems to be no way to convey any information: your associate doesn't know what the board looked like before, so they just see an apparently random distribution, so you can't communicate anything by the difference between the old and new board states.
If you only needed a probabilistic solution, you could agree to set up something along the lines of "the longest line of consecutive heads points to the target location", but that would only work in a small number of cases.
I did get as far as "the board state is a 64-bit number, so you can use it to convey some information" by myself, but I didn't quite get all the way there.
The actual solution is that if you number all the squares and XOR together all the numbers whose squares contain a head, you get a number (call it X), and you can add or remove one head in order to change this to be the number corresponding to the square you want to indicate.
(If this isn't apparent: every square has a unique binary representation, so you can get from the current value of X to the one you want by flipping some subset of bits, so you can do that in a single step by flipping the coin whose number consists of those bits you want to flip. For example, if X is currently 30 (16 + 8 + 4 + 2) and you want to make it 42 (32 + 8 + 2) you need to flip 4, 16, and 32 (and leave 8 and 2 unchanged), so you flip the coin at position 4 + 16 + 32 = 52.)
3. The yellow hats puzzle
The OP gave a hint "Trying to turn the "you can't do better than 50%" intuition into a formal proof, and seeing where it fails, might give you an insight into how to do so?"
I found this hint quite helpful: my initial reasoning was that if one person guesses randomly and everyone else shuts up, the odds of success are 50%, and so if any additional people also guess, that will only multiply the probability by something <=1 and make it smaller. I was taking it for granted that the success probabilities of everyone's guesses were independent, but trying to formalise this made me realise that assumption was wrong. Although B can't actually take A's guess into account when making their guess, A and B do have some shared information, in the form of the other 29 hats that they can both see, and they can decide in advance to make both their guesses some function of those, which "entangles" their guesses and makes them not independent. (That's about as far as I got before looking at spoilers.)
The strategy is to designate, in advance, some potential hat distributions as "good" and some as "bad", where a distribution can be changed from bad to good by altering one hat. Then if you as an individual look around at the other hats and see that the distribution is definitely good regardless of your own hat colour, or definitely bad regardless of your hat colour, you keep quiet; but if your own hat would make the difference between a good and a bad distribution, then you assume it's a good distribution and call accordingly. Then, if it's actually a bad distribution, your team loses anyway, but if it's actually a good distribution, then you've correctly guessed your hat colour, and everyone else has either kept quiet or correctly guessed their own, so your team wins.
So the odds of success come down to how you divide up the possibility space into good and bad distributions. One commenter suggested designating good distributions as those where the number of buttercup hats is not a multiple of 3. This is not the optimal solution, but it's relatively easy to understand (and working through it helped me understand the general principle better), and it gives better odds than the naive 50%.
So if you as an individual see a multiple of 3 buttercup hats, then either there really is a multiple of 3, in which case the team loses whatever you do; or you yourself have the (3n+1)th buttercup hat, in which case you call "buttercup" and are correct, and all the other buttercup hat wearers do likewise (because they also see 3n buttercup hats and hope they themselves are the (3n+1)th), and all the cadmium hat wearers keep quiet (because they see 3n+1 buttercup hats, which they know to be a good distribution regardless of whether they themselves are the (3n+2)th buttercup hat or not).
If you see 3n+1 buttercup hats, you keep quiet, because regardless of your own hat colour the overall distribution will not be a multiple of 3; and if you see 3n+2, you call "cadmium" (because either it really is 3n+2 and you're cadmium, or you're buttercup and it's actually a multiple of 3 and you've already failed).
With this strategy, assuming the hats are initially chosen randomly, your team's odds of success are 2/3, because you'll fail if and only if there are a multiple of 3 buttercup hats.
The actual optimal solution (according to the OP; IDK how to prove it's optimal) involves Hamming codes - which I hadn't come across before (although I knew of Hamming distance), so apologies if there are inaccuracies in my explanation of them. They're binary numbers containing extra bits used for redundancy and error correction, a bit like the checksum digit in a bar code. They are always 2^n - 1 bits long for some n, which means it wasn't a coincidence that the puzzle involves "you and your thirty friends" (I had initially thought it was a sloppy way of saying there were 30 people in total, and that the difference between it being 30 versus 31 didn't matter).
AIUI, they work by using all the (2^n)th bits as error-correcting bits, and setting those such that the index-XOR (XOR of all the bit positions with a 1 in them) of the whole number is 0. This means that any single-bit-flip error can be detected and corrected (because you know which data bit was wrong and can then flip it).
So a 31-bit Hamming code will contain 26 data bits and 5 error-correcting bits (at positions 1, 2, 4, 8 and 16), each of which checks more than one data bit in an overlapping way, and only a small proportion of all 31-bit numbers are valid Hamming codes for any 26-bit numbers (because there's only one way to get a given 26-bit number right and lots of ways to get a 1-bit deviation from it). So you invert this imbalance and designate that small proportion of valid codes as "bad" hat distributions, each of which is one hat-change away from a "good" hat distribution (because you can clearly change a valid Hamming code into an invalid one by flipping one bit and introducing one error).
So, of the 2^31 possible hat distributions, 2^26 are valid Hamming codes corresponding to the 2^26 possible 26-bit numbers (i.e. "bad" distributions) and the rest are "good" distributions, so your odds of failure are only 2^26/2^31, or 1 in 32.
In terms of practical execution, the players number themselves in advance, and then they each look around and calculate the index-XOR of the numbers of the people wearing (say) buttercup hats, once including themselves and once not including themselves. If neither result is 0, they keep quiet; if one result is 0, they guess their own hat colour according to the non-zero result.
4. The red/green/blue hats puzzle
I haven't actually solved this yet (or peeked at a solution), but I feel like I've got quite close, and I thought the discussion of my progress so far could be interesting. (Alex knows the solution, so it does exist.)
I briefly considered the easier case where there are only 2 people and only 2 possible hat colours. That version could seem impossible, because there are 4 possible states (RR, RG, GR, GG) and you only get two guesses between you. But I figured out fairly easily that there are, in a sense, only two possible states: "same" and "different". So you can cover those cases by having person A guess the colour they see B wearing, and person B guess the colour they don't see A wearing; then in the "same" case A succeeds and in the "different" case B succeeds. However, I don't know how to generalise this to the 5-person 3-colour case.
Calling the people in the 3-row A, B, and C, and the people in the 2-row P and Q, and the "order" of the colours R->G->B:
If A names the colour that follows P's colour, and P names the colour that follows A's colour, then one of them will succeed as long as they're not wearing the same colour (because you've covered the case where P's colour is the one following A and the case where P's colour is the one preceding A, so the only case left is where P's colour is the same as A). This means you've already succeeded in 2/3 of cases.
(Interestingly, this means you can effectively "assume" A and P are wearing the same colour (because the other possibilities are already covered), which means that if B and C want to know A's colour they can look at P and assume it's that (and similarly Q can look at A and infer P). However, I didn't actually use this in subsequent parts of my approach.)
I also worked out B and C could both name Q's colour, and Q could look at B and C, and if they're equal guess that colour and if they're different guess the third colour. This works if B and/or C match Q (because then B and/or C will guess correctly), and it also works if B doesn't match C (because we can assume neither B nor C matches Q, because we already covered that case, so Q must be the third colour that doesn't match B or C). It only fails if B matches C AND Q doesn't match B AND Q doesn't match C. I think that means it fails 1/3 * 2/3 * 2/3 = 4/27 of the time, which, combined with the 2/3 success from A and P's strategy above, gives overall success odds of 77/81. Which is pretty good, but sadly this wasn't a probabilistic puzzle and we needed a guaranteed strategy.
Because we've already covered all the possibilities where B and C don't match, we can "assume" B and C do match, and then treat B and C as a single player with a single hat colour. But I'm not sure exactly where to go with that.
Alternatively, I came up with a more symmetrical-looking diagram where A and C, the outermost players on the longer row, name the colours of P and Q respectively, and the other three players each look at the two players opposite them (e.g. P looks at A and B) and if they match, name that colour, and if they don't, name the third colour. (Or, instead, A and C could each do the same-if-same, third-colour-if-different thing with P and Q, making it even more symmetrical.) It feels like that could work out to cover all cases - there are only three possible colours, so if you can reduce it to a situation where you "know" (by having already covered the alternatives) that A is different from both P and Q, and Q is different from both B and C, and so on, then there aren't enough colours for all of them to be different from each other, so some of them must coincide - but I don't think I have the mental stack space to work it through and prove it.
My final idea is to note that there must be a reason there are 5 players rather than 3, and it's likely that it's possible with 5 but impossible with 3, and maybe that's because the extra two players can be used as error-checking trits somehow, like the error-checking bits in the yellow-hats puzzle, but again I haven't quite worked it through. (Although simont says he has a solution that works with 4 players in 2 rows of 2, so maybe the 5th player is actually unnecessary...)
Overall comments
These puzzles all feel very similar: in all cases the solution seems impossible, not in a "narrow miss" way but in a "nowhere near possible" kind of way. The solutions to 3 and 4 are even fairly similar to each other: more so than you'd expect from the difference in their setups. They both basically involve index-XOR-ing everything. This makes me want to look into other applications of index-XOR, and also makes me wonder if the solution to the RGB hats puzzle (which I haven't quite solved yet) also involves it somehow.
I feel like there should be some practical application here - some similar real-world situation where it looks at first and second glance like there's zero information that can be conveyed, but where a clever strategy means that actually it can, and the discrepancy between the apparent security and the actual information leak can be exploited.
I don't necessarily mean "exploited" in an immoral way: it could be an attack against economic deadweight loss, or against Moloch (Scott Alexander's term for tragedy-of-the-commons type situations where the sum of everyone's actions leads to a situation nobody wants but no individual can break the deadlock), or against entropy (in the sense of general chaos and decay, not in the information-theory-specific sense, confusingly), rather than against other people. Finding information leaks in apparently secure contexts sounds like the domain of fraudsters and hackers, but it could also be applied to things like reconstructing fragmentary ancient texts or recovering corrupted recordings that seem to be lost, or providing market information that was thought to be unknowable but which is useful to both buyers and sellers - or, of course, white-hat hacking, finding potential exploits for fraudsters and hackers and closing them.
1. The 100 prisoners and boxes puzzle
The naive strategy of everyone opening 50 boxes at random gives success odds of only 0.5^100, which is about 1 in 10^30. It's possible to do much better.
I got nowhere with this by myself (in 2006) and had to be told the answer.
The strategy is that the prisoners number themselves 1 to 100, and each prisoner starts by opening the nth box, where n is his own number. If he finds his own name, he's succeeded; otherwise, he opens the mth box, where m is the number of the prisoner whose name he just found, and so on, until he's either found his own name and hence succeeded, or opened 50 boxes without finding his own name and hence failed.
The reason this works is because the permutation of 100 names into 100 boxes forms one or more cycles. An example of a cycle would be (1 42 69 5), which means that box 1 contains the name of prisoner 42, box 42 contains the name of 69, box 69 contains the name of 5, and box 5 contains the name of 1. If this is the case, then prisoners 1, 42, 69 and 5 will each find their own names in 4 moves using the above strategy.
It is possible for the random permutation of all 100 boxes to form one single long cycle of length 100, but the odds of this are actually quite low (about 0.01); it's more likely that there will be lots of cycles of different sizes (possibly including one or more cycles of length 1, where someone's name is in their own box).
The strategy succeeds if all cycles are no longer than 50. If any one cycle (and it could only be one cycle) is longer than 50, it fails. But that turns out to give success odds of about 30%, which feels like a realistic chance and is vastly better than the random approach.
(In the comments on yesterday's post, simont suggests an interesting variant, where the prisoners have an accomplice who can go into the room beforehand and switch the contents of two boxes. This allows them to guarantee success.)
2. The chessboard puzzle
This seems impossible because there seems to be no way to convey any information: your associate doesn't know what the board looked like before, so they just see an apparently random distribution, so you can't communicate anything by the difference between the old and new board states.
If you only needed a probabilistic solution, you could agree to set up something along the lines of "the longest line of consecutive heads points to the target location", but that would only work in a small number of cases.
I did get as far as "the board state is a 64-bit number, so you can use it to convey some information" by myself, but I didn't quite get all the way there.
The actual solution is that if you number all the squares and XOR together all the numbers whose squares contain a head, you get a number (call it X), and you can add or remove one head in order to change this to be the number corresponding to the square you want to indicate.
(If this isn't apparent: every square has a unique binary representation, so you can get from the current value of X to the one you want by flipping some subset of bits, so you can do that in a single step by flipping the coin whose number consists of those bits you want to flip. For example, if X is currently 30 (16 + 8 + 4 + 2) and you want to make it 42 (32 + 8 + 2) you need to flip 4, 16, and 32 (and leave 8 and 2 unchanged), so you flip the coin at position 4 + 16 + 32 = 52.)
3. The yellow hats puzzle
The OP gave a hint "Trying to turn the "you can't do better than 50%" intuition into a formal proof, and seeing where it fails, might give you an insight into how to do so?"
I found this hint quite helpful: my initial reasoning was that if one person guesses randomly and everyone else shuts up, the odds of success are 50%, and so if any additional people also guess, that will only multiply the probability by something <=1 and make it smaller. I was taking it for granted that the success probabilities of everyone's guesses were independent, but trying to formalise this made me realise that assumption was wrong. Although B can't actually take A's guess into account when making their guess, A and B do have some shared information, in the form of the other 29 hats that they can both see, and they can decide in advance to make both their guesses some function of those, which "entangles" their guesses and makes them not independent. (That's about as far as I got before looking at spoilers.)
The strategy is to designate, in advance, some potential hat distributions as "good" and some as "bad", where a distribution can be changed from bad to good by altering one hat. Then if you as an individual look around at the other hats and see that the distribution is definitely good regardless of your own hat colour, or definitely bad regardless of your hat colour, you keep quiet; but if your own hat would make the difference between a good and a bad distribution, then you assume it's a good distribution and call accordingly. Then, if it's actually a bad distribution, your team loses anyway, but if it's actually a good distribution, then you've correctly guessed your hat colour, and everyone else has either kept quiet or correctly guessed their own, so your team wins.
So the odds of success come down to how you divide up the possibility space into good and bad distributions. One commenter suggested designating good distributions as those where the number of buttercup hats is not a multiple of 3. This is not the optimal solution, but it's relatively easy to understand (and working through it helped me understand the general principle better), and it gives better odds than the naive 50%.
So if you as an individual see a multiple of 3 buttercup hats, then either there really is a multiple of 3, in which case the team loses whatever you do; or you yourself have the (3n+1)th buttercup hat, in which case you call "buttercup" and are correct, and all the other buttercup hat wearers do likewise (because they also see 3n buttercup hats and hope they themselves are the (3n+1)th), and all the cadmium hat wearers keep quiet (because they see 3n+1 buttercup hats, which they know to be a good distribution regardless of whether they themselves are the (3n+2)th buttercup hat or not).
If you see 3n+1 buttercup hats, you keep quiet, because regardless of your own hat colour the overall distribution will not be a multiple of 3; and if you see 3n+2, you call "cadmium" (because either it really is 3n+2 and you're cadmium, or you're buttercup and it's actually a multiple of 3 and you've already failed).
With this strategy, assuming the hats are initially chosen randomly, your team's odds of success are 2/3, because you'll fail if and only if there are a multiple of 3 buttercup hats.
The actual optimal solution (according to the OP; IDK how to prove it's optimal) involves Hamming codes - which I hadn't come across before (although I knew of Hamming distance), so apologies if there are inaccuracies in my explanation of them. They're binary numbers containing extra bits used for redundancy and error correction, a bit like the checksum digit in a bar code. They are always 2^n - 1 bits long for some n, which means it wasn't a coincidence that the puzzle involves "you and your thirty friends" (I had initially thought it was a sloppy way of saying there were 30 people in total, and that the difference between it being 30 versus 31 didn't matter).
AIUI, they work by using all the (2^n)th bits as error-correcting bits, and setting those such that the index-XOR (XOR of all the bit positions with a 1 in them) of the whole number is 0. This means that any single-bit-flip error can be detected and corrected (because you know which data bit was wrong and can then flip it).
So a 31-bit Hamming code will contain 26 data bits and 5 error-correcting bits (at positions 1, 2, 4, 8 and 16), each of which checks more than one data bit in an overlapping way, and only a small proportion of all 31-bit numbers are valid Hamming codes for any 26-bit numbers (because there's only one way to get a given 26-bit number right and lots of ways to get a 1-bit deviation from it). So you invert this imbalance and designate that small proportion of valid codes as "bad" hat distributions, each of which is one hat-change away from a "good" hat distribution (because you can clearly change a valid Hamming code into an invalid one by flipping one bit and introducing one error).
So, of the 2^31 possible hat distributions, 2^26 are valid Hamming codes corresponding to the 2^26 possible 26-bit numbers (i.e. "bad" distributions) and the rest are "good" distributions, so your odds of failure are only 2^26/2^31, or 1 in 32.
In terms of practical execution, the players number themselves in advance, and then they each look around and calculate the index-XOR of the numbers of the people wearing (say) buttercup hats, once including themselves and once not including themselves. If neither result is 0, they keep quiet; if one result is 0, they guess their own hat colour according to the non-zero result.
4. The red/green/blue hats puzzle
I haven't actually solved this yet (or peeked at a solution), but I feel like I've got quite close, and I thought the discussion of my progress so far could be interesting. (Alex knows the solution, so it does exist.)
I briefly considered the easier case where there are only 2 people and only 2 possible hat colours. That version could seem impossible, because there are 4 possible states (RR, RG, GR, GG) and you only get two guesses between you. But I figured out fairly easily that there are, in a sense, only two possible states: "same" and "different". So you can cover those cases by having person A guess the colour they see B wearing, and person B guess the colour they don't see A wearing; then in the "same" case A succeeds and in the "different" case B succeeds. However, I don't know how to generalise this to the 5-person 3-colour case.
Calling the people in the 3-row A, B, and C, and the people in the 2-row P and Q, and the "order" of the colours R->G->B:
If A names the colour that follows P's colour, and P names the colour that follows A's colour, then one of them will succeed as long as they're not wearing the same colour (because you've covered the case where P's colour is the one following A and the case where P's colour is the one preceding A, so the only case left is where P's colour is the same as A). This means you've already succeeded in 2/3 of cases.
(Interestingly, this means you can effectively "assume" A and P are wearing the same colour (because the other possibilities are already covered), which means that if B and C want to know A's colour they can look at P and assume it's that (and similarly Q can look at A and infer P). However, I didn't actually use this in subsequent parts of my approach.)
I also worked out B and C could both name Q's colour, and Q could look at B and C, and if they're equal guess that colour and if they're different guess the third colour. This works if B and/or C match Q (because then B and/or C will guess correctly), and it also works if B doesn't match C (because we can assume neither B nor C matches Q, because we already covered that case, so Q must be the third colour that doesn't match B or C). It only fails if B matches C AND Q doesn't match B AND Q doesn't match C. I think that means it fails 1/3 * 2/3 * 2/3 = 4/27 of the time, which, combined with the 2/3 success from A and P's strategy above, gives overall success odds of 77/81. Which is pretty good, but sadly this wasn't a probabilistic puzzle and we needed a guaranteed strategy.
Because we've already covered all the possibilities where B and C don't match, we can "assume" B and C do match, and then treat B and C as a single player with a single hat colour. But I'm not sure exactly where to go with that.
Alternatively, I came up with a more symmetrical-looking diagram where A and C, the outermost players on the longer row, name the colours of P and Q respectively, and the other three players each look at the two players opposite them (e.g. P looks at A and B) and if they match, name that colour, and if they don't, name the third colour. (Or, instead, A and C could each do the same-if-same, third-colour-if-different thing with P and Q, making it even more symmetrical.) It feels like that could work out to cover all cases - there are only three possible colours, so if you can reduce it to a situation where you "know" (by having already covered the alternatives) that A is different from both P and Q, and Q is different from both B and C, and so on, then there aren't enough colours for all of them to be different from each other, so some of them must coincide - but I don't think I have the mental stack space to work it through and prove it.
My final idea is to note that there must be a reason there are 5 players rather than 3, and it's likely that it's possible with 5 but impossible with 3, and maybe that's because the extra two players can be used as error-checking trits somehow, like the error-checking bits in the yellow-hats puzzle, but again I haven't quite worked it through. (Although simont says he has a solution that works with 4 players in 2 rows of 2, so maybe the 5th player is actually unnecessary...)
Overall comments
These puzzles all feel very similar: in all cases the solution seems impossible, not in a "narrow miss" way but in a "nowhere near possible" kind of way. The solutions to 3 and 4 are even fairly similar to each other: more so than you'd expect from the difference in their setups. They both basically involve index-XOR-ing everything. This makes me want to look into other applications of index-XOR, and also makes me wonder if the solution to the RGB hats puzzle (which I haven't quite solved yet) also involves it somehow.
I feel like there should be some practical application here - some similar real-world situation where it looks at first and second glance like there's zero information that can be conveyed, but where a clever strategy means that actually it can, and the discrepancy between the apparent security and the actual information leak can be exploited.
I don't necessarily mean "exploited" in an immoral way: it could be an attack against economic deadweight loss, or against Moloch (Scott Alexander's term for tragedy-of-the-commons type situations where the sum of everyone's actions leads to a situation nobody wants but no individual can break the deadlock), or against entropy (in the sense of general chaos and decay, not in the information-theory-specific sense, confusingly), rather than against other people. Finding information leaks in apparently secure contexts sounds like the domain of fraudsters and hackers, but it could also be applied to things like reconstructing fragmentary ancient texts or recovering corrupted recordings that seem to be lost, or providing market information that was thought to be unknowable but which is useful to both buyers and sellers - or, of course, white-hat hacking, finding potential exploits for fraudsters and hackers and closing them.