3 problemas muy interesantes (y aún sin resolver): tableros y fichas en líneas rectas.

El siguiente problema es un problema muy interesante aún sin resolver, que topé con él en uno de los numerosos libros de Martin Gardner sobre matemáticas recreativas. El problema principal es el siguiente:

Problema principal

Sobre un tablero de nxn casillas, ¿será siempre posible colocar 2n fichas de forma que nunca haya 3 en línea recta? (Entendiendo por línea recta cualquier línea recta, no solamente filas, columnas y diagonales de tablero).

Es decir, por ejemplo, estas 3 fichas en un tablero de 5×5 pese a no estar en la misma fila, columna o diagonal, también están en línea recta:

Por ejemplo, en la siguiente imagen que se mostrará a continuación, podemos ver una solución, de las muchas existentes, para cada uno de los valores de n=2 hasta n=12.

El caso n=2 es obvio, podemos colocar 2n fichas (4) sin que haya 3 en la misma recta.

Para n=3 también parece sencillo colocar 2n fichas (6) sin que haya 3 en la misma recta.

A medida que n aumenta, la cosa se va complicando:

En cualquiera de dichas soluciones se han colocado 2n fichas en cada tablero, y puedes comprobar que es imposible colocar una ficha adicional sin que se forme una línea recta entre 3 fichas. Antes de seguir, piénsalo. ¿Sabrías decir por qué?

Es obvio. Es imposible colocar más de 2n fichas en un tablero de nxn de forma que nunca haya 3 en línea recta, ya que el máximo número posible de fichas que podemos colocar en cada una de las filas y columnas es 2.

Actualmente se conocen soluciones para todos los tableros nxn, hasta n=26. Pero solo se ha demostrado que como mínimo es posible colocar n fichas en cualquier tablero nxn.

Si llevamos este problema también a la programación, es muy interesante el siguiente ejercicio: ¿Sabrías programar una pequeña aplicación que compruebe en un tablero de nxn con varias fichas sobre él (una matriz nxn con unos y ceros, por ejemplo), si existe alguna línea recta en dicho tablero con al menos 3 fichas?

Si sólo tuviésemos en cuenta filas, columnas y diagonales, el ejercicio sería sencillo. Pero cuando tomamos la línea recta en sentido estricto y permitimos también cualquier línea recta más allá de filas, columnas y diagonales, como la que vimos en el ejemplo inicial de la entrada, el problema pasa a hacerse más complicado, pues debemos pensar en todas las posibles rectas que existirían en función del tablero. 😉

En relación al problema inicial, cabe destacar que si restringiéramos la definición de línea recta solamente a filas, columnas y diagonales, la respuesta al problema es afirmativa y el problema estaría resuelto.

Un segundo problema similar:

Ahora vamos a ver un problema muy similar derivado del anterior también muy interesante:

En lugar de preguntarnos cuál es el máximo número de fichas que se pueden colocar en un tablero de nxn de manera que no haya 3 alineadas, preguntémonos lo siguiente:

¿Cuál es el mínimo número de fichas que pueden colocarse en un tablero de orden n de forma que, añadiendo una ficha más en cualquiera de las casillas vacías, podrá formarse siempre una línea recta de 3 fichas?

En este caso el problema tampoco está resuelto, ni siquiera si la definición de línea se restringe a columnas, filas y diagonales del tablero.

A continuación puedes ver las soluciones mínimas para n=3 hasta n=14 (no son soluciones únicas, hay varias) cuando tomamos la definición de línea en sentido estricto (línea en cualquier orientación):

Y también las soluciones de n=8, n=9 y n=10 cuando tomamos la definición de línea limitándonos a columnas, filas y diagonales.

Y a raíz de este problema surge un juego muy interesante apto para todos para jugar en un tablero de ajedrez, para de 2 a 4 jugadores. Por turnos, cada jugador colocará una ficha, todos del mismo color, en uno de los cuadrados del tablero. El objetivo del juego es evitar formar una línea recta con 3 de las fichas colocadas en el tablero, intentando que el oponente lo haga. En el momento que alguien la forme, perderá.

El juego es especialmente interesante cuando tenemos en cuenta la definición de línea recta en sentido estricto, es decir, vale cualquier línea recta además de las filas, columnas y diagonales (como la del primer ejemplo de la entrada). Es fácil formar una línea recta de 3 fichas y que ningún jugador la vea, en ese caso continúa el juego.

¿Aún más? Sí, un tercer problema similar:

Y un tercer problema similar podría ser el siguiente: ¿En qué tableros de nxn es posible colocar n fichas de modo que todas las distancias entre cada dos fichas sea distintas?

Por ejemplo, supongamos el tablero 3×3. Es sencillo encontrar hasta 3 soluciones (sin contar rotaciones, giros, o simetrías) en donde la distancia entre cada par de puntos es diferente. Dicho problema se limitaría a encontrar un triángulo con un vértice en cada punto que tuviera cada uno de los lados diferentes:

De igual forma, pueden encontrase 16 formas distintas de colocar 4 puntos en un tablero 4×4 de forma que la distancia entre cada par de puntos sea diferente, y 28 formas de colocar 5 puntos en un tablero de 5×5.

Sin embargo, para n=6 la solución es más complicada. Solo hay 2 soluciones:

Y para n=7, únicamente una. Es la siguiente:

Este tercer problema, sí está resuelto. Se ha demostrado que el tablero de orden 7 es el mayor para el que existe solución. Dicha solución es única.

La verdad es que los 3 son problemas muy curiosos, que me parecía interesante compartirlos. Espero que te hayan resultado interesantes.

Esta entrada participa en la Edición 9.4 del Carnaval de Matemáticas, que en esta ocasión organiza Gaussianos.

Opt In Image
¡Suscríbete!
¿Quieres suscribirte gratis y recibir nuevas entradas y más? ¡¡Gracias!!

 

 

1 Comment

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *