martes, 17 de junio de 2008

Boggle cervantino

Hoy, una idea intrigante de Pablo Coll: ¿Cuál será el menor boggle donde entre el Quijote completo?

Precisemos: un boggle es un tablero cuadrado donde cada casilla contiene una letra. Buscamos el menor en el que se puedan ir leyendo todas las letras del Quijote, saltando de una letra a otra que esté vecina ortogonal o diagonalmente. A los efectos del problema ignoraremos acentos, signos de puntuación y mayúsculas (aunque bien podrían incluirse).

Desde ahí, Pablo generaliza algo temerariamente: imagina un Boggle de Babel, donde pueda leerse cualquier texto finito. ¿Existirá? ¿Qué tamaño tendría que tener?

4 comentarios:

Markelo dijo...

Uf... de solo pensarlo se me marean las neuronas.

Un objetivo más modesto podría ser:

¿Cuál es el boogle mínimo que permite leer todas las palabras posibles de tres letras?

AAA, AAB, AAC, ... ZZX, ZZY, ZZZ.

Y por supuesto, generalizarlo luego para palabras de N letras

luisito dijo...

Digamos que el boggle tiene C casillas. Veamos cuantas frases de N letras podemos armar.

Para la primera letra podemos elegir cualquiera de las C casillas. De ahi en mas para cada letra siguiente tenemos 8 direcciones posibles hacia donde ir (las ocho vecinas). Asi que en total tenemos C*8^(N-1) frases que podemos encontrar en el boggle.

Cuantas frases de N letras hay en total? Serian 26^N.

Aca vemos cual es el problema. Para cualquier tamanio de tablero, va a haber un numero N grande para el cual
26^N > C*8^(N-1). Va a haber frases que no se encuentran en el Boggle. Asi que decile a Pablo que el Boggle de Babel no existe (o debe ser infinito).

El Quijote completo tiene muchas letras. Asi que en la desigualdad de arriba N seria muy grande. Por lo que C va a tener que ser grande y vamos a necesitar muuuuuuuchas casillas.

Manu dijo...

ja, iba a postear lo mismo que luisito acerca del Boggle de Babel.

luisito tenes blog?

luisito dijo...

No Manu. No tengo blog.