Rompecabezas nivel MIT

(Prometo poner fotos una vez las saque de la cámara)

Aquí, on base, como decimos normalmente, es donde se sitúa el lodge donde a su vez vivimos la mayoría de los becarios. Dos edificios (uno para los becarios NASA y otro para los Googlers) estilizadamente rectangulares y enclavados perpendicularmente. Digamos que a vista de pájaro forman un ángulo de 90 º y en medio cobijan nuestro querido patio. Cada uno de estos edificios consta de dos plantas donde el pasillo-balcón rodea las habitaciones, cada planta dispone de unas 10 habitaciones, cada habitación de dos camas y normalmente dos huéspedes.

El patio dispone de barbacoa, bancos, mesas y además es el punto caliente para la WiFi. Así que en mi caso puedo afirmar que soy afortunado, ya que desde mi nido en la primera planta puedo husmear quién está en el epicentro sin temor a ser percibido y a la vez soy una de las habitaciones que capta la WiFi.

Estábamos charlando animosamente unos cuantos del lodge en el descrito patio cuando apareció John. Como no, se trata de un americano que desciende de familia extranjera. Más concretamente de Hong Kong. Además sucede que había estado yo leyendo el “Surely you‘re joking Mr. Feynmam” que contaba las mil maravillas de la que había sido la sede de sus primeros y genuinos años como universitario en el Massachussets Institute of Technology (MIT). De modo que aquí tenía un individuo aparentemente inofensivo, un tanto nervioso en sus movimientos pero dulce en rasgos y palabras, y con el halo de que algo se cocía en su mente.

Roman y él, se enfrascaban en una conversación sobre rompecabezas. Mientras tanto permanecía yo a la escucha ya que desconocía los rompecabezas que ellos decían conocer. El primer rompecabezas decía… (Las respuestas las dejo al final del post)

1. Tenga usted dos mechas de igual longitud. Las dos tardan exactamente una hora en quemarse. Sin embargo, son irregulares en forma y por lo tanto, la velocidad con la que se quema la mecha es variable (o aleatoria para nosotros). En otras palabras cuando una de las mechas esté prendiendo por la mitad, no podemos asegurar que ha pasado media hora. ¿Como podemos hacerlo para medir un cuarto de hora? (Las irregularidades de las dos cuerdas no están distribuidas de igual forma)

A lo que Roman contraatacaba proponiendo otro:

2. Puede ser que ya conozcan el problema ese en que hay un oso situado en un punto de la Tierra. El oso se mueve hacia el Sur un kilómetro, seguidamente al Oeste otro kilómetro y finalmente otro kilómetro hacia el Norte. El sitio de donde ha partido y al que ha llegado son los mismos, ¿de qué color es el oso? La respuesta es: es un oso polar (blanco) y se encuentra en el polo norte.

Pero no es esta la única solución posible, todavía quedan más puntos en la Tierra donde podría estar dicho oso. ¿Cuales son?

A continuación John proponía un típico caso de probabilidades para comprobar hasta qué punto sabemos lo que sabemos.

3. Tenemos una moneda. La lanzamos. ¿Probabilidad de que salga cara? Obviamente 0,5.

Ahora tenemos dos monedas, y las lanzamos a la vez, cayendo las dos debajo del sofá. Pero antes de que se metan debajo, hemos visto como en una salía cruz. Así que metemos la mano debajo y sacamos la primera moneda que encontramos sin mirarla. ¿Cual es la probabilidad de que sea cara?

Entonces llegó el momento del rompecabezas final. Tragando saliva John nos contaba lo siguiente, no sin antes afirmar que estaba un nivel por encima de los contados hasta aquí.

4. Estamos en una prisión de alta seguridad con 100 presos. A los presos se les asignará a cada uno un número entre 1 y 100 de forma totalmente aleatoria. Pueden repetirse. Este número irá pegado a la espalda, con lo que un único preso no podrá verse su número pero sí podrá ver el de los demás 99 presos.

Una vez asignados los números, los presos deberán intentar adivinar el suyo. Si nadie lo adivina, todos serán condenados a muerte. Si tan solo uno (o más) adivina su propio número, todos sobrevivirán.

A los presos les es permitido planificar una estrategia conjunta antes de la asignación de los números. PERO, una vez asignados, no puede existir ningún tipo de comunicación, ni transferencia de información entre los presos, más que la de poder ver los números del resto de compañeros. En otras palabras, lo único con que pueden basarse, es en los números que ven en el resto de prisioneros.

Debe encontrarse una estrategia para asegurarse de que al menos uno de ellos adivinará su número. “Asegurarse” es encontrar una estrategia que asegure que, cualquiera que sea la asignación de los números, siempre resultará que uno o más prisioneros dan con el número. ¿Cual es esa estrategia?

Así que en el patio estábamos 7 u 8 personas con poses de jugador de ajedrez sentados y con los sentidos aletargados, meditando cómo demonios podía ser que existiera una estrategia ganadora. ¡Menudo reto! Mientras tanto, John contestaba a las propuestas sin futuro para una estrategia que salvara a los prisioneros. Pero por más que pensábamos, parecía imposible encontrar un sistema que asegurara al 100% que, una vez asignados los los números aleatoriamente y sin ninguna dependencia, uno pudiera descubrir su propio número mirando… ¡a los del resto de compañeros presos!

Hasta que pasado un rato solo quedamos tres. Mi compañero Roman, un tipo que había visto pero no conocido y yo, los tres sacando humo por nuestras orejas. Entonces, el tipo que no conocía murmuraba que él ya sabía la solución para 2 prisioneros (con 1 y 2 como números a asignar aleatoriamente y con posibilidad de repetición), pero no para 100. ¿Sí? ¿Cual? Fácil: el primer prisionero dice el número que ve en el segundo prisionero y el segundo prisionero dice el número que NO tiene el primero.

No voy a entrar en detalles, pero si lo comprueban con casos prácticos verán que funciona. La idea reside en que solo hay 2 posibilidades. Que los prisioneros tengan los mismo números (1 y 1, o 2 y 2) o que los tengan diferentes (1 y 2, o 2 y 1) entre ellos. Por lo tanto uno tiene que apostar a que el número del otro es igual que el suyo, y el otro tiene que apostar a que los números son diferentes. Como solo hay 2 posibilidades, uno acertará ya que un hay una relación inequívoca entre el número que tiene uno y el que tiene el otro si suponemos que son iguales o diferentes.

Así, que trabajando en equipo, uno puso la semilla, y los otros dos (Roman y yo) pusimos la generalización a los 100 presos. Esa noche dormimos contentos, sabiendo que habíamos resuelto un rompecabezas de nivel MIT.

SOLUCIONES

1. Medir un cuarto de hora:

Se coge una mecha y se enciende por las dos puntas. En el mismo instante se enciende la segunda mecha por una sola punta. Cuando la primera termina de quemar, ha pasado media hora. Ahora cogemos lo que queda de la segunda y encendemos la punta que no prende. El tiempo que tarda desde que encendemos esta segunda punta, hasta que se consume toda la mecha, es exactamente un cuarto de hora.

2. El oso que vuelve a casa:

Empezando desde el polo sur. Buscamos el primer paralelo que se cierra en un kilómetro. Nos desplazamos un kilómetro arriba de cualquier punto situado encima de este círculo. En este punto es donde también podría empezar a andar el solo: el punto de partida. Por lo tanto en un círculo hay infinitos puntos y por consiguiente son infinitas soluciones. ¿Hay más todavía? Sí. Ahora hacemos lo mismo para encontrar el punto de partida pero con un paralelo de longitud 1 kilómetro dividido por un número natural.

3. Probabilidad de cara:

La probabilidad es de 1/3. Teniendo en cuenta que hemos cogido una de las dos monedas y que sabemos que una es cruz, solo hay 3 posibilidades: una cara, la otra cruz; una cruz, la otra cara; las dos cruz. Para una moneda solamente que no sabemos si es una o la otra: hay 6 posibilidades: 4 (2+1+1) cruz y 2 (1+1) cara. Por lo tanto 2/(4+2)=1/3.

4. Los 100 prisioneros.

Primero vamos a ver una solución para el caso de tan solo 2 personas donde se les asigna números entre 1 y 2, pudiendose estos repetir. La solución en este caso sería: uno escoge el número que ve en el otro, y el otro escoge el que NO tiene el primero. ¿Qué no véis como esto funciona? Probad casos empíricos: 1 y 1, 1 y 2, 2 y 1, y 2 y 2.

Ahora con 100 prisioneros. La clave de la cuestión está en lo siguiente: si uno tiene una propiedad conjunta de los 100 números de los prisioneros que los relaciona unívocamente, sabiendo los 99 números podría averiguar el suyo. ¿Cual es esa propiedad? La suma de todos los 100 números módulo 100, siempre dará un valor entre 0 y 99. Si sabemos lo que da la suma y sabemos 99 números de los que la conforman, podremos averiguar el número que queda. Es una una simple ecuación de una incógnita. Pero no sabemos cuanto suman los números.

¿Pero cuantas posibles sumas hay? Hay 100 posibles sumas: desde 0 hasta 99. Y disponemos de 100 tipos. Por lo tanto hay que hacer que cada uno deduzca su número suponiendo que la suma es una.

El primer prisionero supondrá que la suma es 0.
El segundo supondrá que es 1.
El tercero supondrá que es 2.
Y así sucesivamente.
Como solo hay 100 posibles sumas, uno de ellos supondrá la suma correctamente y por lo tanto deducirá su número correctamente. Uno y solo uno.

rompecabezas