8
$\begingroup$

Following Guess your hat color, but you don't have to and it's interpretation via Covering codes I tried to create a puzzle with more hat variativity, i.g. 3 types of hats.

4 hats are put on 4 logicians, each hat color is selected randomly: Red, Green or Blue.
As usual, every logician doesn't see the hat on his own head, but sees the rest. They cannot communicate in any way possible.
Each logician at the same moment must answer the question - "what color is the hat on your head?". And there are only 3 possible answers they can say: "Red", "Green", "Blue" and "I don't know".
If at least one color is named incorrectly logicians fail and die. If no one named a correct color they die just the same. Otherwise (if at least one answer is correct) - logicians survive.
As usual, they have time to discuss a strategy before the hats are put on their heads.
What's the strategy, which gives the highest probability to survive?

I picked number of logicians $N=4$ and number of colors $M=3$, because these are the numbers a generalized covering code exists for ($N=(3^2-1)/2$, see wiki). There by the puzzle solution:

Logician number themselves with 2D vectors:
$L_1 = (0,1)$;
$L_2 = (1,0)$;
$L_3 = (1,1)$;
$L_4 = (1,2)$.

And colors with integers:
$c_{red} = 0$;
$c_{green} = 1$;
$c_{blue} = 2$.

They calculate a sum S of all hats as $\sum(c_i \cdot L_i) \mod 3$. For example, if hats are like GRRB, then $S = [ (0,1)+0+0+2*(1,2) ] \mod 3 = (2,5) \mod 3 = (2 \mod 3,5 \mod 3) = (2,2)$

With each hat placement there will be exactly one person who is not sure whether $S = (0,0)$ or not. And logicians agree that only that person may speak. And that they must always assume that $S \neq (0,0)$ and name the color appropriately - randomly choosing one of the two colors.

Due to the fact that 8 non-zero combinations: $1\cdot L_i$ and $2\cdot L_i$ cover all 8 possible non zero vectors $(0,1); (0,2); (1,0); (1,1); (1,2); (2,0); (2,1); (2,2)$ the sum $S$ can take all $9$ possible results with the same probability of $1/9$. Thereby the logicians lose for sure in $1/9$ of the cases when $S=0$ and they win with probability of $50\%$ in the rest of the cases. Giving survival probability of $P_{survival} = 4/9$.

That's all good, but the probability is much less than expected. The upper estimate of survival probability is $P_{survival} \le N/(N+M-1) = 2/3$. Here is why:

For each situation a specific person speaks up their color there will be 1 hat distribution where they are correct and $M-1$ hat distributions where they are wrong. To survive they need at least one person to speak. When they die there can be $N$ speaking logicians at most. Thereby
$K_{goodDisctributions} \cdot (M-1) \le N \cdot K_{deadlyDistributions}$,
$K_{goodDisctributions} / K_{deadlyDistributions} \le N / (M-1) $,
$P_{survival} = K_{goodDisctributions} / (K_{goodDisctributions} + K_{deadlyDistributions}) \le N / (N+M-1)$

This number was achievable in the similar cases for $M=2$ (when $N=2^k-1$). But now I have no idea how to achieve it. Thereby two questions:

Is there a solution for the mentioned puzzle ($N=4$, $M=3$) with probability $P_{survival} > 4/9$?

Is there a combination of $N\ge 2$ and $M\ge 3$ where $P_{survival} = N/(N+M-1)$ is achiavable?


Edit:
@tehtmi answer proves that $P_{limit} = N/(N+M-1)$ is not achievable. I've rewarded this proof with a bounty. Now I want to reward the best strategy with a bounty.

@Reinier's strategy gives (if I've not messed up the calculations)
$P=16/27 \approx 59.3\%$ for $N=4,M=3$,
$P=55/81 \approx 67.9\%$ for $N=5,M=3$,
$P=17/32 \approx 53.1\%$ for $N=4,M=4$,
$P=75/128 \approx 58.6\%$ for $N=5,M=4$
Is there a better strategy for any of those cases?

$\endgroup$
  • $\begingroup$ They will not find the strategy that gives highest probability, because they are logicians, not probabilists. $\endgroup$ – WhatsUp Jul 23 at 13:46
  • $\begingroup$ Why can't this problem be solved with the same method (covering sets) as your previous question with 3-coloured hats? $\endgroup$ – Dmitry Kamenetsky Jul 24 at 0:58
  • $\begingroup$ @DmitryKamenetsky what do you mean? I've posted the solution with the same method. The one which gives 4/9. $\endgroup$ – klm123 Jul 24 at 6:22
  • 1
    $\begingroup$ @DmitryKamenetsky With 2 colors, each right guess accompanies only 1 wrong guess, so wrong guesses can be placed without restriction. With 3+ colors, each right guess accompanies 2+ related wrong guesses, so there is a restriction on how they are placed. Most dominating sets on the full graph probably can't be realized by a real strategy. $\endgroup$ – tehtmi Jul 25 at 6:19
3
+200
$\begingroup$

Partial Answer

I am only going the answer the first question here, the answer is

Yes, I found a solution with a survival probability of $\frac{16}{27}$.

The case $N = 2$, $M = 3$

In this case the following tactic can be used: if a logician sees no-one with a red hat, they say "Red", otherwise they say "I don't know".
Note that this tactic works in the case where there is exactly 1 red hat, which is the case in 4 out of 9 situations. So we get a success probability of $\frac{4}{9}$, which is already as good as the suggested solution for $N = 4$!

The case $N = 3$, $M = 3$

As a first try at a good tactic, we can again let every logician say "Red" if they don't see any red hat, and "I don't know" otherwise. This guarantees they live if exactly one of the hats is red, so it would give a winning probability of $\frac{12}{27} = \frac{4}{9}$.
However, there is still some room for improvement here: if a logician sees 2 red hats, they already know for sure that both other logicians are going to say "I don't know", so they might just as well guess something else, for example "Blue". In this way, there are three additional winning situations,((red, red, blue) and permutations), so we get a winning probability of $\frac{15}{27} = \frac{5}{9}$.

The case $N = 4$, $M = 3$

What we can do in this case is the following: Again, if a logician sees no red hats, they will say "Red". In the case that a logician sees 2 red hats and no blue hat, they will say "Blue". Otherwise they will say "I don't know". This tactic works in all cases where there either is exactly one red hat (32 situations), or where there are at least 2 red hats and exactly one blue hat (16 situations). This gives a winning probability of $\frac{48}{81} = \frac{16}{27}$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ $N=4,M=3$ - hey, that's more than 50%! And even w/o distinguishing logicians. Cool. May be 54/81 is possible after all? $\endgroup$ – klm123 Jul 23 at 15:01
  • $\begingroup$ I've tried finding better solutions using a genetic algorithm, but after an hour of running it's found a ton of 48/81 solutions but not a single 49/81. $\endgroup$ – Magma Jul 23 at 21:18
  • $\begingroup$ @Magma could you post the code somewhere? $\endgroup$ – klm123 Jul 24 at 6:23
2
+100
$\begingroup$

Answering whether the $N/(N + M - 1)$ survival probability can be met:

To achieve the $N/(N + M - 1)$ probability, it is clear (from construction of the constraint) that three things must be true:

1) When the logicians succeed, only one of the logicians has guessed.

2) When the logicians fail, every logician has guessed incorrectly.

3) At least one logician guesses for every configuration.

So, we should attempt to construct a strategy assuming these rules must be true. We consider the graph of hat configurations with configurations notated as strings. By a row will will mean a group of configurations where all hat colors except one are fixed. Each vertex (corresponding to a hat configuration, which I will also sometimes call simply a "guess") is called correct if exactly one logician guesses, and the guess is correct so the logicians survive or incorrect/wrong otherwise. For a given row, if the corresponding logician (whose hat varies in that row) guesses, they will be right exactly once and wrong in every other position in the row. When they guess right, it must be a correct configuration and when they guess wrong, it must be an incorrect configuration. If the logician doesn't guess, none of the configurations in the row may be wrong (as every logician must guess wrong whenever there is any wrong guess). So each row is either completely correct or has exactly one correct vertex.

Clearly someone must guess wrong at least once, so WLOG let's start with $000...0$ as a wrong guess. Each logician guesses in this configuration, so WLOG, let "one" be each logician's correct guess. Then bit strings with $1$ one are correct guesses, and other strings with $N-1$ zeros are incorrect. This characterizes the correctness of every guess with $N$ or $N-1$ zeros.

So, $100...0$ is a correct guess for logician 1. If $1x0...0$ ($x \neq 0$) is a wrong guess, every logician guesses wrong for it including logician 2. But that means there is a corresponding correct guess for logician 2 in the row $1?0...0$. But once there is a wrong guess, there can only be one correct guess in the row which we already have with $100...0$ which can't be the guess of two different logicians; (it is already the correct guess of logician 1). So it must be that 1x0...0 is a correct guess. Similarly any string with a one and $N-2$ zeros is a correct guess by making a similar argument with a different pair of logicians.

If $1x0...0$ ($x \neq 1$) is a correct guess, we already know $0x0...0$ is a wrong guess, so everything else in row $?x0...0$ is also wrong. Furthermore, since this is logician 1's row, it must be logician 1 who guessed correctly. The same argument works for every pair of logicians. We have now characterized the correctness of all configurations with $N-2$ zeros: configurations are right when they have a one, and if there is only $1$ one, it corresponds to the logician with the correct guess.

We can now see how to induct. Suppose we know that for all smaller zero counts, configurations are correct exactly when there is at least $1$ one, and if there is exactly $1$ one, it corresponds to the correct guesser.

If we know $a_{1}...a_{k}00...0$ is a correct guess and if only one of $a_i$ is one (for logician $i$), then $a_{1}...a_{k}x0...0$ must be a correct guess because otherwise logician $k + 1$ would have to guess correctly in a row that already has a correct guess by logician $i$, which, as before, is impossible. This takes care of cases with $1$ (or $2$) ones.

If $a_{1}...a_{k+1}0...0$ has exactly $1$ one (and is thus correct), say in position $k+1$, then $a_{1}...a_{k}00...0$ is wrong by the inductive hypothesis, so everything else in row $a_{1}...a_{k}?0...0$ is also wrong and logician $k+1$ must be the one who guesses correctly.

If $a_{1}...a_{k+1}0...0$ has more than $2$ ones, we can further induct on the number of ones. Say position $k+1$ has one of the ones. Then $a_{1}..a_{k}0$ and $a_{1}..a_{k}2$ are two guesses in the same row with fewer ones and thus correct by the new inductive step, so all other vertices in the row must also be correct. (Here, we have used the fact that there are at least three colors.)

If $a_{1}...a_{k+1}0...0$ has no ones, then again, it is in the same row as a correct guess, say $a_{1}...a_{k}10...0$ which is correct, and, by the inductive hypothesis, $a_{1}...a_{k}00...0$ which is wrong. Thus, it is also wrong. This completes the inductive step.

It follows, we must have a strategy where guesses are correct exactly when there is at least $1$ one. However, this isn't a valid strategy (for $N > 1$), as there is only a valid guesser when there is exactly $1$ one. Otherwise, all adjacent configurations are correct which is impossible. Therefore, there is no strategy that fulfills the given constraints. (Of course, the subset of this strategy that consist of valid guesses is used as part of the strategy Reinier suggests which is perhaps no coincidence; it seems quite efficient.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ Could you please elaborate on the last paragraph? There is only a valid guesser when there is exactly 1 one. Why there can't be a valid guesser with $L>1$ one's? $\endgroup$ – klm123 Jul 27 at 10:34
  • $\begingroup$ To have a valid guesser, you have to choose who guesses right for the configuration which means there will be a particular $M - 1$ adjacent configurations that are wrong. This isn't strictly enforced in the construction, so it is violated at the end. If there are multiple ones, every adjacent configuration still has at least 1 one (a move of one step can only change one hat) so the construction still requires it to be correct. So there is no one who could have made that guess without messing up adjacent guesses which we have already assumed are correct. $\endgroup$ – tehtmi Jul 27 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.