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