Cómo resolver Mínimum Máximum

Uno de los acertijos más difí­ciles del PQRST13 fue el problema 10: Mí­nimum Máximum. De hecho solo 36 participantes de 146 obtuvieron algún puntaje, y solo 9 lograron el máximo.

Les recuerdo el enunciado:

Coloque letras en una cuadrí­cula de 6x6 para que se lean las palabras MAXIMUM y MINIMUM tantas veces como sea posible. Cada palabra debe ser obtenida pasando de una letra a otra en forma vertical, horizontal o diagonal. Cada letra puede ser usada más de una vez en la misma palabra.

La principal dificultad que se le presentaba a uno cuando atacaba este problema es: ¿Cómo hacer para contar todas las posibles maneras de leer las palabras sin que se escape ninguna?

En efecto es una tarea formidable... a menos que uno encuentre un atajo.

Homero fue quien, entre nosotros, encontró un método rápido y efectivo para contarlas y generosamente lo compartió con todos.

Por ejemplo, veamos la siguiente cuadrí­cula:

M M M M M M
U M U M U M
I M A M I M
N X I X N I
I M A M I M
U M U M U M

Intenten contar la cantidad de veces que aparece la palabra MINIMUM antes de seguir leyendo.

Explica Homero:

Se construye una tabla poniendo un 1 donde hay una M, y un 0 donde no:

1 1 1 1 1 1
0 1 0 1 0 1
0 1 0 1 0 1
0 0 0 0 0 0
0 1 0 1 0 1
0 1 0 1 0 1

Como la letra que viene antes de la M en MINIMUM es la U, hay que construir otra tabla que en el lugar donde hay una U ponga la suma de los valores que rodean a esa posición en la tabla anterior (poniendo un 0 donde hay otra letra):

0 0 0 0 0 0
4 0 7 0 7 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
2 0 4 0 4 0

El número en cada lugar de esta tabla representa cuántas veces se puede escribir UM partiendo desde ese lugar.

Se repite el procedimiento, ahora con las letras M, I, N, I, y finalmente la M, siempre sumando con la tabla anterior.
Siguiendo este método se llega, con la M final (la primera de la palabra) a la siguiente tabla:

00 00 00 00 00 00
00 34 00 77 00 77
00 34 00 77 00 154
00 00 00 00 00 00
00 34 00 77 00 154
00 34 00 77 00 77

Aquí­ cada número representa cuántas veces se puede escribir MINIMUM partiendo desde la casilla correspondiente, por lo tanto, para saber el total de MINIMUMs basta con sumar la tabla completa:

MIN = 906

Se puede repetir el procedimiento con los MAX, y después se evalúa el resultado.
¿No les parece que era un bonito problema?

Dicho por Homero en Mayo 20, 2005 10:31 PM