16
$\begingroup$

$n$ logicians are wearing hats which can be of $n$ different colors. Each logician can see the colors of all hats except his own. The logicians must simultaneously call out a color; they win if at least one calls the color of his own hat.

Mathematically, a strategy is an element of $(C^{n-1} \to C)^n$ where $C$ is the set of hat colors ($\mathrm{card}(C) = n$); a strategy $(d_0,\ldots,d_{n-1})$ is given by the decision procedures of each logician, where logician $k$ calls out $d_k(h_0, \ldots, h_{k-1}, h_{k+1}, \ldots, h_{n-1})$ when the hat colors are $(h_0, \ldots, h_{n-1})$.

One winning strategy for this classic puzzle is

having numbered the logicians and the colors, each logician calls the color that is his own number minus the sum of the hat colors that he sees (all modulo $n$). Then whoever has the number corresponding to the sum of the colors is calling out his own hat's color.

This isn't the only solution. (Hint: the case $n=2$ is easy. Now concentrate on $n=4$ and try to reduce it to the previous case.)

You can rephrase the strategy above this way: let $h_0, \ldots, h_{n-1}$ be the hat colors of logicians $0, \ldots, n-1$; logician $k$ calls out the value of $h_k$ that makes the equation $h_0 + \ldots + h_{n-1} = k$ true. More generally, equip the set of colors $C = \{c_0, \ldots, c_{n-1}\}$ with any group structure $(C, *)$, and assign each logician a unique color $\ell_k$; then a winning strategy is for each logician $k$ to solve the equation $h_0 * h_1 * \ldots * h_{n-1} = \ell_k$ for $h_k$ and call out the solution. Hence every group structure leads to a winning strategy.

Are the strategies presented above are all there is? If not, is there a reasonable way to describe the collection of all winning strategies, such as relating them to another well-known mathematical structure? For example, how many distinct strategies are there for a given $n$?

  • 0
    Would you please give all the information on 2 and 4 that you have? This is a question, not a challenge to make us work, right?2011-11-06
  • 0
    @Gilles: You have not spelled out anything. You have not given a clean definition of "winning strategy" (when are two strategies the same?), you have not given the answer for 2 and 4. You should explain what you know.2011-11-06
  • 0
    @Phira I've now spelled out the most general solution I know.2011-11-06
  • 0
    Each logician's colours can independently be put in bijection with the group, and the product can be formed in any order. Very nice question, by the way! :-)2011-11-06
  • 2
    Yup. This is fun! Though (as a kinda coding theorist) I like that version even better, where there are only two colors. The logicians have the option to call a color or pass... and the rule is that if any single one calls a wrong color, they all lose as a team. The object is then to device a strategy that maximizes the chance of the team winning (to the best of my knowledge they cannot guarantee a win).2011-11-06
  • 1
    You have to take an *Abelian* group for this to work.2011-11-06
  • 0
    @Phira: Why does the group have to be abelian? The product must have some value, and given $n-1$ colours that value uniquely determines the $n$-th; if they all guess a different value, one of them must be right, and must therefore correctly deduce his or her own colour -- where does commutativity enter into it?2011-11-06
  • 0
    @Phira: The product $c_0\cdot\dotso\cdot c_{n-1}$.2011-11-06
  • 0
    @Phira: I don't understand. It seems you haven't understood Gilles' solution. The $c_i$ *are* the hat colours, as stated in the second paragraph (or, as I pointed out in a comment above, each of them can separately be mapped to the hat colours). Also a product is just a product; it can't be right or wrong :-)2011-11-06
  • 0
    @joriki I have deleted my comments, I see no point in discussing this further. Even if the OP were written correctly, the question would be too wide and vague in my opinion. And if the problem with a post is inconsistency, it does not help to point to one of the inconsistent definitions.2011-11-06
  • 0
    @Phira: I don't understand your attitude to this question. You haven't pointed out a single concrete problem with it. First you objected to some vagueness in the question, though I thought it was clear enough from the original formulation what was meant. Now the question has been clarified, and as far as I can remember the comments you've now deleted, you haven't pointed out a single concrete problem in it; you've merely claimed repeatedly that there are such problems. That doesn't strike me as particularly constructive.2011-11-06
  • 0
    @joriki In the second grey rectangle the c's are defined differently from the beginning, and neither definition makes the product a correct strategy. And just because you did not understand what I said, does not mean that I did not point to anything concrete. But if you don't understand it after an already lengthy comment exchange, a further comment discussion is rather pointless.2011-11-06
  • 3
    @Phira: Well, since you deleted the comments there's no way of telling now whether you'd pointed to anything concrete. I suggest you do so now. So far, I can see neither an inconsistency in definitions of the $c_i$, nor an error in the product strategy.2011-11-06
  • 0
    @joriki: Are the c_i all the available colors or the colors of the actual hats? In what order does a player multiply other people's hat colors?2011-11-06
  • 1
    @Phira: The $c_i$ are the colours of the actual hats. The players don't multiply the colours of other people's hats; they solve the equation $c_1\ldots c_{n-1}=l_k$ for $c_k$, as described in the second box. The result is $c_{k-1}^{-1}\ldots c_1^{-1}l_kc_{n-1}^{-1}\ldots c_{k+1}^{-1}$. As I pointed out in a comment above, they could use any other order for the product, as long as they all use the same.2011-11-06
  • 0
    @joriki I see, thank you. I see now that the strategy works with this interpetation. Note that the $c_i$ *are* defined as all the elements of the set of colors in the same paragraph. I still don't understand the sentence "logician k calls out the value of $h_k$ that makes the equation $h_0+\dots+h_k=k$ true.", but this is less important.2011-11-06
  • 0
    @Phira: You were right, there were inconsistencies in the use of $c_i$ and $h_i$ to refer to all the available colours or the colours of the actual hats. I've tried to fix the question. Regarding that sentence you quoted, I think the last index was supposed to be $n-1$ instead of $k$ -- at least that would correspond to the solution in the first box that this equation is supposed to describe. I've fixed that, too.2011-11-07

1 Answers 1