Búsqueda de Fresas
Descripción
A los castores les encanta jugar a la “Búsqueda de fresas”. En este juego se pone un número diferente de fresas en cada campo de una cuadrícula. Un castor puede empezar en cualquier campo y dar 3 pasos. En cada paso puede elegir ir hacia arriba, abajo, derecha o izquierda.
En un ejemplo, un camino permite comer 9 + 1 + 6 + 5 = 21 fresas.
En otro, 7 + 1 + 5 + 8 = 21 fresas.
En total, el castor visita cuatro campos: el que eligió para empezar y tres más, y se come todas las fresas que haya en ellos.
Un pequeño castor está jugando en otra cuadrícula.
Pregunta
¿Cuál es el número máximo de fresas que podría comer?
Ver soluciónOcultar solución
Solución
La respuesta correcta es 23. Un recorrido de tres pasos siempre visita cuatro campos adyacentes y sólo puede formar un número limitado de figuras. No es necesario comprobar los 51 recorridos posibles uno por uno. Conviene revisar primero las formas que incluyen los campos con 9 u 8 fresas, porque son los valores más altos. Entre ellas aparecen recorridos que suman 23, por ejemplo 9 + 1 + 5 + 8 y 5 + 9 + 2 + 7. Además, si un recorrido no usa ni 8 ni 9, la suma máxima posible de otros cuatro campos es 7 + 6 + 5 + 5 = 23. Por tanto, 23 es el máximo.
La informática detrás del desafío
Muchos problemas de informática buscan un valor máximo o mínimo: hacer más trabajo, gastar menos recursos o, en este caso, comer el mayor número de fresas. A esto se le llama optimización. Una forma de hallar la mejor solución es enumerar todas las posibilidades y calcular su valor, método conocido como búsqueda exhaustiva o fuerza bruta. Cuando el número de posibilidades crece, conviene analizar restricciones y propiedades del problema para reducir lo que necesitamos revisar.
Para el aula
Dibuja una cuadrícula de 3 × 4 y escribe un número del 1 al 9 en cada casilla. Elige exactamente tres movimientos ortogonales. Antes de probar todos los caminos, identifica qué casillas de valor alto conviene incluir y busca el recorrido de cuatro casillas con mayor suma. Después verifica si tu estrategia realmente encontró el máximo.