Siempre hay una estrategia de este tipo, sin importar el número de colores, cuando $n$ es suficientemente grande (dependiendo del número de colores). Consulte la parte inferior de esta respuesta para obtener un valor explícito de $n$ que funciona. Para $4$ colores, da $n = 4^{144}$ .
Dejemos que $k$ sea el número de colores. La idea es que el niño pueda, de antemano, hacer $k$ afirmaciones sobre los colores del otro grupo, de tal manera que en cada escenario exactamente una afirmación sea verdadera, y asignar cada afirmación a un color. Un ejemplo sencillo es, cuando Tom hace la $k$ afirmaciones obvias sobre el color de Jade y las asigna a, bueno, esos colores. Cuando el experimento comienza, las chicas pueden asumir entonces que la afirmación correspondiente al color de Tom es falsa. (De hecho, si Tom acierta, ya no importa nada). En el ejemplo, pueden suponer que el color de Jade no es el mismo que el de Tom. Utilizaremos afirmaciones más interesantes.
Por el principio de encasillamiento, entre un grupo de $1+(b-1)k$ chicas, hay un grupo de $b$ que tiene el mismo color. Arreglar $b$ por el momento y supongamos $n \geq 1+(b-1)k$ . (La elección de $b$ dependerá de $k$ solamente). Fijar un grupo de este tipo $G$ de $1+(b-1)k$ chicas. Los niños se ponen de acuerdo sobre una enumeración $G_1, \ldots, G_{\binom{1+(b-1)k}{b}}$ de los subconjuntos de tamaño $b$ de $G$ .
La clave es que, dado un grupo de $k$ Las niñas que pueden suponer que tienen el mismo color, pueden adivinar cada una un color diferente, para que al menos una de ellas acierte. El problema es que las chicas nunca pueden saber qué grupo de $k$ Las chicas tienen el mismo color, pero los chicos pueden limitar las posibilidades:
Lema. Dada una información sobre los colores de las chicas, que toma valores en un conjunto de tamaño $N$ los chicos pueden limitar el número de valores que puede tomar para $k-1$ siempre que haya al menos $\binom N{k-1}$ chicos.
Formalmente, si $C$ es el conjunto de colores, y dada una función $f : C^n \to I = \{1, \ldots, N\}$ conocido por los chicos y chicas, existe una estrategia que lleva $\binom N{k-1}$ chicos y hace que, si todos esos chicos adivinan mal, entonces hay un subconjunto $J \subseteq I$ de tamaño $k-1$ tal que $f(x) \in J$ . Donde $x \in C^n$ denota el vector de los colores de las chicas.
Prueba. En el caso $N = k-1$ (o más pequeño), esto está claro: basta con que un chico mapee cada elemento de $I$ a un color diferente. La cuestión es que esto es posible para las grandes $N$ . Cuando Tom elige $k-1$ índices $i_j \in I$ , mapea cada grupo $i_j$ a un color, y la declaración " $f(x)$ no es ninguno de los $i_j$ " a la $k$ color, entonces las chicas pueden asumir que $f(x) \neq i_j$ para algunos $i_j$ o que $f(x)$ es uno de los $i_j$ dependiendo del color de Tom. En este último caso, estamos contentos: hemos reducido las posibilidades de $f(x)$ a $k-1$ números. Necesitamos una estrategia para el primer caso, en el que las chicas sólo pueden excluir uno de los $k-1$ índices que eligió Tom, y no tenemos control sobre cuál será. Basta con encontrar subconjuntos $U_j$ de tamaño $k-1$ de $I$ tal que, para cada elección de elementos $u_j \in U_j$ el complemento $U - \cup_j\{u_j\}$ tiene como máximo la cardinalidad $k-1$ . Por supuesto, esto es posible, simplemente tome todos los subconjuntos de $I$ de tamaño $k-1$ . Así, siempre que haya al menos $\binom{|I|}{k-1}$ chicos, las chicas pueden asumir que hay un subconjunto $J \subseteq I$ de tamaño $a \leq k-1$ , de tal manera que $f(x) \in J$ . Por ejemplo, podemos suponer que $a = k-1$ las chicas siempre pueden hacer $J$ más grande de una manera que acordaron de antemano. $\square$
Dejemos que $I = \{1, \ldots, \binom{1+(b-1)k}{b}\}$ . Los chicos pueden ahora hacer afirmaciones sobre qué grupo $G_i$ tiene el mismo color (donde se elige el grupo con menor índice si hay varios). Llama a ese grupo (con el índice más pequeño) $H$ . Este es nuestro $f(x)$ . Así, siempre que haya al menos $\binom{|I|}{k-1}$ chicos, las chicas pueden asumir que hay un subconjunto $J \subseteq I$ de tamaño $k-1$ , de tal manera que $H = G_j$ para algunos $j \in J$ . Este $J$ es conocido por todas las chicas, mirando los colores de los chicos.
Ahora que hemos limitado las posibilidades de $H$ a $\{G_j : j \in J \}$ En este caso, nos gustaría aplicar nuestra idea clave a cada uno de estos grupos: en cada grupo, las chicas dicen todos los colores posibles. El problema es que esos grupos no son necesariamente disjuntos. Pero los niños saben cómo resolverlo:
Lema. Dados los enteros $a,k \geq 1$ y $b \geq k+(a-1)(k-1)$ , entonces dado $a$ establece $G_1, \ldots, G_a$ de tamaño $b$ existe $m \leq a$ y un número finito de conjuntos disjuntos $T_1, \ldots, T_m$ de tamaño $k$ de manera que cada $G_j$ contiene algunos $T_i$ .
Prueba. Por inducción en $a$ . Para $a=1$ esto es trivial. Sea $a>1$ y supongamos que cada intersección $G_a \cap G_i$ es como máximo de tamaño $k-1$ . Entonces podemos seleccionar $k$ elementos de $G_a$ que no están en ningún otro $G_i$ , tomarlos para formar un $T_j$ y proceder por inducción. Si algún $|G_a \cap G_i| \geq k$ , elija $k$ elementos en su intersección y que formen un $T_j$ . Este $T_j$ funciona para cualquier $G_l$ que contiene esos $k$ elementos. Elimine estos elementos de todos los $G_l$ y proceder por inducción. $\square$
El lema implica, con $a = k-1$ que existen grupos disjuntos $T_j$ de $k$ niñas, de manera que las niñas puedan asumir cada $G_j$ contiene un $T_j$ . (En la práctica, las chicas deben estar de acuerdo con esta elección de $T_j$ para cada posible $J \subseteq I$ de tamaño $k-1$ .) En particular, existen grupos disjuntos de $k$ chicas, al menos una de las cuales está contenida en $H$ . Es decir, al menos uno de ellos está formado por chicas del mismo color. En cada grupo $T_j$ , deja que las niñas adivinen todos los colores diferentes. Entonces, al menos una chica adivina correctamente (a menos que uno de los chicos adivine correctamente).
Concluimos que $$n = \max \left(\binom{|I|}{k-1} , 1+(b-1)k \right) $$ es suficiente, cuando $|I| = \binom{1+(b-1)k}{b}$ y $b = k+(a-1)(k-1)$ y $a = k-1$ . Utilizando el límite $\binom xy \leq x^y$ y la estimación $b \leq k^2$ y $1+(b-1)k \leq k^3$ conseguimos que $$n \geq \left( (k^3)^{k^2}\right)^{k} = k^{3k^3}$$ es suficiente.
