El objetivo (si es que es posible lograrlo) es colocar las cifras de tal modo que se pueda leer, en orden, cualquier secuencia finita de dígitos (no importa qué secuencia sea, no importa de qué longitud sea).
Para leer las cifras comenzamos por una casilla que contenga el primer número de la secuencia y luego nos vamos moviendo a través de casillas que sean vecinas en horizontal, vertical o diagonal (como el movimiento del rey en ajedrez). Se puede pasar más de una vez por una misma casilla, pero sólo podremos movernos entre casillas que contengan cifras (es decir, no se puede pasar por casillas vacías). Para leer dos cifras iguales consecutivas (como sucede por ejemplo en 4338) el recorrido deberá visitar dos casillas diferentes que sean vecinas y tengan el mismo número (el número 3 en el caso del ejemplo).
Si quisiéramos leer secuencias formadas solamente por los números 0 y 1 entonces el objetivo sería realizable gracias a este tablero:
El tablero anterior permite leer cualuqier secuencia de ceros y unos. Por ejemplo, vemos aquí cómo leer la secuencia 0, 0, 0, 1, 1, 1, 0:
El objetivo es también posible para secuencias formadas por los dígitos 0, 1 y 2. El siguiente tablero permite leer cualquier secuencia de este tipo:
Y el siguiente permite leer cualquier secuencia formada por los dígitos 0, 1, 2 y 3:
Las preguntas son:
1. ¿Existe un tablero que permita leer cualquier secuencia formada por los dígitos 0, 1, 2 y 3?
2. ¿Cuál es el máximo valor de n para el cual existe un tablero que permite leer todas las secuencias formadas por los números entre 0 y n?
3. En caso de que fuera posible hacerlo para n = 9 ¿cuál es el tablero más pequeño que lo permite? (Por "el más pequeño" entendemos el tablero de menor área total y, a igualdad de áreas, el que tenga la menor cantidad de casillas ocupadas.)
Nota: Este problema está inspirado en un desafío llamado El Rey de Pi. La relación entre ambos es que si hubiera un tablero para n = 9 entonces en él podría leerse "completo" el número Pi (es decir, podrían leerse, en orden, tantas cifras de Pi como se quisiera).
5 comentarios:
Yo diría que el tope es 2, es decir, 3 dígitos, el del ejemplo, porque si agrego el 3, 4 dígitos, no voy a encontrar forma de que todos los números queden vecinos entre sí. Que es lo que se necesitaría.
Me recuerda al desafío del mapa de colores. En él se plantea que con 4 colores puede pintarse cualquier mapa de manera que ninguna de sus provincias o estados vecinos tengan el mismo color. Traten sino de encontrar uno en que no se pueda.
Estimado Pitógarras,
Para 0, 1, 2 y 3 (4 dígitos) sí es posible, como ahora se puede ver en la entrada.
Saludos,
Cierto. Tal vez eso se logre por la posibilidad de ir de vértice en vértice. En el planteo de los 4 colores se aclara que dos segmentos son vecinos cuando comparten algo mas que un punto. Pero esto como comentario al márgen, porque realmente no estoy seguro de que sean comparables, siquiera por oposición, uno y otro planteo.
Lo que sí veo en este problema es que para lograr un esquema del tipo que se solicita, la condición primera es que cada una de las casillas que se agreguen con un nuevo valor esté conectada con otra casilla del mismo valor y con al menos una casilla con cada uno de los otros valores existentes.
Estoy seguro que esto no puede lograrse con mas de 8 dígitos ya que cada casilla tiene un máximo de 8 posibles vecinos: 4 lados y 4 vértices. Y como dijimos, debe existir además para cada casilla una casilla vecina que tenga el mismo valor. Con lo cual eso acota las posibilidades a 7 posibles vecinos de distinto valor para cada casilla.
Veré si llego a algo mas, pero por el momento sólo puedo asegurar que no será posible encontrar una solución con 9 o más dígitos.
PD: Una ayudita más no me vendría mal.
El máximo posible es de 4 dígitos. El problema puede extenderse a figuras con N vecinos y la solución será N/2 (en caso de cantidad impar de vecinos, como por ejemplo un triángulo en que se excluya la vecindad de los vértices, la solución estará dada por la parte entera del resultado de la división). Podemos incluso imaginar figuras de 3 o mas dimensiones y la solución estará siempre dada por N/2.
Pregunta:
¿Cuál es el máximo de vecinos iguales a si mísma que puede tener una figura plana y regular? ¿De qué figura/s se trataría?
Defino para esto que dos figuras son vecinas si comparten un segmento de borde común, no sólo un punto o vértice; y que no puede haber superposiciones entre ninguna de las figuras.
Publicar un comentario