Caminata marciana

Ésta es el video de mi charla en el Tercer Encuentro por Martin Gardner y Jaime Poniachik:



Y ésta es la transcripción aproximada:

En esta ocasión voy a invitarlos a pasear por Marte... ¿Qué es Marte? "Un planeta" me responderán ustedes, con toda razón. Pero para nosotros el mapa de ese planeta será un cuadriculado ilimitado que sigue infintamente en todas direcciones.

Un camino en ese cuadriculado será cualquier recorrido que comience en una casilla y termine en otra (todos nuestros caminos tendrán un comienzo y un final, ninguno seguirá indefinidamente), que pase de cada casilla a otra que sea vecina en horizontal, vertical o diagonal, y que nunca pase dos veces por la misma casilla.

En la siguiente figura vemos un ejemplo de camino (el circulito rojo indica su comienzo y la flecha indica el final).

Una vez que hemos dibujado el camino, en las casillas visitadas por él (y sólo en esas) vamos a colocar números. Los números serán colocados en el mismo orden en que las casillas fueron visitadas por el camino y de acuerdo con la siguiente regla: en cada casilla va el número que indica la cantidad de números que, hasta ese momento, hay alrededor de la casilla.

En el ejemplo anterior, la primera casilla (la del circulito) no tiene todavía número alrededor, de modo que allí va un 0 (la primera casilla siempre tendrá un 0).

La siguiente casilla tiene ahora un número a su alrededor (el 0 que acabamos de poner), de modo que en la segunda casilla va un 1. La siguiente tendrá un 2, y así sucesivamente. El camino, con todos los números colocados se ve así:

Éste es el mecanismo básico: dibujamos un camino y colocamos los números según la regla que acabamos de enunciar. A partir de este mecanismo podemos plantear una serie de desafíos.

Desafío 1: Dibujar un camino en el que aparezcan, al menos una vez, todos los números del 0 al 8 (es claro que el mayor número que puede aparecer es el 8).

Un ejemplo es el siguiente:

Que, al colocar los números, se ve así (he marcado en amarillo los números del 0 al 8 para que se destaquen).

Como se ve, hay muchos números adicionales (todos los que quedaron en blanco). El verdadero desafío es logar que la suma de esos números adicionales sea la mínima posible.

Desafío 1 (completo): Dibujar un camino en el que aparezcan, al menos una vez, todos los números del 0 al 8 de modo tal que la suma de los números adicionales sea la mínima posible. En el ejemplo anterior la suma es 36, esa solución puede mejorarse.

Desafío 2: Dibujar un camino en el que se forme la siguiente distribución de números, de modo tal que la suma de los números adicionales sea la mínima posible.

El interés de esta disposición de números consiste en que se trata de un cuadrado mágico: las tres filas, las tres columna y las dos diagonales suman 12.

Desafío 3 (cráteres): Un cráter es el borde de un cuadrado de n x n con sus casillas (sólo las casillas del borde) ocupadas por números todos iguales entre sí. Por ejemplo, el siguiente es un cráter de 4 x 4 con 3's:

Como antes, el objetivo es encontrar un camino que forme diferentes cráteres de modo tal que la suma de los números adicionales sea la mínima posible. Algunas marcas que he obtenido son las siguientes:

Cráter de 3 x 3 con 2's: es imposible, es decir, no existe un camino que pueda formar un cráter así. A quienes les interese los desafíos de este tipo, pueden intentar demostrar esta imposibilidad.

Cráter de 3 x 3 con 3's: Rodolfo Kurchan, organizador del encuentro, encontró una solución de suma 8:

0

1333

13 31

2333

  23

Claudio Meller, en este enlace, también aporta el dibujo de una solución de suma 8.

Cráter de 3 x 3 con 4's: en un mensaje privado Rodolfo Kurchan me ha informado que encontró una solución de suma 8, pero no envía el dibujo.

Cráter de 3 x 3 con 5's: en su mensaje privado Rodolfo Kurchan me ha informado que encontró una solución de suma 15, pero tampoco tengo el dibujo de ese camino.

Cráter de 3 x 3 con 6's: es imposible, como dije antes, quienes estén interesados por desafíos de este tipo pueden intentar demostrar esta imposibilidad.

Cráteres de otros tamaños: evéanse más abajo algunas soluciones.

Existen otras disposiciones interesantes de números que también pueden plantearse como desafíos, pero lo haré más adelante, en otras entradas.

Quienes encuentren soluciones que quieran transmitir, o nuevos desafíos para plantear a partir de este mecanismo, pueden hacerlo en los comentarios a esta misma entrada. Una manera de de escribir una solución sin recurrir a un dibujo sería indicar las direcciones en que el camino se va desplazando (N = norte o arriba, NO = noroeste, O = oeste o izquierda, etc.) Desde luego, no es relevante la posición de la casilla inicial. Por ejemplo, el camino del primer ejemplo se escribiría así: SE, O, NE, SE, N, N.

Muchas gracias.

Nota: Después de haber preparado esta charla, googleando en busca de ideas similares que alguien hubiera podido tener previamente, descubrí en este enlace un mecanismo más o menos similar, aunque no igual, al que he contado aquí. Como se puede ver en el enlace, también se parte de un camino en el que se escriben números, pero en este otro caso, se pone (un poco arbitrariamente) primero un número 1 y luego se van sumando los números que quedan alrededor. Los desafíos, además, son diferentes. No obstante las diferencias, me pareció correcto mencionar la similitud de ideas.

Actualizaciones:

Cuadrado mágico (24.10.12): Claudio Meller envía una solución que da una suma de 28 para el desafío de dibujar el cuadrado mágico. Su solución puede verse en el archivo que se descarga desde este enlace. Rodolfo Kurchan tiene una solución que da una suma de 26, que es la siguiente:
 121

15072

16424

31831

2341

Y que mejora a 23:
  121

15072

16424

31831

 241

(En los comentarios puede verse todavía otra mejora.)

Nuevo desafío (24.10.12): Rodolfo propone hallar un camino que dibuje los números 012345678 en ese orden (siempre de tal modo que la suma de los números adicionales sea la mínima posible). Rodolfo envía esta solución, que suma 20:
   2221111

0123456782

  12  1121

Pero Claudio Meller, en este enlace, aporta una solución con una suma de 19.

Cráteres (24.10.12): Claudio Meller envía una solución del 4x4 con 2's que da una suma de 4, el dibujo en este enlace y envía el dibujo de una solución de suma 12 para el de 4x4 de 3's, en este enlace.

Soluciones de Rodolfo Kurchan para cráteres:
...........................
4x4 dos = 5 (mejorada por la solución de Claudio Meller)

0  1

12222

 2  2

 2  21

 2222

   2

........................... 

4x4 tres = 12 (iguala la de Claudio Meller)

0   2

133332

13  31

 3123

13333

    1

...........................

4x4 cuatros = 20

021 1

144441

 4134

 42541

 44441

  1

........................... 
4x4 cincos = 32

 1 1

1 1 031

1 55551

 154151

 15 3541

 155551

  1111
...........................

Resumen de las mejores marcas hasta ahora:

Números del 0 al 8 al menos una vez cada uno: suma 8 (de Marcos Donnantuoni, puede verse la solución en los comentarios a la entrada, Marcos conjetura que es óptima).

Cuadrado mágico: suma 22 (de Marcos Donnantuoni, puede verse la solución en los comentarios).

Números del 0 al 8 en línea (desafío propuesto por Rodolfo): suma 16 (solución de Marcos Donnantuoni, puede verse en los comentarios).

Cráter de 3x3 con 3's: suma 8 (Rodlfo Kurchan y Claudio Meller, pueden verse en la entrada).
Cráter de 3x3 con 4's: suma 8 (Rodlfo Kurchan, confiamos en su palabra).
Cráter de 3x3 con 5's: suma 15 (Rodlfo Kurchan, confiamos en su palabra y Claudio Meller que sí envía un dibujo, que puede verse en los comentarios).

Cráter de 4x4 con 2's: suma 4 (Claudio Meller, puede verse en la entrada).
Cráter de 4x4 con 3's: suma 12 (Rodlfo Kurchan y Claudio Meller, pueden verse en la entrada).
Cráter de 4x4 con 4's: suma 20 (Rodlfo Kurchan, puede verse en la entrada).
Cráter de 4x4 con 5's: suma 32 (Rodlfo Kurchan, puede verse en la entrada).