Rompecabezas

El siguiente problema pareciera no tener nada que ver con la matemática. Al menos con la concepción clásica que tiene (¿tenía?) asociada a la matemática con los números y saber hacer cuentas. Creo que esa percepción está cambiando. De todas formas, quiero plantearle algo «divertido».

Usted, como yo, ha visto muchísimos rompecabezas en su vida. Con más o menos piezas, más o menos difíciles de resolver. Algunas veces habrá tenido paciencia para armarlos, otras no. Algunas otras veces habrá ayudado a un niño, y otras veces habrá sido usted el niño.

Usted también sabe que hay rompecabezas cuya solución implica invertir muchísimo tiempo, aunque más no sea porque involucran ensamblar un número enorme de piezas. Hay gente que los empieza a armar arriba de una mesa, y se pasa semanas (si no meses) hasta que lo termina. Para algunos, es incluso un pasatiempo o un hobby.

Por supuesto, cada uno establece una estrategia que no tiene por qué ser la misma para cada rompecabezas y, quizás, uno ni siquiera sabe que la tiene. Por ejemplo, uno puede empezar por los bordes, o buscar colores parecidos, o aquellos que tienen algún patrón en común.

No sé si habrá gente que es profesional en el armado de rompecabezas, pero creo que cada uno de los que está leyendo esto sabe bien a qué me refiero. Más aún: en el proceso de resolución, muchas veces uno ensambla distintos bloques y, después, casi sin proponérselo, puede pegar un bloque con otro. Es decir, no siempre se trata de ir armando un bloque cada vez más grande al que uno le va agregando una pieza por vez.

Sólo para ponernos de acuerdo con los nombres, voy a llamar «bloque» tanto a las piezas más pequeñas (cuando está todo desarmado), como a cualquier grupo de piezas que ya estén interconectadas.

En realidad, para ser técnicamente correctos, uno tendría que decir que una «pieza» es un «bloque de una sola pieza».

Al mismo tiempo, voy a decir que hago una «jugada» cada vez que logro ensamblar dos bloques. O sea, cada «jugada» que hago implica que tengo menos piezas o bloques sueltos.

Supongamos entonces que uno está frente a uno que tiene 5000 piezas. Sí, cinco mil. Como verá más adelante, el número de piezas no tiene importancia, pero por ahora -para fijar las ideas- digamos que son cinco mil.

Dicho todo esto, ahora sí, dos preguntas:

a) ¿Cuál es el mínimo número de «jugadas» que uno tiene que hacer para poder armar el rompecabezas de 5000 piezas?

b) ¿Qué estrategia puede diseñar usted para que, si uno sigue los pasos que usted indique, quede armado el rompecabezas en ese número mínimo de jugadas?

Una última cosa: no permita que lo confunda todo lo que yo escribí acá arriba. Es algo muy sencillo: uno tiene un rompecabezas con piezas que, al principio, están todas separadas. Se trata de conectarlas. Las preguntas son: ¿cuál es el número mínimo de movimientos o jugadas que hay que hacer para armar el rompecabezas? Y, por otro lado, ¿cuál es la estrategia que garantiza que uno lo arme en ese número de movidas?

Solución

La única gracia que tiene este problema es tratar de resolverlo uno. Encontrar o no la solución resulta irrelevante. Si quiere, puede leerla ahora (la solución), pero no se prive del placer de poder pensarlo en soledad. Igualmente, acá va.

Pongámonos de acuerdo en un par de hechos:

a) El número inicial de piezas (o bloques) es 5000.

b) El número final de bloques es uno. Cuando ya esté armado todo, queda un solo bloque (grande, pero uno).

c) Cada movida reduce el número de bloques libres en uno. Es decir, cada vez que ensamblo dos bloques, hay un bloque libre menos.

Dicho todo esto, piense conmigo lo siguiente: no bien empiezo a armar el rompecabezas, mi primera jugada significa conectar «dos bloques». Si originalmente había 5000, ahora, hay 4999. Y en el próximo paso, o en la próxima jugada, quedarán 4998. Y así siguiendo.

¿Quiere leer nuevamente las preguntas que propone el problema? ¿No tiene ganas de pensar las respuestas por su cuenta, sin leer lo que sigue más abajo?

Ahora creo que estamos en condiciones de contestar las dos preguntas.

Por un lado, como hay 5000 piezas y cada jugada reduce en uno el número de bloques, eso significa que no se puede resolver en menos de 4999 pasos. Es que para ir teniendo cada vez menos bloques uno necesita ir ensamblándolos de a uno por vez.

Ahora bien: ¿qué estrategia diseñar para que uno pueda armar el rompecabezas en esos 4999 pasos?

Lo interesante es que no importa qué estrategia uno diseñe, todas involucran 4999 pasos. Así como no se puede hacer en menos, tampoco se puede hacer en más (salvo que uno arme y desarme constantemente, lo que descarto porque supongo que la idea es resolver el problema y no complicarlo).

Entonces uno piensa que cada vez que armó algo no vuelve para atrás (o sea, no los de-sarma), por lo tanto cualquier proceso de armado que elija tiene ¡exactamente 4999 pasos! ¿No es raro esto? ¿E interesante a la vez?

Y con esto último quedan contestadas las dos preguntas.

Tengo un pequeño agregado: ¿y si en lugar de 5000 piezas fueran 10.000? ¿Cuál sería el mínimo número de pasos y qué estrategia usar para el armado que involucre ese número?

Respuesta: Como usted habrá advertido ya, el hecho de que sean 5000 o 10.000 no interesa. En realidad, el número mínimo de pasos para armar el rompecabezas es ahora de 9999. Por otro lado, cualquier estrategia para resolverlo que involucre no volver para atrás requiere de exactamente de esos 9999 pasos. Más en general aún: si uno tiene un rompecabezas con cualquier número de piezas, digamos n piezas, en donde n es un número cualquiera, la cantidad mínima de pasos (o jugadas) para armarlo es de (n-1). Y cualquier estrategia que uno elabore y que sirva para completarlo requiere de esos (n-1) pasos.

Por último, por supuesto que el artículo no enseña a armar un rompecabezas. Tampoco me lo proponía. En todo caso, lo que dice es que cualquier estrategia que a usted le haya servido para armarlo es buena, en el sentido de que inexorablemente usted habrá usado el mínimo número posible de pasos para armarlo. Ahora bien, la pregunta que no puedo contestar es si el tiempo que le llevó es el óptimo (o mínimo). Eso no lo puedo predecir pero, en definitiva, ¿qué importancia tiene?

Fuente: http://www.pagina12.com.ar/diario/contratapa/13-148169-2010-06-24.html