25
$\begingroup$

There are $n$ boys and $n$ girls. Each of them is given a hat of only 4 possible (known) colors and doesn't know its color. Now each can only see all the colors of hats of those of the other gender and no contact is allowed, then each is asked to guess the color of their own hat at the same time. Determine whether such $n$ exists that there is a strategy that at least one child can guess right under any circumstances.

When there are only 3 possible colors, the problem has been solved ($n=2$ is OK) through simple algebra. But when it comes to 4 colors, the problem seems much harder. Please help.

Solution for 3 colors ($n=2$): we use 0, 1, 2 to represent the colors, the boys are $a, b$ and girls are $c, d$, respectively. Each boy knows the value of $c, d$, while each girl knows the value of $a, b$. Now consider the four number:$$a+b+c,$$ $$d+a-b,$$ $$d+b-c,$$ $$d+c-a.$$ It's easy to show at least one of them is divisible by 3. As a result, the strategy is: $A, B, C, D$ guess $c+d$, $c-d$, $-a-b$, $b-a$$\pmod 3$ respectively, and one of them must be right.

$\endgroup$
  • 1
    $\begingroup$ In what order do they guess? $\endgroup$ – Arnaud Mortier Jul 31 '18 at 12:15
  • 3
    $\begingroup$ With no transfer of information, I don't see how this is possible even with just 2 colors. Could you provide the solution for 2 (or 3) colors? $\endgroup$ – Jens Jul 31 '18 at 13:21
  • 1
    $\begingroup$ Lack of info transfer need not make it impossible. This is incomplete it demonstrates how info transfer may not be nesc. If n=2 and there are three colors then Boy 1 will guess Blue unless the girls are wearing a Green and a Red hat. If Boy 1 is wearing Blue, the girls both answer Red. If B1 is wearing Blue either he or one of the girls is right. But... I can't finish it. $\endgroup$ – fleablood Jul 31 '18 at 14:19
  • 1
    $\begingroup$ "The problem has been solved" makes it sound as though it's part of the literature. Can you give a citation? $\endgroup$ – Brian Tung Aug 3 '18 at 15:57
  • 5
    $\begingroup$ Let me try to restate the problem in plain language, without all the confusing silliness about boys and girls and colored hats. Does there exists, for some $n∈\mathbb N,$ a pair of functions $$f,g:\{1,2,3,4\}^n→\{1,2,3,4\}^n$$ such that $$\forall x,y\in\{1,2,3,4\}^n\exists i\in\{1,…,n\}(f(x)_i =y_i\text{ or }g(y)_i=x_i)\ ?$$ $\endgroup$ – bof Aug 6 '18 at 13:29
11
+100
$\begingroup$

There is always such a strategy, no matter the number of colors, when $n$ is sufficiently large (depending on the number of colors). See the bottom of this answer for an explicit value of $n$ that works. For $4$ colors, it gives $n = 4^{144}$.

Let $k$ be the number of colors. The idea is that a child can, on beforehand, make $k$ statements about the other group's colors, in such a way that in every scenario exactly one statement is true, and map each statement to a color. A simple example is, when Tom makes the $k$ obvious statements about Jade's color and maps them to, well, those colors. When the experiment starts, the girls may then assume that the statement corresponding to Tom's color is false. (Indeed, if Tom guesses right, nothing matters anymore.) In the example, they may assume Jade's color is not the same as Tom's. We will use more interesting statements.

By the pigeonhole principle, among a group of $1+(b-1)k$ girls, there is a group of $b$ which has the same color. Fix $b$ for the moment and suppose $n \geq 1+(b-1)k$. (The choice of $b$ will depend on $k$ only.) Fix such a group $G$ of $1+(b-1)k$ girls. The children agree about an enumeration $G_1, \ldots, G_{\binom{1+(b-1)k}{b}}$ of the subsets of size $b$ of $G$.

The key is that, given a group of $k$ girls that may assume they have the same color, they can each guess a different color, so that at least one of them will guess right. The problem is that the girls can never know which group of $k$ girls has the same color, but the boys can limit down the possibilities:

Lemma. Given a piece of information about the girls' colors, which takes values in a set of size $N$, the boys can limit down the number of values it can take to $k-1$, provided there are at least $\binom N{k-1}$ boys.

Formally, if $C$ is the set of colors, and given a function $f : C^n \to I = \{1, \ldots, N\}$ known to the boys and girls, there exists a strategy which takes $\binom N{k-1}$ boys and makes that, if all those boys guess wrong, then there is a subset $J \subseteq I$ of size $k-1$ such that $f(x) \in J$. Where $x \in C^n$ denotes the vector of the girls' colors.

Proof. In the case $N = k-1$ (or smaller), this is clear: just let one boy map each element of $I$ to a different color. The point is that this is possible for very large $N$. When Tom chooses $k-1$ indices $i_j \in I$, maps each group $i_j$ to a color, and the statement "$f(x)$ is none of the $i_j$" to the $k$th color, then the girls may either assume that $f(x) \neq i_j$ for some $i_j$, or that $f(x)$ is one of the $i_j$, depending on Tom's color. In the latter case, we are happy: we've narrowed down the possibilities of $f(x)$ to $k-1$ numbers. We need a strategy for the former case, where the girls can only exclude one of the $k-1$ indices Tom chose, and we have no control about which it will be. It suffices to find subsets $U_j$ of size $k-1$ of $I$ such that, for each choice of elements $u_j \in U_j$, the complement $U - \cup_j\{u_j\}$ has cardinality at most $k-1$. This is of course possible, simply take all subsets of $I$ of size $k-1$. Thus, provided that there are at least $\binom{|I|}{k-1}$ boys, the girls can assume that there is a subset $J \subseteq I$ of size $a \leq k-1$, such that $f(x) \in J$. W.l.o.g. we may assume $a = k-1$; the girls can always make $J$ larger in a way they agreed about on beforehand. $\square$

Let $I = \{1, \ldots, \binom{1+(b-1)k}{b}\}$. The boys can now make statements about which group $G_i$ has the same color (where the group with smallest index is chosen if there are multiple such groups). Call that group (with smallest index) $H$. This is our $f(x)$. Thus, provided that there are at least $\binom{|I|}{k-1}$ boys, the girls can assume that there is a subset $J \subseteq I$ of size $k-1$, such that $H = G_j$ for some $j \in J$. This $J$ is known to all the girls, by looking at the boys' colors.

Now that we've limited the possibilities for $H$ to $\{G_j : j \in J \}$, we would like to apply our key idea to each of these groups: in each group, let the girls say all possible colors. The problem is that those groups are not necessarily disjoint. But the children know how to deal with that:

Lemma. Given integers $a,k \geq 1$ and $b \geq k+(a-1)(k-1)$, then given $a$ sets $G_1, \ldots, G_a$ of size $b$, there exist $m \leq a$ and a finite number of disjoint sets $T_1, \ldots, T_m$ of size $k$ such that each $G_j$ contains some $T_i$.

Proof. By induction on $a$. For $a=1$ this is trivial. Let $a>1$ and suppose each intersection $G_a \cap G_i$ is at most of size $k-1$. Then we can select $k$ elements of $G_a$ that are not in any other $G_i$, take these to form a $T_j$, and proceed by induction. If some $|G_a \cap G_i| \geq k$, choose $k$ elements in their intersection and let them form a $T_j$. This $T_j$ works for any $G_l$ that contains those $k$ elements. Remove these elements from all $G_l$ and proceed by induction. $\square$

The lemma implies, with $a = k-1$, that there exist disjoint groups $T_j$ of $k$ girls, such that the girls may assume each $G_j$ contains a $T_j$. (In practice, the girls must agree about such a choice of $T_j$'s for every possible $J \subseteq I$ of size $k-1$.) In particular, there exist disjoint groups of $k$ girls, at least one of which is contained in $H$. That is, at least one of which consists of girls with the same color. In each group $T_j$, let the girls guess all different colors. Then at least one girl guesses correctly (unless one of the boys guesses correctly).


We conclude that $$n = \max \left(\binom{|I|}{k-1} , 1+(b-1)k \right) $$ suffices, where $|I| = \binom{1+(b-1)k}{b}$ and $b = k+(a-1)(k-1)$ and $a = k-1$. Using the bound $\binom xy \leq x^y$ and estimating $b \leq k^2$ and $1+(b-1)k \leq k^3$ we get that $$n \geq \left( (k^3)^{k^2}\right)^{k} = k^{3k^3}$$ suffices.

$\endgroup$
  • $\begingroup$ So can you give the explicit functions for the case $k=4$? In particular, what are the values of $a$ and $b$? And the minimal $n$? $\endgroup$ – san Aug 8 '18 at 21:19
  • $\begingroup$ @san Sure. I'll get back to this tomorrow. It looks like at will be of size something like $4^{4^{4^2}}$. $\endgroup$ – punctured dusk Aug 8 '18 at 21:20
  • $\begingroup$ I don't understand very well your strategy. Could you make the explicit construction for $k=4$, fixing $a$, $b$, $n$ and $N$? $\endgroup$ – san Aug 9 '18 at 20:46
  • $\begingroup$ You can read the values from the formulas at the end: $a=3$, $b=10$, $|I| = \binom{37}{10}$ and $n = \binom{|I|}3 = \frac16 \binom{37}{10} \left(\binom{37}{10}-1 \right) \left(\binom{37}{10}-2 \right)$. I can't make the construction itself much more explicit, there are too many things the children need to agree about on beforehand; such as an enumeration of all subsets of $\{1, \ldots, 37\}$ of size $b=10$, the ordering of the girls and the boys, and the choice of $T_j$'s for all possible $S_j$'s in the second lemma. Which part of my answer needs clarification? $\endgroup$ – punctured dusk Aug 9 '18 at 20:50
  • $\begingroup$ So if $a=3$, $b=10$, $k=4$, what is the value of $m$ in the second Lemma? $\endgroup$ – san Aug 9 '18 at 21:01
1
$\begingroup$

Here is what I've tried so far to find a possible solution. First I tested your solution for 3 colors against all 81 hat combinations to make sure it works since it's still pretty mind boggling to me. I also went back and looked at n=1 with 2 colors, where one person simply says the color they see, and the other person says the opposite of the color they see. I tried to find a pattern that might apply for 4 colors.

In both examples the players have positionally unique strategies that are sensitive to the order of the inputs, & every group input has a unique group output.

With n=1, we have 1 variable a, which can expressed as a and -a to describe each player's strategy.

With n= 2, we have 2 variables a and b, which can be expressed together as follows to form the strategies you posted:

a+b, a-b, -(a+b), and -(a-b) -- replacing a & b in the first two expressions with c & d

With 3 variables we can write the following 8 possible strategies:

a+b+c, a+b-c, a-b+c, a-b-c, and their 4 opposites -- making the whole expression negative and replacing a, b, & c with d, e, & f.

I ran into trouble when deciding how many players to have. With 6 players (a thru f, resulting in 4096 hat combinations), we have to choose which 2 of the 8 available expressions to ignore. I haven't found a combination of 6 of them that produces a unique output (after %4) for every input. With 8 players, we can use all 8 expressions, but each expression only refers to three other players, which is not all the information each players has available.

Hopefully this idea could go somewhere, but I've personally hit a block.

$\endgroup$
  • $\begingroup$ Maybe we should be more greedy on $n$. Personally, I don't think there is a strategy that is easy to find when $n$ is small. $\endgroup$ – J.Guldan Aug 8 '18 at 4:11
1
$\begingroup$

I worked out the intricated solution of @barto in the case of $k=4$, and it is too long for a comment.

So take 25 girls, set $N=\binom{25}{7}$, $I=\{1,\dots,N\}$ and $n=\binom N3$ and take $n$ boys. For $j=1,\dots, n$ (that is for each boy) take a set $U_j$ subset of $I$ with three elements. Let the set of colors be $C=\{a,b,c,d\}$ and set $C'=\{a,b,d\}$. For each $j$ fix a bijection $\sigma_j: C'\to U_j$. Moreover, for every $i=1,\dots,N$ choose some subset $G_i$ of $\{1,\dots,25\}$ of seven indices. The $G_i$, $U_j$ and $\sigma_j$ are known to everyone beforehand. We also need to fix for each $j$ and the set $U_{j}=\{i_1,i_2,i_3\}$, three sets $T_1,T_2,T_3$, subsets of cardinality 4, of $G_{i_1}$, $G_{i_2}$ and $G_{i_3}$ respectively, such that $T_i\cap T_j$ is either empty or equal to $T_i$.

Now given $X\in C^{25}$ (any possibility of the colors of the girls) set $$i_0(X)=i_0=\min\{i: \# \{X_k, k\in G_i\}=1\}$$ Since there are four colors and 25 girls, necessarily there is a set of seven girls with the same color, and so $H=G_{i_0}$ is the one of these sets with the minimal index. All boys know the colors of the hats of the girls, so $H$ is known to the boys, and their decision can be codified by the following function $B:C^{25}\to C^n$ given by $$B(X)_j=\left\{ \begin{array}{ll} (\sigma_j)^{-1}(i_0(X))& \text{if }i_0(X)\in U_j\\ c &\text{if } i_0(X)\notin U_j\end{array}\right.$$

On the other hand the girls take the decision in two steps: First, they determine one boy $j_0$ such that $i_0(X)$ is in $U_{j_0}=\{i_1,i_2,i_3\}$, if all the boys have the wrong answer. Since for the subsets of cardinality 4 $T_1,T_2,T_3$, of $G_{i_1}$, $G_{i_2}$ and $G_{i_3}$ respectively, $T_i\cap T_j$ is either empty or equal to $T_i$, we obtain that for at least one of the sets $T_i$, all girls in that set have the same color. So they choose their colors such that for each $T_i$ the four girls choose different colors (which are already determined previously for each $j_0$), and so at least one girl has the right answer.

${\bf Final Comments:}$

This is the strategy I understood from Barto's answer and comments. It remains to prove that the girls can choose a boy with $j_0$ such that $i_0(X)$ is in $U_{j_0}=\{i_1,i_2,i_3\}$, if all the boys have the wrong answer (It seems to me to be equivalent to the first lemma of barto).

In fact, if there is at least one boy with color $Y_j=c$, they set $j_0=\min\{j:\ Y_j=c\}$. Then, if the boy is wrong, necessarily $i_0(X)\in U_{j_0}$, by the definition of $B$. On the other hand, if no boy has color $c$, there is an inductive process (the girls should have a laptop to follow the process) starting from the set $J=\{i=1,\dots,N\}$ (or, equivalently $J=\{G_i:\ i=1,\dots,N\}$) and eliminating one of the $i$'s (one of the $G_i$'s) at each step, such that at the end we are left with three indices and $i_0$ is one of them (with three sets $G_i$ and $H$ is one of them).

Inductive step: If $\#J>3$, then take any subset of three elements, $\{i_1,i_2,i_3\}$. This subset is a $U_j$ for some $j$, and we eliminate the index $\sigma_j(Y_j)\in U_j$. Note that since we assume that no boy has the color $c$, the index $\sigma_j(Y_j)$ is well defined.

It is impossible that $i_0(X)=\sigma_j(Y_j)\in U_j$: If $i_0(X)\notin U_j$, then this is clear, and if $i_0(X)$ is in $U_j$, since the boy is wrong, $$ \sigma_j(Y_j)\ne \sigma_j(B(X)_j)=i_0(X). $$

So the inductive procedure yields a set of three indices such that one of them is $i_0$, necessarily it is a $U_j$, and we set $j_0=j$.

Finally a comment on the number 7 for the cardinality of the $G_i$'s (opposed to 10 suggested by Barto). If you have three sets $G_1,G_2,G_3$ of 7 elements, then

-if the intersection of the three sets has 4 or more elements, you can set $T_1=T_2=T_3$ a subset of 4 elements in the intersection.

-if the intersection of two sets say $G_1, G_2$ has 4 or more elements but $G_1\cap G_2\cap G_3$ has less than four, you can set $T_1=T_2$ a subset of 4 elements in the intersection of $G_1$ and $G_2$ and $T_3$ a set in $G_3\setminus (G_1\cap G_2)$ of four elements.

-If no intersection of two sets has 4 or more elements, take $T_1$ in $G_1\setminus G_2$, $T_2$ in $G_2\setminus G_3$, $T_3$ in $G_3\setminus G_1$, of four elements respectively.

$\endgroup$

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.