En cierto juego, $30$ bolas de $k$ diferentes colores se guardan dentro de una caja sellada. Sólo se le indica el valor de $k$ pero no el número de bolas de

Question

En cierto juego, $30$ bolas de $k$ diferentes colores se guardan dentro de una caja sellada. Sólo se le indica el valor de $k$ pero no el número de bolas de cada color . En base a esto, tienes que adivinar si es posible dividir las bolas en $10$ grupos de $3$ cada una, de forma que en cada grupo las tres bolas sean de distinto color. Su respuesta ha de ser sencilla $YES $ o $NO$ . Ganas o pierdes un punto según aciertes o no. ¿Para qué valores de $k$ puedes decir $NO$ ¿y estar seguro de ganar? ¿Para qué valores de $k$ se puede decir $YES$ y estar seguro de ganar? Justifique su solución .

Sólo puedo distinguir que si $k=2$ entonces PHP(Pigeon hole Principle) podemos decir $NO$ . El argumento sigue siendo trivial para $k=1$ . Ahora, no estoy entendiendo como podemos ser obvios al decir $YES$ . ¿Habrá una prueba rigurosa de lo mismo? ¿Son las únicas opciones posibles para decir $NO$ es para $k=1,2$ . Si es así, entonces es mi manera de decir $NO $ ¿puede considerarse una solución válida? Si no es así, ¿cuáles son los otros valores de $k$ ? No acabo de entenderlo. Puede que haya entradas similares sobre el mismo tema en este sitio, pero tampoco las encuentro...

Answer 1

Obsérvese que para cualquier combinación de $3n$ bolas, es posible dividirlas en $n$ grupos de $3$ cada uno con todas las bolas en cada grupo que tienen diferentes colores iff ningún color particular tiene más de $n$ pelotas.

Dirección "Sólo si": si un color tiene más de $n$ bolas, entonces al menos un grupo tendrá al menos dos bolas de este color.

Dirección "Si": demostrar por inducción.

Si $n = 1$ entonces tenemos $3$ bolas, y cada color tiene como máximo $1$ bola, así que podemos ponerlos todos en un grupo.

Supongamos que podemos agrupar cualquier combinación de $3n$ bolas en las que ningún color tiene más de $n$ pelotas. Supongamos que tenemos una combinación de $3(n+1)$ bolas de forma que ningún color tenga más de $n+1$ pelotas. Además, como máximo $3$ colores tienen más de $n$ bolas (porque de lo contrario ya habría más de $3n+3$ bolas sólo en estos colores). Por lo tanto, podemos elegir $3$ colores con más bolas, poner una bola de cada uno de ellos en el primer grupo, y obtener una nueva combinación de $3n$ bolas, donde ningún color tiene como máximo $n$ bolas, que pueden dividirse en grupos por inducción.

Así pues, la pregunta es equivalente a la siguiente: ¿para qué $k$ podemos garantizar que habrá un color que tenga al menos $11$ bolas, y para las que $k$ podemos garantizar que no habrá tal color.

Está claro que podemos garantizar que habrá tal color para $k = 2$ pero no puede por $k = 3$ (toma $10$ bolas de cada color).

También podemos garantizar que no habrá tal color con $k \geq 21$ (si un color tiene al menos $11$ bolas, luego el resto $20$ colores tienen como máximo $19$ bolas juntas, lo cual es imposible), pero no puede garantizar con $k = 20$ (tomar un color con $11$ bolas, y descanso $19$ colores con una bola cada uno).

Así, para $k \leq 2$ podemos decir "NO", porque $k \geq 21$ podemos decir "SÍ", y para todos los demás no podemos decir nada.