Los presos y los 2 interruptores
Foto de la cuenta de Flickr de El Tekolote
Otra vez, los habitantes de nuestra isla apresaron a 100 presos que condenaron a muerte. Y de nuevo, como nuestro rey era muy peculiar y además no era muy sanguinario, decidió darle una oportunidad a estos presos para poder salir libres y solamente ser expulsados de la isla. Los reunió a todos y les comunicó la nueva propuesta: "A partir de mañana estaréis encerrados en celdas individuales. De vez en cuando y de forma aleatoria seleccionaré a uno de vosotros y os llevaré a una habitación con dos interruptores antiguos, uno al lado de otro, que podrán estar subidos o bajados. El prisionero tendrá que elegir uno de los dos interruptores y cambiar el estado de este. Nadie más accionará los interruptores hasta que le toque el turno al siguiente preso. Como los interruptores son antiguos y no están conectados a nada, no causarán ningún efecto. Seguiremos así hasta que alguno de vosotros afirme que todos habéis estado ya en la habitación. Si el preso tiene razón, se os pondrá a todos en libertad y seréis expulsados de la isla. Si el preso se equivoca todos moriréis. Ah, como el orden es aleatorio, puede pasar que un preso entre en la habitación varias veces antes que otro. Además, si tardáis en responder, de vez en cuando os tocará a todos volver a la habitación. En la habitación solamente se os permitirá accionar los interruptores, os vigilaremos para que no podáis dejar otras pistas de haber estado ya allí". Los presos pasaron el resto del día en el patio para que pudieran estar relajados antes de un día tan importante. ¿Pueden diseñar una estrategia para poder salvarse?
Comentarios a través del feed: RSS 2.0
Dirección de trackback.
8 comentarios
Vamos a ver, al principio me costo un cacho, pero creo que casi lo tengo (un pequeño programa para comprobar soluciones que me he hecho, me ha venido bien).
Mostrar ▼
PD: Como quedo el de los 300 cables?
Por cierto, que si la cosa no fuera de salir de la cárcel, sino de engañar al rey para que nunca les ejecutara (vamos, sobrevivir), sería tan fácil como dividirse en dos grupos y un grupo mueve siempre el interruptor de la izquierda y el otro grupo el de la derecha. No saldrían nunca pero oye, evitas la ejecución
Ya esta, lo tengo (parece habitual en mi resolver estas cosas en dos pasos). Iba a consultarlo con la almohada pero me ha venido de repente
Mostrar ▼
Hola David. He editado el problema. He quitado las condiciones para evitar no morir y estar tiempo indefinido en la cárcel. Resulta que esas condiciones las añadí en un último momento para eso, evitar que puedan hacerlo. De hecho pensé en lo que has dicho en tu último post, pero entre una cosa y otra se me olvidó añadir una condición para evitarlo. Además las condiciones que he añadido tienen una pega con la solución que yo me sé.
Edito: pues mientras escribía has vuelto a escribir con la solución. La pega que tienes no la tienes puesto que he editado, así que correcto. Ah, el de los cables creo que era correcto aunque lo escribiste de forma confusa. Hay otra solución.
Otra solución para cual? Para este? Para el de los cables? (ese yo ya tengo aceptado que es una chapuza como lo explique, podría refinarlo mas, pero no mejorando el número de viajes) Para los dos?
Ah, y un último detalle que acabo de ver con tu mensaje. Cuando digo en #3 que la restricción original era un problema, no me refería a que por ello la solución no fuera válida, simplemente a que afectaría al rendimiento (tardarían mas en salir, pero saldrían con un 100%)
De hecho, he pasado esto por el ordenador (todo el simulador ya estaba hecho), y teniendo que cumplir las restricciones, el "algoritmo" solo es estadisticamente 13% mas lento, para 100 intentos, con 100 presos.
Como último dato, si el rey sacara un preso cada 5 minutos a la sala de los interruptores, se tardaría unos 80 dias (20549,11 cambios de interruptor sin restricciones 23348,45 con ellas)
Sí, sí, de acuerdo en que luego arreglaste esa pega. ¿Las simulaciones las has hecho usando aleatoriedad al sacar los presos?
Y me refería al de los cables.
Si, mas o menos, si, aleatorio el como sacar los presos y el estado inicial de las bombillas.
En realidad utilice la misma semilla para el generador de numeros en ambos casos (con restricciones y sin ellas), pero nada mas