miércoles, 29 de abril de 2015

Enigma de los monjes (Solución)

Ya se me había olvidado acabar el enigma de los monjes...

Este problema no es dificil si empezamos por el caso más fácil y lo vamos extrapolando. Sería un poco hacer una demostración por inducción. Es decir, primero se demuestra que un caso concreto es verdad y a continuación se demuestra que si el caso n es verdad, el n+1 también lo es. Así quedaría demostrado para todo n.

Aplicado a nuestro problema primero miramos un caso concreto, el más sencillo.
n=1 >> Solo hay un monje con marca en la frente:
-Esa noche ese monje verá que nadie tiene marcas.
-Los demás solo ven la marca de ese compañero (aún no pueden saber si ellos mismos la tienen o no)
-Alguien ha de tenerla, así que el monje deduce que él mismo la tiene.
-Al día siguiente se va.
-Por la noche cuando los demás monjes ven que falta el compañero entienden que ellos no tienen marca.

Y ahora intentamos ver que a partir de ese caso se pueden deducir inductivamente todos los demás.
n=2 >> Dos monjes con marcas.
-Los que tienen marca ven solo una, la del otro.
-Así que en principio creen que están en el caso n=1 y que mañana faltará el otro.
-Ambos deciden no irse.
-Al día siguiente en la cena siguen viendo una marca y deducen que si el otro no se ha ido es porque no estamos en el caso n=1. Por tanto ha de haber dos (3 no porque estarían viendo 2)
-Ambos deciden irse.
-Los que no tienen marca ven 2, y al cabo de dos días ven que faltan dos compañeros. Ahí entienden que ellos no tienen la marca.

Por si acaso vamos a ver el siguiente caso:
n=3 >> Hay tres marcas.
-Los que tienen marca están viendo 2 y piensan que estamos en n=2.
-Por tanto creeran que los otros dos están viendo una y que creen que están en n=1.
-Al día siguiente nadie se va. Queda descartado n=1.
-A los dos días nadie se va. Tampoco estamos en n=2.
-Ahí los 3 a la vez se dan cuenta que no es cosa de los dos marcados que están viendo sino que ha de haber un tercero y ha de ser él mismo.

Si pasan n días y tú ves que n marcados no se van, es que tú tienes la marca también, estamos en n+1, y nos vamos todos.

Así es como saben si tienen marca o no y en siete días se van siete monjes (o seis dependiendo de si cuentas también el día inicial o no)

Es curioso ponerse en la piel de un monje con marca de un total de 8 marcados. n=8.
Verá 7 y pensará que está en n=7.
Por tanto cree que la cosa no va con él y que el resto de marcados ven 6 y creen que están en n=6.
Por tanto pensarían que el resto de marcados ven 5 y creen que están en n=5.
Por tanto creerían que el resto ven 4 y crerían estar en n=4.
etc.

¡Inception!

5 comentarios:

Albert-Miquel Sánchez dijo...

Varias cosas:

1 - Para esta solución había que suponer que obligatoriamente había alguien con manchas, es decir, el oráculo no se había equivocado (claro, cómo se iba a equivocar). Esto no quedaba explícito en el enunciado.

2 - Hay que suponer que todos los monjes son super listos, lo que tampoco quedaba explícito en el enunciado. Un moje monje menos listo con mancha (del tipo que me imaginaba yo en el problema) que viera a otro monje con mancha y que no se fue la primera noche podría pensar "mira que pringao, no se ha dado cuenta que es él el de la mancha".

3 - Una entrada para la solución? No te bastaban los comentarios?

Baterpruf dijo...

Ok, lo podría haber añadido. Pero el enunciado es copiado. Esos son los datos.

Yo creo que se pueden dar por supuesto.

El enunciado dice que cuando llega el séptimo día se van los que corresponden. O sea que saben usar la lógica.

Y podría ser que ese "algunos" no sea suficientemente preciso, no se sabe si incluye el cero. Pero si incluye el cero no habría solución, o sea que descartamos el cero porque sí hay solución.

Aparte... se están yendo al día 7 porque hay varios, no cero.

Albert-Miquel Sánchez dijo...

Discrepo. Dar algo por supuesto va en contra de toda lógica.

Baterpruf dijo...

Minucias!

Albert-Miquel Sánchez dijo...

En cualquier caso ha sido un buen ejercicio. Muy bien Bater!!!