En un antiguo reino había un rey que cada vez que se aburría decidía inventarse algún juego para intentar poner en un aprieto a sus presos dándoles a la vez la oportunidad de salir libres. En esta ocasión eran 100 los presos que tenía en el calabozo, los reunió a todos y les comunicó el nuevo juego:
"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 de palanca, 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. 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."
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? En la habitación de los interruptores solo pueden accionar un interruptor, no pueden dejar ningún tipo de señal para dar pistas a los demás.
Comentarios
#28 Piensa que antes que tu primera vez hay gente que puede haber entrado varias veces.
Pues sí. Tienes razón, no lo sube el primero que entra, sino el preso-contador.
El preso contador lo sube la primera vez que entra y empieza a contar cada vez que entre y lo vea bajado.
Espero que ya no queden huecos en la explicación. ¿Falta algo?
Me ha gustado mucho.
#29, el problema está en que cuando entre el contador por primera vez no sabrá si la palanca estaba subida de primeras y no le toca contar o si la ha subido alguien y tenga que contar.
#30 Veamos, conforme lo dices, con la misma dinámica:
- Ponemos un preso como "contador" (pero sin bici )
- Cada preso sube el interruptor-contador una y sólo una vez, menos el contador que es el único en bajarlo.
- Si el interruptor-contador está arriba, acciona el otro, que no tiene valor.
Cuando el contador cuente las suficientes veces, 99, que ha bajado el interruptor-contador, sabrá que han estado todos.
Soluciones a un posible falso primer positivo:
- Que el contador no esté nominado de antemano, que sea el primero en entrar en la habitación. Problema: nadie sabrá quién es el primero. Por lo que descartamos
- Que en lugar de contar hasta 99, cuente hasta más de 99, si sólo se sube una vez por preso, si llega a poder contar más de 99, sabrá que ha habido un falso positivo pero que han estado todos
#31 O también puedes hacer que cada uno tenga que bajar la palanca de control para ir contando dos veces no? y si llegas a contar 199.. pim todos libres, no? joe llevo toda la mañana pintando flechitas
#34, por fin alguien da con una solución 100% buena. Su no entiendo mal dices que tienen que activar la palanca 2 veces. Ahí está el truco. Bueno, tienes un pequeño fallo, lo que tienes que contar es 198, que significará que todos los presos han activado la palanca 2 veces con la posibilidad de que uno solo la haya activado una vez.
CC #1, #2, #5, #10
#31, tu última solución no vale tampoco porque si decimos que debe de contar más de 99 y el interruptor estaba en la posición 0, solo podrá contar hasta 99. Al menos que cambies de alguna forma como actúan los demás.
#36 O no, si el primero en entrar se encuentra con la palanca subida, la deja como está, y el contador lo cuenta igual,
#37, su la palanca está activada inicialmente contará al final 100.si no está activada contará al final 99.
#36 y #31 no me vale ¿y si el rey es un cachondo y mete a 3 presos en bucle y uno de ellos es el contador? Si cada uno baja la palanca de control infinitas veces no hay forma de saber si han estado todos o no
#45, espera, a qué comentario querías citar. Si te refieres al que he dado por buena la solución, lo que pasa es que ahí cada preso puede activar la palanca como mucho 2 veces, así que si hace ese bucle, solo contaría 4 (o 5 si la palanca estaba activada inicialmente).
#46 Con el mío también
#48, no, tú dices que cada preso puede activar el interruptor una vez (al menos en 31 que es el que has citado ahora). En la solución que se ha dado por aquí cada preso puede activar el interruptor 2 veces.
Si cada preso lo activa una vez, al llegar a 99 el contador no puede saber si lo han activado 99 presos o 98+interruptor. Y no sabemos si va a poder llegar a 100.
Si cada preso activa hasta 2 veces, al llegar a 198, o bien todos los presos lo han activado 2 veces, o bien 98 presos lo han activado dos veces, el otro preso una vez y el interruptor estaba inicialmente activado. Así que al llegar a 198 el contador, el que cuenta sabrá que todos los presos han pasado por la activación.
Esa es la diferencia.
#49 Si son sólo 2 veces por preso, de acuerdo lo había entendido de otra forma
#45 No hace falta que sea un cachondo (el enunciado dice que es aleatorio), pero la aleatoriedad puede generar eso, es lo que tiene la aleatoriedad...
#30
- El primer preso deja el contador a 1
- El preso contador al entrar si ve que el interruptor esta en 0 sabe que es el primero en entrar y lo deja como esta.
- El resto de presos solo ponen a 1 si esta en 0, y solo lo ponen una vez.
entra el preso 1 --> 1
entra contador --> 0 (1)
entra contador ----> 0
entra el preso 1 --> 0
entra preso 4 -----> 1
entra preso 3 -----> 1 (no hace nada y esperara a un 0 para poner en 1 y ser contado)
entra contador ----> 0 (2)
entra preso 4 -----> 0
entra preso 3 -----> 1
...etc
#32, pero si el contador estaba inicialmente a 1, el primer preso no lo tocaría y el contador al entrar no puede saber si es el primer preso en entrar o no. Solo lo sabrá si el contador estaba inicialmente e 0 y él es el primero.
#35
Contamos hasta 200 y cada uno hace dos marcajes. Con eso nos evitamos la incertidumbre que comentas.
#41 perdón, 198 ya que el contador no se cuenta. 2*(n-1)
#42, sí, ya se te han adelantado.
Ya se me ocurrió.
Era más fácil de lo que pensaba.
Usar un interruptor como señal y el otro como comodín (que suben o bajan).
Clave: Solo uno de los presos es el preso-contador, y el resto se limitan a mover el interruptor señal una única vez cuando entran por segunda vez (o siguientes si lo ven fuera de su posición).
Basta que el preso contador cuente el número de veces que el interruptor da la señal, cuando haya contado 99 señales puede estar seguro de que han pasado todos (además de él).
Ej: El izquierdo es el oscilante, su posición (arriba o abajo) es irrelevante, y el de la derecha es el señal. La señal es bajarlo.
El primer preso en su primera entrada sube el derecho, pone el contador a cero, y si ya está arriba ↑, mueve el izquierdo (pasa turno).
Desde ese momento cada nuevo preso que entre moverá el izquierdo en su primera entrada (pasa turno), esté como esté, da igual. Y en su segunda entrada o cualquiera de las siguientes (y solo una única vez), da una señal: baja el derecho.
Ese interruptor señal estará arriba hasta que llegue el preso-contador, que lo bajará y ya sabrá que un preso entró dos veces.
Contando el número de veces que ve la señal sabrá cuantos presos han entrado.
Ahora el problema más complicado está en establecer qué interruptor es el oscilante y cuál el señal. Deben establecer un sistema de orden en la orientación dentro de la habitación que les permita identificar bien el interruptor señal, será el que esté más a la derecha, o más lejos de la puerta, o más arriba, y la señal será bajarlo
o moverlo hacia la derecha o alejarlo de la puerta(nada, ya dice el enunciado que se baja).#27, casi correcto. Has diferenciado lo que hace el primer preso del resto. Pero un preso no sabe si es el primer preso o ha estado alguien antes y lo ha subido. Piensa que antes que tu primera vez hay gente que puede haber entrado varias veces. Por cierto, te has liado al explicarlo, el preso contador sería el único en subirlo en vez de ser el único en bajarlo, ¿no? Pero se te ha entendido.
Casi casi lo tienes. Hay que hacer alguna variación
#5, de hecho no se sabe la posición inicial, podría ser cualquiera de las 4 posibles.
No entiendo bien la parte de...
"Además, si tardáis en responder, de vez en cuando os tocará a todos volver a la habitación."
#10, obviamente vuelven a sus celdas.
Lo de si tardan en responder y tal quiere decir que independientemente de las veces que hayas estado en la habitación, si nadie da una respuesta en algún momento te volverá a tocar. "Os tocará a todos volver a la habitación" pero individualmente
CC #13
#16 Entonces, si alguien dice "Aún no han estado todos" ¿ese ya no es llamado de nuevo?
#19, uhm, aquí la respuesta que se puede dar es "Ya han estado todos", y en tal caso se termina el juego (para bien o para mal). Vamos, solo existe una respuesta posible y solo se podrá dar una vez. Y mientras no se de pues eso, de vez en cuando te llamarán para que entres a la habitación.
#21, todos los presos vuelven a la habitación de vez en cuando. Y obviamente no puedes contar usando los 4 estados de los interruptores, entre otras cosas porque estás forzado a moverlo, y si quisieras contar como dices, si entras por segunda vez no deberías de aumentar el contador.
La forma de hacerlo es bastante sencilla. Pero ten en cuenta una cosa también, no hace falta dar la respuesta en cuanto hayan estado todos una vez, solo tienes que estar seguro de que han estado todos, pero lo mismo ya han estado 1000 veces.
#6, no, solo uno.
#14, todo aleatorio, lo mismo un día no llevan a ninguno que pasan 30 presos un día, y pasando uno de ellos 40 veces, etc.
#15 ¿Y después de que se accione el interruptor los presos pueden consultar su estado?
#17, el preso que le de al interruptor sabrá su estado. Y solo el preso que le toque después podrá ver el estado. El resto de presos no.
#18 Pues entonces no se me ocurre nada que pueda funcionar cualquier cosa dependería de implementar un contador con los interruptores, pero en esas condiciones, o tenemos un preso que de vez en cuando vuelve a la habitación y va contando cada día (o cada 4), o no podemos, el mayor contador en esas condiciones es hasta 4, con lo que si pusiésemos un contador, nunca llegaría más allá del 4 antes de repetir todo
puede pasar que un preso entre en la habitación varias veces antes que otro.
De ahí se entiende que van a la habitación con los interruptores, y luego vuelven a su celda.
Además, si tardáis en responder, de vez en cuando os tocará a todos volver a la habitación.
Esto no lo entiendo.
¿Puedo entender que van entrando todos a la misma habitación y se quedan ahí todos juntos acumulados esperando la respuesta y que solo vuelven a su celda si no hay respuesta?
¿O vuelven a su celda tras accionar el interruptor?
#2, #5 y #10.
Venga, os simplifico un poco el problema, a ver si así os inspiráis.
Mismas condiciones, pero solo un interruptor, y ahora permitimos que el preso puede abstenerse.
No sé si funciona del todo bien, pero lo dejo como punto de partida:
Norma: solo poner ↓↓ cuando hayas visitado por segunda vez, señal1.
Norma: numerarse los presos.
Norma: Dejar tantas señales para el siguiente como tu número de preso.
Norma: Solo poner ↑↓ cuando el número señales recibidas supere a tu número de preso.
Paso 1, llevar el 2 hacia arriba.
Si encuentro ↑↑, bajo el 1 -> ↓↑
Si encuentro ↓↓, subo el 2 -> ↓↑
Si encuentro ↓↑, subo el 1 -> ↑↑
Si encuentro ↑↓, subo el 2 -> ↑↑
Queda el 2 arriba y el 1 oscilando.
Paso 2, mantener el 2 arriba si no has estado antes, bajarlo si ya lo has visitado.
Si encuentro ↓↑ y no he estado, subo el 1 -> ↑↑
Si encuentro ↓↑ y sí he estado, bajo el 2 -> ↓↓ (Señal1 para el siguiente).
Si encuentro ↑↑, bajo el 1 -> ↓↑
Si encuentro ↓↓ (señal1), subo el 2 -> ↓↑ y cuento que alguien me dejó la señal1 de que ha pasado por segunda vez.
No puede haber ↑↓ (lo usaremos más adelante como señal2).
Paso 3.
Repetir el paso 2.
Cada preso puede dejar tantas señales1 como su número de preso, a partir de entonces, ya no deja más veces la señal1, si soy el preso 32 y encuentro ↓↑ y ya he dejado 32 señales1, subo el 1 -> ↑↑ (no deja señal1)
Cuando un preso cuente el número de señal1 hasta un número mayor que su número de preso deja la señal2 ↑↓.
Eso implica que al menos otra persona además de mí ha entrado más de una vez.
Si encuentro ↑↓, subo el 2 -> ↑↑ y cuento una señal2.
Cuando un preso encuentre un número de señales2 mayor a (100 menos su número de preso) significa que todos han pasado por la habitación.
Ya me cansé de pensar, no sé si funciona...
#23, diría que te has liado un poco porque hay cosas que no entiendo. ¿Qué pasa si el preso con número 27 entra 270 veces seguidas a la celda? (el no tiene por qué saber que son seguidas).
Y... ¿has tenido en cuenta que no conocemos el estado inicial de los interruptores?
Cuando he empezado a leer tu comentario he pensado que ibas a sacarlo a falta de un pequeño detalle (de forma distinta a la mía), pero luego has empezado a poner cosas que creo que lo único que has hecho es complicarte.
#24 ¿Qué pasa si el preso con número 27 entra 270 veces seguidas a la celda?
El preso 27 deja 27 señales1, (y cuenta 27 señales 1) luego ya no deja más señales1. No pasaría nada más.
Si viera una señal1 más, sería, necesariamente, de otro preso.
Yo tampoco creo que funcione del todo, lo dejo como principio para que piensen otros.
No sé cómo controlar que haya 100 señales diferentes y que alguien las reciba.
¿has tenido en cuenta que no conocemos el estado inicial de los interruptores?
Ese es el paso 1, dejar el interruptor 2 fijo arriba, y el 1 oscilando.
Falta un dato ¿ hay algún preso disléxico ?
Pues estoy en blanco
#0 ¿Tienen que accionar uno por obligación, no pueden "abstenerse"?
#2, no pueden abstenerse.
#4 ¿y pueden accionar más de uno?
¡Espera! ¡Pone "A partir de mañana" ! Eso quiere decir que por lo menos tienen ese día para ponerse de acuerdo en una estrategia ¿no? #0
#11, sí, claro. Y los deja a todos juntos en el patio.
#12 Se lleva todos los días a un preso a la habitación o son días sueltos aleatorios.
borrado
Supongo que al patio ya no vuelven, ¿no?
#1, claro, ya no se comunican más entre sí, salvo subiendo o bajando interruptores.
#3 "Podrán estar subidos o bajados" no significa que los dos vayan a estar necesariamente en la misma posición la primera vez ¿verdad?
Es que no he dado ninguna explicación, solamente he descrito un algoritmo.
Explicación:
Si el interruptor derecho está inicialmente abajo, nadie hace nada hasta hasta que el preso contador lo suba, por lo que la posición inicial es irrelevante, todo empieza cuando el interruptor derecho está arriba.
El resto de presos subirán el interruptor derecho una y solo una vez, y será contabilizado por el preso contador.
La aleatoriedad hace que el resto de presos pasen todos por los tres estados.
#53, falla. Imagina que inicialmente el derecho está arriba. Y pasa esto:
Entra el contador el primero, lo baja.
¿Y ahora qué? Nadie lo ha visto arriba salvo el propio contador por lo que no habrá ningún veterano y nadie lo volverá a subir. La cuenta nunca llegará a 99, de hecho se quedará en 0. De hecho diría es bastante probable que con tu método no se llegue a 99. Si en algún momento solo hay novatos y jubilados (y el contador, claro) con el derecho abajo (y ya estuvo subido) se acabó.
#54,No falla porque la siguiente vez que entre el preso contador subirá el interruptor derecho, y no incrementará la cuenta.
"El preso contador siempre mueve el interruptor derecho, y solo incrementa la cuenta cuando encuentra el interruptor derecho arriba cuando en su anterior visita lo dejó abajó".
Como el asunto es aleatorio, todo novato, al final pasará a veterano. (otra cosa es el tiempo que se tarde)
#56, vale, ahora lo he entendido. En un principio funcionaría, aunque habría que suponer que hay una aleatoriedad perfecta. Porque si no es perfecta podría pasar que algún preso no vea nunca el interruptor arriba, ya que este estará continuamente subiendo y bajando. Así que en sentido estás suponiendo de más. Pero OK.
La otra solución que se ha dado funciona aunque esta aleatoriedad no sea perfecta, basta con que se cumpla que los presos pasarían infinitas veces por la habitación, con lo que escaparían si viven lo suficiente, claro.
#57 Si, es mas sencilla la solución de contarlos dos veces
Sigo sin entender esto "si tardáis en responder, de vez en cuando os tocará a todos volver a la habitación", supongo que es consecuencia de la aleatoriedad, es evidente que si no responde nadie, con el tiempo todos pasarán por la habitación varias veces.
Mi respuesta es : un preso contador y resto de presos.
El resto de presos inicialmente serán novatos.
Un preso novato cuando entre a la habitación, siempre moverá el interruptor izquierdo, y pasará a ser veterano si encuentra el interruptor derecho arriba.
Un preso veterano cuando entre a la habitación, si encuentra el interruptor derecho abajo, lo subirá y se convertirá en jubilado ,y si lo encuentra arriba, moverá el interruptor izquierdo.
Un preso jubilado, siempre moverá el interruptor izquierdo.
El preso contador, mantendrá una cuenta iniciada a cero y solamente moverá el interruptor derecho e incrementará la cuenta cuando encuentre el interruptor derecho arriba si anteriormente lo dejó abajo.
Una vez que la cuenta llega a 99 asegurará que todos han pasado por la habitación.
Yo creo que funciona, aunque también creo que se puede simplificar mas.
#43, no queda clara tu explicación, pero me da la sensación de que falla. No olvides que no se conoce la posición inicial de los interruptores.
podría ser que los que han entrado una vez se sientan en un lado del patio y los que han entrado 2 o más veces se sientan en el otro
Se sabe cómo están inicialmente? o es aleatorio??
#33, no se sabe.