Un tablero (casi) cubierto con piezas

Ya hay solución para el décimo desafío matemático con el que EL PAÍS celebra el centenario de la Real Sociedad Matemática Española. María López Valdés, de la empresa Bit&Brain Technologies propuso el problema (ver vídeo de la izquierda) y lo resuelve ahora (vídeo de la derecha): es imposible cubrir el tablero dejando únicamente una casilla vacía y el mínimo número de huecos que podemos dejar es de 17. El ganador de una biblioteca matemática como la que entrega cada semana EL PAÍS ha sido en esta ocasión Salvador Fuster Peiró, de Oliva (Valencia). Este domingo, en el quiosco, por 9,95 euros con el periódico, Mapas del metro y redes neuronales, de Claudi Alsina.

Esta semana el desafío ha resultado más difícil y, con aproximadamente las mismas visitas que en ocasiones anteriores, se han recibido 420 respuestas, el mínimo hasta ahora. Suponemos que es una consecuencia lógica de nuestro interés por plantear retos diversos. También ha sido difícil valorar las respuestas. Un 7% daban resultados erróneos, un 30% el resultado correcto con demostraciones inobjetables (la mayoría mediante distintas versiones de la idea mostrada en el vídeo, alguna usando programación entera u otros métodos), y un 63% presentaban la solución correcta con argumentos a los que se les podía poner algún pero. En términos de examen: no eran de 10 pero, ¿merecían aprobar?

Considerando por un lado que en el planteamiento del problema no se había pedido explícitamente una demostración del segundo apartado, y por otro que tampoco se trata de convertir los desafíos en un juego de azar, la decisión ha sido que entrasen en el sorteo todas aquellas soluciones correctas que habían hecho un esfuerzo por entender qué pasaba. Destacamos entre ellas la de Alejandro Apezteguía Torres quien, tras dar una fórmula para el número mínimo de casillas que habría que dejar libres en un tablero nxn, nos pide perdón por imitar a Fermat y decir "¡He encontrado una maravillosa demostración de este hecho, pero el espacio restante al margen es demasiado pequeño para incluirla!".

Muchas de las propuestas de solución presentan argumentos que dan la respuesta correcta para tableros 9x9 o para tableros nxn con n impar, caso en que la idea del vídeo siempre funciona. Pero, como sucede con la fórmula de Alejandro, no siempre son argumentos válidos en general, como vamos a intentar mostrar con algún ejemplo.

Bastantes lectores han demostrado que al llenar una franja 2x9 se dejaban al menos 2 huecos, y luego han observado que teníamos 4 franjas 2x9 más una línea superior vacía. Podemos probar esta idea en un tablero 6x6 (véase en el pdf adjunto el desarrollo de la cuestión).

Incluimos también aquí la solución y la demostración presentada por el ganador de la semana, que coincide básicamente con la propuesta por María López:

PRIMERA CUESTIÓN

Si pintásemos el tablero con 2 colores, de manera que cada columna fuese de un color diferente a la de la columna su lado, tendríamos un total de 5 columnas de un color, que denominaremos color A, y otras 4 columnas del otro color, que denominaremos color B. Es decir, tendríamos 5x9=45 casillas de color A y 4x9=36 casillas de color B.

Ahora bien, las piezas poseen una forma particular, de modo que al colocarlas en cualquier posición válida del tablero, ya sea en horizontal o en vertical, ocupan 2 casillas de color A y 2 casillas de color B.

Por tanto, dado que únicamente disponemos de 36 casillas de color B, nunca podremos colocar más de 36/2=18 piezas, pues cada pieza ocupa 2 casillas de cada color.

Por tanto, queda demostrado que es imposible cubrir el tablero dejando únicamente una casilla vacía.

SEGUNDA CUESTIÓN

El número mínimo de casillas que quedan libres es precisamente 17, ya que únicamente podremos colocar 16 piezas en el tablero.

Para comprobar este hecho colorearemos de nuevo el tablero, pero en este caso lo haremos usando 4 colores, que llamaremos A, B, C y D. Lo haremos de la siguiente forma:

A B A B A B A B A

C D C D C D C D C

A B A B A B A B A

C D C D C D C D C

A B A B A B A B A

C D C D C D C D C

A B A B A B A B A

C D C D C D C D C

A B A B A B A B A

Como podemos observar hay 5*5=25 casillas coloreadas con A, 5*4=20 casillas coloreadas con B, 4*5=20 casillas coloreadas con C y 4*4=16 casillas coloreadas con D.

Ahora bien, con la distribución de colores realizada, al colocar una pieza en el tablero, lo que ocurrirá es que, independientemente de la forma de colocar la pieza, cada casilla que ocupa nuestra pieza tendrá un color diferente.

Dado que el número de casillas coloreadas con D es únicamente 16 y como al colocar una pieza, seguro que una de las casillas que ocupa posee color D, resulta que únicamente podremos colocar 16 piezas como máximo y como es sencillo encontrar ejemplos en los que se pueden colocar 16 piezas en total, resulta que el número de casillas que deberemos dejar sin ocupar como mínimo es 81 - 16*4 = 17.

Felicidades a los acertantes. Este jueves plantearemos un nuevo problema.

Un tablero con casillas libres

Cómo rellenar con piezas un tablero