December 13, 2020
'From Alex van den Brandhof comes a matter of life and death:
The Potentate of Puzzles decides to give five unlucky citizens a test. The potentate has countless red hats, green hats and blue hats. She says to the citizens, “Tomorrow, you will all be blindfolded as I place one of these hats on each of your heads. Once all the hats are placed, your blindfolds will be removed. At this point, there will be no communication between any of you! As soon as I give a signal, everyone must guess — at the same time — the color of the hat atop their own head. If at least one of you guesses correctly, all of you will survive! Otherwise …”
The potentate continues: “The good news is that there’s a little more information you’ll have. I will be arranging you into two rows facing each other, with two of you in one row and three of you in the other. Citizens in the same row cannot see each other, but they can see all the citizens in the other row. Finally, each citizen will know their placement within their own row — that is, whether they are seated on the left or right or in the middle.”
Can the citizens devise a strategy beforehand that ensures their survival? If so, what is the strategy?'
Answer: Yes (well, almost--99%)
Explanation:
At first glance this seemed impossible. After all, how does other citizens' hats affect the color of my own hat? However, believe it or not, there is a strategy that works 99% of the time, literally. The key is to understand that the goal is to ensure at least one of the citizens gets his/her color correctly. If the plan can ensure that everyone covers all the bases, then this is possible. My strategy is as follows:
The big picture is that everyone in the same row will always guess the same color. Exactly which color I will explain later, but everyone in a row will guess the same color, based on what they see of the other row. Denote the people in the first row as "1" and second row as "2". Further, let us denote R as red, B as blue, and G as green. The notation is as follows: 1GR means row 1 has the first person wearing a green hat and the second person wearing a red. Similarly, 2BBR means the second row has the first person wearing blue, second wearing blue as well, and the third wearing red.
We will focus on the perspective of the people in the first row. If they see that each of the citizens in the second row is wearing a different color, e.g. 2GBR, then pop a champagne, because this configuration is guaranteed to succeed as everyone in row 2 will guess the same color. Which color will row 2 guess? If row 1 are wearing hats of a different color, then there must be a third color not worn by row 1 people. This will be the color that row 2 guesses their own hat. Row 1 will always pick a color that they see in the second row to guess. For example, if 1BR, then 2 will guess G. The only way row 2 gets it wrong is if none of them a wearing a green hat, but then row 1 will pick a color that they see in row 2 to guess, and since row 1 also guesses the same color, it would either be all blue or all red, and so at least one will get it correctly.
If row 1 sees row 2 representing two colors, e.g. 2GGR, then all row 1 needs to worry about is what happens if row 2 guesses blue, in this case. To counter this, prior to the meeting the citizens should agree on one thing--if row 1 are wearing the same color, then row 2 will guess a corresponding color. The exact pairing is as follows:
To see how this would work, imagine if row 1 sees row 2 as 2GGR. In this case, the only way row 2 will get it all wrong is if everyone there guesses B. This happens when a) 1GR/1RG or b) 1GG. The first case is row 2 guessing the "other" color not seen in row 1, and the second case is by the above planning. In both cases, G is the common color, so the two people sitting in row 1 would both guess G. You can verify other color patterns as well.
The ONLY way things might go awry is if row 2 are all wearing the same color. Even then, there is a strategy to maximize the chances of success. Imagine if row 1 sees 2GGG. In this case, row 2 will guess wrong if everyone there guesses B or R. In the case of guessing B, this would be because either a) 1GR/1RG or 2) 1GG. Similarly, row 2 would guess R either due to a) 1BG/1GB or b) 1BB. In those cases, except for 1BB, all other scenarios have at least one person in row 1 wearing a green hat, so row 1 would all guess GG. This means the only setup that would foil the citizens' plan would be 1BB 2GGG; 1RR 2BBB; 1GG; 2RRR. That's three scenarios out of a total of \(3^5 = 243\) scenarios. The raw success rate would be at least \(\frac{240}{243} \approx 99\%\). This is much better than the random guessing strategy which yields \(1 - \left(\frac{2}{3}\right)^5 \approx 87\%\). Even if the potentate knows something is up and tries a row 1 all the same color and row 2 all the same color pattern, he/she would still need to know the pairing beforehand in order to get the color patterns correct.
More minds = greater possibilities!
Here's the code for my strategy for the Classic, verification here: https://t.co/ZH8nmhVD5r
— AZ (@a_____z___) December 14, 2020
Non-computer proof is left as an exercise to the reader 😊 pic.twitter.com/vRNIBJykat
Alright, so it turns out there is a way to achieve 100% success, courtesy of Angela Zhou. My proof is as follows:
Let the actual colors of citizens in row 1 be A and B, respectively. Similarly, let the actual colors of citizens in row 2 be X, Y, and Z, respectively. Before I totally forgot about the positional information for the citizens, which now comes in handy. We denote the actual guesses of each of the citizens be their respective small letters (so for example, row 1 citizen 1 would be guessing "a". His/her actual hat color would be "A"). Please also note that the valid values are 0, 1, and 2. We are doing modulo 3 here.
Now, let's prove a useful lemma: \(-2a \equiv a \pmod{3}\). \begin{align} \text{For } a = 0, &\quad -2a = 0 \equiv 0 = a \pmod{3} \\ \text{For } a = 1, &\quad -2a = -2 \equiv 1 = a \pmod{3} \\ \text{For } a = 2, &\quad -2a = -4 \equiv -1 \equiv 2 = a \pmod{3} \\ \end{align} This will come in handy later.
Now it's modulo arithmetic time!
Here let's assume \(A \neq B\). Now, as per our strategy, row 2's guesses would be x = A, y = B, and z = -A-B. Suppose here all three citizens are wearing different hats in actuality, which means (X + Y + Z) % 3 = 0 (If all three citizens are wearing the same hats, in this case at least one will get the hat color correct). Then the only *wrong* configuration would be X = -A-B, Y = A, and Z = B, i.e. a circular shift of hats. Then, for row 1, for the first citizen to get his/her hat color wrong, the following must happen using the strategy: \begin{align} A &\not\equiv -A-B + 1 \\ B &\not\equiv -2A + 1 \\ B &\not\equiv A + 1 \\ \end{align} The last step we used our lemma from earlier.
However, in this case, b would be guessing \(a+2\). For the second citizen sitting in row 1 to also get the hat color wrong, the following must happen using our strategy: \begin{align} B &\not\equiv A + 2 \\ \end{align}
So it implies that \(B \equiv A \pmod{3}\). But by our earlier assumption, \(A \neq B\) and only 0, 1, and 2 are the possible values, so we reached a contradiction.
Still in the \(A \neq B\) case, the only condition left to check would be that if two of the three citizens in row 2 are wearing the same hat, which can only either be X and Z or Y and Z, since \(A \neq B\). To have everyone in row 3 be wrong, the only combination would be X = B, Y = A, and \(Z = B \neq -A-B\ \to A \not\equiv B\) (remember x = a, b = b, and z = -a-b for A and B in row 1). Here, (X + Y + Z) % 3 would not be 0. Then, per our strategy: \(a = -Y-Z = -A-B\) and \(b = -X-Z = -B-B = -2B \equiv B\). So the second citizen in row 1 will be guaranteed to get his/her hat color correctly.
Here we consider the case where \(A = B\). This means that row 2 will guess \((x = A, y = A, z = -A-A = -2A \equiv A)\), so all three citizens in row 2 will be guessing the same color--the sole color seen in row 1. Here we don't have to consider as many cases, for if all three hat colors in row 2 are different, then someone in row 2 will be correct as guaranteed. As A = B, only cases where the second row will be all wrong are the permutations of: (X = A + 1, Y = A + 1, Z = A + 2) or (X = Y = Z = A + 1 or A + 2), modulo 3, of course. In the latter case, (X + Y + Z) % 3 = 0 so as per our strategy, one of A or B will hit A, since \((A + 1) + 2 \equiv 3\) or \((A + 2) + 1 \equiv 3\). For the first case, (X + Y + Z) % 3 does not equal to 0, so as per our strategy: \begin{align} a &\equiv -Y-Z\\ b &\equiv -X-Z \\ \end{align} The possibilities for a and b are: \(-(A + 1) - (A + 2) = -2A - 3 \equiv A - 3 \equiv A\) and \(-(A + 1) - (A + 1) = -2A - 2 \equiv 1\), so at least a = A or b = A, and since both are wearing A, at least one will get the correct hat color.
I believe all the cases are covered!