jueves, 26 de junio de 2008
Hace unos días, Marcos, en uno de sus blogs, comentaba una pregunta de Pablo Coll:
¿Cual será el menor Boogle que permita leer El Quijote completo? Y remataba la cosa imaginando un Boogle de Babel. Pueden leer el resto en Juegos de ingenuo.
A manera de variante más manejable, se me ocurrió preguntar por el boogle mínimo que permita leer todas las palabras posibles de 3 letras (AAA, AAB, ... YZZ, ZZZ) y, por supuesto, extenderlo luego a palabras de N letras.
Aunque es más sencillo, la cosa dista de resolverse facilmente con papel y lápiz.
Por eso, para Pequeños Enigmas propongo una variante más acotada aun pero que también se complica bastante.
Les recuerdo que el Boogle se trata de un tablero cuadrado con una letra (o dígito) por casilla. Las palabras (o números) se forman pasando de una casilla a otra vecina en forma ortogonal o diagonal. Dentro de una misma palabra (o número) no se puede utilizar dos veces la misma casilla.
Lo que propongo es encontrar el menor boogle que permita acomodar los números de 1 a N de forma tal que se puedan leer las N^N combinaciones de N dígitos. A igualdad de tamaño es mejor el tablero cuadrado que deja más casillas sin utilizarse.
Por ejemplo, con N = 3 podríamos hacer
Ustedes comprobarán rápidamente que se pueden leer los 27 números de tres cifras posibles.
¿Y con N = 4? Pensé que sería fácil y armé el siguiente tablero:
Pero en cuanto me puse a comprobarlo, me di cuenta que no pueden lograrse el 1232 ó el 1323.
¿Se puede en 4x4? Si. y seguramente ustedes encontraran alguna solución posible.
Con N = 5 no fui capaz de lograrlo en 5x5. ¿Se podrá? ¿Cuál será el mejor tablero?
A partir de N=6 la cosa se vuelve complicada y a partir de N=8 ya es obvio que no alcanzan con 8 repeticiones de cada dígito. Tal vez alguno se anime.
Suscribirse a:
Enviar comentarios (Atom)
11 comentarios:
Una variante "ingenua": lograr que el boggle "deje afuera" la mayor cantidad de palabras posible.
Una especie de boggle antisocial.
1-1-2-2
1-4-1-2
4-3-2-3
4-4-3-3
Este funciona para los todas las cadenas de 4 números.
es exactamente la solución que yo tenía.
¿Y con n = 5?
Pues este último intento tampoco vale.De las 256 combinaciones posibles faltan sólo 4:
1-3-3-1 y 3-1-1-3
2-4-4-2 y 4-2-2-4
Tengo la desagradable impresión de que es imposible para n > 3
Bueno... ya estoy por batir mi propio record de meteduras de pata consecutivas...
para colmo, mi solución no es exactamente igual a la mostrada como dije... de todos modos, tampoco se puede lograr esos números con ella.
Volvemos entonces a la pregunta original:
¿Cuál es el menor tablero cuadrado que permite acomodar todos los números?
A igualdad de tamaño es mejor el que deja más casillas sin usar.
Para las cadenas de 4 números basta el de 5x5:
1-1-2-2-4
1-4-1-2-4
4-3-2-3-1
4-4-3-3-1
#-#-#-#-#
con cinco casillas sin usar,marcadas con #
Sorprendentemente he encontrado uno de 5x5 donde se dejan 9 casillas sin usar:
#-#-#-4-#
#-3-2-3-4
3-2-3-4-1
#-1-2-1-4
#-#-1-2-#
No es posible dejar más casillas sin usar, ya que 9 casillas + 16 numeros = 25
Buenísimo.
Aun me falta revisarlo, pero a esta altura confío más en tu palabra que en mis neuronas.
He confeccionado un pequeño programa que los comprueba, y también intenta solucionarlos.
Aquí está:
Boggle.rar
No es gran cosa ni está muy pulido, pero menos da una piedra.
Le he corregido un fallo importante y lo he hecho un poco más amigable:
Boggle2.rar
Gracias... lamentablemente parece que para ejecutarlo debería instalar .Net (o algo así es lo que entiendo)
Ya lo probaré en otro momento con más tiempo.
Publicar un comentario