[size=115]Solución: La respuesta es [tex]n=11[/tex]. Notemos que para encontrar el valor máximo de [tex]n[/tex] debemos asegurar que para todos los casos es posible llenar el tablero con [tex]n+1[/tex] fichas de dominó. Por inspección vemos que el peor de los casos se da cuando se maximiza el número de casillas que no pueden ser ocupadas por dominós (que llamaremos casillas vacías). Este número es 12. Para probarlo procederemos por contradicción.
[center]
[/center]
· Supongamos que este número es menor que 12, en ese caso habrán a lo más 10 casillas vacías lo que quiere decir que hay al menos 13 dominós en el tablero. Como se muestra en la figura anterior esto es imposible ya que si colocamos las primeras 12 fichas de manera análoga a como se muestra, sería imposible poner a 13ª ficha, contradiciéndose con el enunciado.
· Antes de continuar se debe seguir ls siguiente regla "Dos casillas vacías no pueden estar juntas, de lo contrario podrían ser cubiertas por un dominó y ya no serían vacías".
· Ahora si este número es mayor que 12, habrán al menos 14 casillas vacías[/i] y a lo más 11 dominós. Dividamos el tablero en 4 subtableros de 3x3. Por el Principio del Palomar como hay al menos 14 [i]casillas vacías[/i] y 4 subtableros, podemos asegurar que en un subtablero habrán al menos 4 [i]casillas vacías. Coloreemos, el tablero de 3x3 como en la figura. Demostraremos que siempre las cuatro casillas vacías tendrán el mismo color.
[center]
[/center]
· Una casilla blanca comparte un lado con 3 casillas negras, luego la casilla vacía debería ser (para que tengan distinto color) una de las dos restantes se lado opuesto del tablero. Esta casilla negra comparte lado con otras dos casillas blancas, quedando imposibilitadas para ser casillas vacías todas las que están marcadas con rojo. De ahí quedan dos casillas contiguas y dos casillas vaciás que colocar, lo que es imposible.
[center]
[/center]
· Una casilla vacía negra, si está en el centro estamos listos pues comparte lado con todas las blancas. Si está en una esquina, esta comparte lado con 2 casillas blancas y para que elijamos con distinto color, debemos escoger una de las dos casillas blancas opuestas. En tal caso quedan imposibilitadas para ser casillas vacías todas las marcadas con rojo, y al igual que en el caso anterior nos quedan 2 casillas contiguas y dos casillas vacías que colocar, lo que es imposible. Luego las 4 casillas elegidas tienen el mismo color.
[center]
[/center]
· De lo anterior se puede decir, sin pérdida de generalidad por la posición del tablero de 3x3, que si las cuatro casillas vacías son blancas, se generan al menos dos casillas vacías contiguas a las blancas ya que no podían por sí solas ser ocupadas por dominós, pero a su vez dejan de ser vacías ya que comparten un lado con otras casillas vacías. en este caso el número de casillas vacías decrece 4, donde el número de casillas vacías ya no es mayor que 12. Ahora si las cuatro casillas son negras tenemos dos casos. Si hay una casilla vacía en el centro sin perdida de generalidad se generará al menos una casilla que no puede ser llenada por dominós, que está pegada a otra casilla vacía, esto quiere decir que estas ya no son vacías y su número decrece en al menos 2, es decir a lo más 12. Si las casillas negras están en los vértices al colocar un dominó en la cuadrícula, necesariamente va a quedar una casilla que no puede ser llenada (esto sin pérdida de generalidad). Luego pasa lo mismo que en el caso anterior decreciendo el número de casillas vacías en al menos 2, es decir a lo más 12. Llegando al fin a una contradicción.
[center]
[/center]
Por lo tanto el número máximo de casillas vacías que pueden haber es 12, es decir la cantidad máxima de dominós que siempre podemos colocar es 12, por lo que [tex]n=11[/tex].
[/size]
