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.
Best Answer
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.