8
$\begingroup$

Here is the puzzle:

N hats are put on N logicians, each hat color is selected randomly: black or white.
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: "Black", "White" 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?

It's fairly simple to find an optimal answer for $N = 3$ ($p_{survival} = 3/4$). It's harder, but possible to find an optimal strategy for $N = 7$ ($p_{survival} = 7/8$).
My question - is there a strategy, which has $p_{survival} > 3/4$ for $N \le 6$?
How about a strategy with $p_{survival} > 7/8$ for $N = 10$?
I don't know the answer to these questions. Please either provide such a strategy(-ies), or prove that it is impossible.
Ideally I want to know What is the maximum probability value for $N = 6$ and $N = 10$? (i.e. with a proof that we can't do any better).

P.S. A semi-general strategy, which is optimal for $N = 3$ and $N = 7$ you can find here, but if you don't know it, I suggest you to try to find it on your own, it's a very fun puzzle.

$\endgroup$
10
  • $\begingroup$ What sort of things are the logicians allowed to say while discussing strategy? Outright telling another logician the color of their hat I would assume is not allowed, but can they say other things that relate what hats they see? $\endgroup$
    – Ilak
    Jul 16, 2020 at 17:54
  • 3
    $\begingroup$ They discuss before any hats are given. $\endgroup$ Jul 16, 2020 at 18:10
  • 8
    $\begingroup$ As usual, the logicians wonder why they keep getting forced into these situations. $\endgroup$
    – aschepler
    Jul 17, 2020 at 12:00
  • 3
    $\begingroup$ Just a note, I think I have found answers to both questions in the math literature (though as noted in comments on the linked question, the I think the general answer is unknown and probably hard). (And, I expect some other users also know such things.) Don't really want to answer with that, though, since this is puzzling. (Not really sure of etiquette anyway.) $\endgroup$
    – tehtmi
    Jul 17, 2020 at 12:54
  • 1
    $\begingroup$ @HemantAgarwal Voting to leave open: the previous question is about $N=15$ only (and it's not a duplicate the other way round either, since the answer to this question doesn't resolve the $N=15$ case). $\endgroup$ Jun 19 at 19:04

3 Answers 3

4
$\begingroup$

Reframe the problem:

Consider the possible arrangements of n hats as vertices of an n-dimensional hypercube graph. Coordinate in each dimension corresponds to the color of a hat with edges connecting pairs of hat arrangements that differ by swapping the color of one hat. (Or, if you prefer, this can be equivalently formulated using binary codes and considering 1-bit swaps.)

Given a strategy, if a vertex represents an arrangement where the logicians are successful, one of them must have made a guess, and swapping the hat color of the guesser would lead that guesser to guess incorrectly. So, each successful vertex is adjacent to a failed vertex. WLOG for an optimal strategy, if no one guesses in a configuration, we can choose someone to guess incorrectly in that arrangement (and thus successfully in some adjacent arrangement, possibly to no benefit). Also WLOG, if one logician is wrong for a configuration, any logician who didn't guess may as well also guess incorrectly. Since every logician has guessed for a failing configuration, for any adjacent vertex, some logician has guessed. So, a strategy is essentially the same as a dominating set (a set of vertices so that every vertex in the graph is in the set or adjacent to a vertex in the set) on the hypercube graph with the vertices in the dominating set representing hat configurations where some logician guesses incorrectly. To recover a strategy from a dominating set, observe that a logician's observation corresponds to an edge in the graph (connecting the vertices representing the two possible states of their own hat). If both vertices of the edge are in the dominating set, the logician's guess doesn't matter (they may guess or not guess as they please). If one vertex is in the set, the logician should guess according to the vertex that isn't in the dominating set. If neither vertex is in the dominating set, the logician should not guess.

This is also equivalent to finding covering codes with covering radius $1$ if we view hat arrangements as binary codes.

The best answer I can find in the literature:

The size of the smallest dominating set is given by OEIS A000983. The smallest set for $N = 6$ is of size 12. One such set is $$\{001000, 000100, 110000, 010010, 010001, 100011, 011100, 101110, 101101, 001111, 111011, 110111\}$$ which I found in this paper (citing an earlier work by R.G. Stanton and J.G. Kalbfleisch). For $N = 10$, the best answer is probably not known. The $N = 9$ case can be used, but this is not optimal. This table from Simon Litsyn lists the best known upper bound for $N = 10$ as $120$ referencing (I think) this paper by Östergård. (Possibly this is out of date.) I haven't been able to find a freely-accessible source that lists such codes, though; (it's also possible the upper bounds are non-constructive).

$\endgroup$
8
  • $\begingroup$ Thanks! This is funny how first two paragraphs are exactly how far I was into solving this problem on my own. That was my problem to find those sets or prove that their minimum size is always 1/4 for N<7 and 1/8 for N<15. The terms of "dominating set" and "covering codes" help incredibly. So we have $12/2^6=3/16$ for N=6. What about the set for N=9? Do you have it? Is it bigger than 60 numbers? $\endgroup$
    – klm123
    Jul 19, 2020 at 4:08
  • 1
    $\begingroup$ @klm123 The best for $N=9$ is $62$ as noted in in the OEIS link. There should be an example in this paper researchgate.net/publication/… , but it is paywalled, so I can't check. $\endgroup$
    – tehtmi
    Jul 19, 2020 at 4:15
  • $\begingroup$ Yeah, I see now. This is incredible job which gives me exactly the information I wanted. Thank you. P.S. This is weird that lower bound for K(9,1) is 57, while for K(10,1) it is 105, while solution with K(9,1)=57 will automatically mean that K(10,1) <= 57x2 = 104 that table doesn't seem to be thought through, but anyway it shows that there are better strategies and no simple proof of optimality. $\endgroup$
    – klm123
    Jul 19, 2020 at 4:36
  • $\begingroup$ @klm123 The table is out of date (last updated 1999), but still the best public summary I could find. So, newer results like improving the lower bound for $K(9,1)$ are missing. Your are right that $K(10,1)$ should be less than or equal to twice $K(9,1)$, but if you double check your calculation, you will see there is no problem. $\endgroup$
    – tehtmi
    Jul 19, 2020 at 4:52
  • 2
    $\begingroup$ If we follow links from wikipedia en.wikipedia.org/wiki/…. we can find a more up to date table, where K(9,1) is known to be 62. old.sztaki.hu/~keri/codes/2_tables.pdf $\endgroup$
    – klm123
    Jul 19, 2020 at 5:16
1
$\begingroup$

WRONG AND PARTIAL ANSWER I thought this was a promising approach but it's not, have a look to the comments. I highlighted in bold the parts where my reasoning was wrong.

If the number $n$ of logician is

$b^k - 1$ for some b (with b, k) integer

They can use

The same strategy described in the linked answer but assigning themselves vectors in $Z_b^k$ rather than binary vectors and computing the sum modulo $b$ rather than the XOR.

More specifically:

The logician agree beforehand on a numbering from $1$ to $n$ and each one is assigned the vector that corresponds to their number written in base $b$. For example, if there are $n=8$ logicians ($b=3$ and $k=2$) the first logician is assigned the vector $[0,1]$, the second has $[0,2]$, then $[1,0]; [1,1]; [1,2]; [2,0]; [2;1]$ and the last one has $[2,2]$. Each logician knows which vector is assigned to who.
They agree on the definition of $S$ as the entry-wise sum of the vectors of the logicians with black hats modulo $b$. They also agree beforehand to bet that $S$ is non-zero. All these things happen before the hat distribution.

When the hats are worn:

of course none of the logicians can compute $S$ because they don't know the color of their hats. But each of them knows that $S$ can have only two values: let $v$ be the vector assigned to one specific logician. They compute $S_v$ which is the entry-wise sum of the vectors of the logicians with black hats modulo $b$ excluding themselves. The real $S$ can be either $S_v$ (if logician $v$ has a white hat) or $(S_v + v)$ modulo $b$ (if logician $v$ has a black hat). Each logician makes the same reasoning in their heads.

When they have to answer the question:

If one choice of their hat color would make $S$ equal to zero they claim the other color. Otherwise they say "I don't know". If $S$ is non-zero the logician with vector $S$ will guess their hat color and the other ones will say "I don't know". if $S$ is zero all the logicians guess the wrong color.
that's not true (thanks @tehtmi). This reasoning works only for $b=2$ and using the XOR rather than the sum and modulo. That's because the XOR is the inverse of itself while the modulo sum is not, so it could be the case that neither $S_v$ not $S_v + v$ are zero for the logician which vector is $S$.

This gives them the same optimal survival probably of $\frac{n}{n+1}$ which is the probability of $S$ to be non-zero regardless on $b$.
that's also not true (thanks @thetni and @aschepler and @klm123). The possible values of $S$ are not equidistribuited.

proof:
see the linked answer replacing a bunch of $2$s with $b$, "XOR" with "sum of the vectors modulo $b$", $15$ with $n$ and $16$ with $n+1$.

To answer the question in which $N=10$:

again in the linked answer it is stated that "[this strategy] generalizes when the number of players $N$ is of the form $2^k−1$. If it's not, the players can pretend it is by ignoring some number of the players, which gives win probability $1−\frac{1}{2^k}$ where $2^k$ is the largest power of $2$ with $2^k−1 \leq N$".

Using my generalization they can
pretend that $N$ is $b^k$ for some $b$ with $b^k−1 \leq N$ (of course choosing $b$ such that $b^k$ is maximum) and ignoring some number of the players, which gives win probability $1−\frac{1}{b^k}$.

In this case they chose

$b$ to be $3$ and $k$ to be $2$, ignoring one player which gives them a survival probability of $\frac{8}{9}$ which is greater than $\frac{7}{8}$ as requested.

I'm afraid this strategy is not applicable optimally for a lot of values of $N$ (for example it is not possible to achieve a survival probability greater than $\frac{3}{4}$ for $N=4,5,6$).

$\endgroup$
15
  • 2
    $\begingroup$ The thing is that $2^{10}=1024$ is not even dividable by 9 =) so there should be a mistake. With $b=2$ all possible values of S are equally probable, there by $p=n/(n+1)$, but it is not the case for $b=3$. $\endgroup$
    – klm123
    Jul 17, 2020 at 15:06
  • 1
    $\begingroup$ If sum is S and S nor S+S is 0 and logician S has a white hat, logician S will not guess, as neither S nor S + S is zero. (This may not be the only issue, but in general, I think there are configurations where no one will guess if b is not 2.) $\endgroup$
    – tehtmi
    Jul 17, 2020 at 15:35
  • 1
    $\begingroup$ Also, regarding quantization, when I was looking at this it seemed like the sums were approximately but not exactly equi-distributed. $\endgroup$
    – tehtmi
    Jul 17, 2020 at 15:36
  • 2
    $\begingroup$ If $n=8$ and they pick $b=3, k=2$, I get that the probabilities of true values of $S$ are $32/256$ for $S=0$ and $26/256$ for $S \neq 0$, so $p_{\mathit{survival}}=3/4$, not $8/9$. But this idea has me thinking the problem is equivalent to finding an error correction code on $\mathbb{Z}_2^n$ with Hamming distance 3. I think maximum sizes of such codes are in general unknown. $\endgroup$
    – aschepler
    Jul 17, 2020 at 20:59
  • 2
    $\begingroup$ Have you tried it? For b=3, k=1, n-2, the logicians will fail if they have both black or both white hats. For b=5, k=1, n=4, the logicians will guess wrong 4 times, all pass 4 times, and succeed 8 times. In both cases a survival rate of 50%. For example if logicians 1234 are bbbb, wwww, bwwb or wbbw, they will all guess wrong. If they are bbww or wwbb they will all pass. $\endgroup$
    – Florian F
    Jul 17, 2020 at 21:03
-5
$\begingroup$

Simple 100% strategy for any n>1.

The logicians determine that this is not the typical framing for questions of this type, and that due to this particular framework there is a simple and trivial strategy for staying alive.

  1. During preliminary discussion, designate a non-suicidal logician to be the designated guesser.
  2. Everyone else is instructed to look at that guesser's hat and nod yes for black or shake your head no for white.
  3. If the non-suicidal logician sees shaking heads looking at him that logician says white, if they are nodding yes, he says black.
  4. Everyone else says "I don't know"

The logicians end up living to wonder if it would have been better for them to become suicidal in situations like this just so they wouldn't constantly be put in these types of situations.

$\endgroup$
5
  • $\begingroup$ Oh common, anything, but not this type on answers... You know it's a puzzle, not real life. $\endgroup$
    – klm123
    Jul 16, 2020 at 19:54
  • $\begingroup$ Actually it's life or death for the logicians, if they were just going to suffer scorn, then okay, but you've put their lives on the line, would they ignore obvious solutions? $\endgroup$
    – Mathaddict
    Jul 16, 2020 at 19:56
  • 2
    $\begingroup$ "They cannot communicate in any way possible". Nodding and shaking heads is a form of communication $\endgroup$
    – melfnt
    Jul 16, 2020 at 20:47
  • $\begingroup$ Looking at one other's hat is also a form of communication. $\endgroup$
    – Florian F
    Jul 17, 2020 at 11:18
  • $\begingroup$ @Florian F, melfnt I've added that sentence to the puzzle after this answer. $\endgroup$
    – klm123
    Jul 18, 2020 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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