Otro problema de presos. Dos amigos se encuentran encarcelados, y el director de la prisión, harto de las quejas de que ellos no deberían estar ahí, les propone un juego para darles una oportunidad de librarse. El director les explica el juego y al día siguiente ejecutarán la prueba. Así tienen un poco de tiempo de planear alguna estrategia.
El juego se basa en lo siguiente: el director llevará a uno de los amigos a una habitación en la que habrá un tablero de ajedrez en el que estarán las filas y columnas enumeradas con cifras y letras de forma estándar, es decir, a cada casilla le corresponderá un código de la forma B4, D3, F2, etc. Sobre cada casilla del tablero habrá una ficha de reversi, es decir, como las de las damas pero por un lado blancas y por el otro negras. Y estarán puestas al azar, sin un criterio, de hecho podría ser que todas las fichas tenga la cara superior blancas, o ninguna, hasta que el prisionero no vea el tablero no tendrá información al respecto. Luego, el director dirá una letra y una cifra para indicar una de las casillas, y este dato será el que tendrá que averiguar el segundo preso. Y ¿qué puede hacer el primer prisionero? Lo único que se le permitirá hacer es elegir una de las fichas del tablero y darle la vuelta, cambiando así el color de la cara superior. Podrá elegir la ficha que quiera, no tiene que ser ni mucho menos la de la casilla indicada por el director, y hacer esta acción será obligatorio. A continuación lo sacarán de la habitación y meterán al otro preso, que tendrá que decidir qué casilla es la elegida por el director. Como es de esperar los prisioneros no se cruzarán, el tablero de ajedrez y sus fichas no serán manipuladas por nadie y no valdrá intentar hacer ningún tipo de seña como dejar una pieza un poco torcida o algo así. Al segundo prisionero la única información que le llegará será el color de la ficha de cada casilla.
¿Qué estrategia se te ocurre a ti que podrían idear los dos prisioneros para ser capaces de superar la prueba?
Comentarios
Este problema a mi me costó sacarlo un par de horas. Me lo propuso un amigo informático que conocía una solución (no sé si la sacó él o sus amigos informáticos), y su solución creo recordar que era distinta a la mía. Como aquí hay mucho informático, pues podéis pensar en 0's y 1's por supuesto
#1 Dos preguntas:
¿Se supone que los presos sólo pueden dar la vuelta a una ficha?
¿Los dos presos conocen la disposición del tablero antes de empezar?
#2 Entiendo que no han visto el tablero antes y que sólo puede dar la vuelta a una ficha, además es obligatorio que lo haga (si he entendido bien).
#2, el primer preso le da la vuelta a u a y solo una ficha.
Obviamente no saben la disposición inicial, si no bastaría con darle la vuelta a la de la casilla seleccionada.
Y por si quedan dudas, el segundo preso no tiene que averiguar a qué ficha se le ha dado la vuelta sino la casilla que había elegido el director.
Voy citando gente: #31, #30, #18, #15, #7, #6, #5
Para empezar #20 ha encontrado una solución, que explica mejor en #24.
Él dice que con 57 casillas puede asignarle a cada casilla todas las operaciones posibles de girar al menos 2 fichas de 6 dadas. Esto lo podría hacer escribiendo de la casilla 8 a la 63 su número en binario y cada 1 representaría un giro (por ejemplo 010011 sería girar la moneda 1, 2 y 5). Haciéndolo así lo que tienes que hacer al final es tras ver todas las casillas con giro (las del color acordado), pasarlas a binario, y con todos los números obtenidos ver las veces que sale el 1 en cada cifra. Si el 1 sale un número impar de veces en las unidades indicaría que la ficha 1 se giraría y así.
Comento esto porque si lo entendéis, será más fácil entender la solución que a mi me pasaron:
http://datagenetics.com/blog/december12014/index.html
Resulta que no me acordaba y la he mirado después de ver la de@jgbmur y pensar en lo de ponerlo en binario, y me encuentro con que en esa solución se usa una idea muy parecida. Pero en un principio es una solución distinta.
Y por si fuera poco, me vengo aquí a escribir este comentario y me encuentro con #30, que parece que habla en chino pero es lo mismo que la solución que he enlazado, donde viene explicado con mucho detalle.
Mañana pongo mi solución, que en un principio es distinta.
#31 #32 Les paso un link a una planilla excel online en la que se aplica mi propuesta. Si no se entiende pregunten y les explico (si puedo)
https://1drv.ms/x/s!AkxIr6j_WYMIoQKqFrKd7TZSq74o
#33, ¿has visto el link que he puesto? Ahí se entiende ya perfectamente.
#34 Sí, lo ví, y me asombró un poco haber llegado prácticamente al mismo procedimiento por vías distintas. Yo llegué a armar la planilla que adjunté en #33 al intentar programar el procedimiento de #20, pero se producían errores en algunos casos. Luego decidí tomar la idea básica de #3 pero aplicando la operación XOR (que estaba usando para las "transformaciones") en lugar de la suma. No se me hubiese ocurrido sin esos aportes.
#35, uhm, lo de #20 que te salía error en algunos casos... ¿te refieres a que no conseguiste programarlo bien o a que falla en algún caso?
#36 No sé. Supongo que no conseguí programarlo bien, o tal vez no lo entendí del todo.
#36 #37 Probé corregir el programa para representar correctamente la propuesta #20 y, cambiando algunos valores posicionales y eliminando algunas transformaciones conseguí que funcione bien para todos los casos. Es decir que la propuesta es correcta, aunque un poco más complicada que la otra. Avisen si les interesa que publique la planilla.
Bueno, pongo aquí la solución con la que di yo. Mi planteamiento fue hacerlo primero para 2x2, luego extenderlo para 4x4 y por último a 8x8. Mi solución es más fea que las anteriores. Copio lo que escribí en otro sitio (editando algún detalle), pero antes de copiar os comento que el problema me lo contaron con en vez de un tablero, 64 presos dispuestos en filas y columnas y en vez de una ficha de reversi, pues con un sombrero negro o blanco. El alcaide elige a una persona, el primer preso le cambia el gorro a alguien y el segundo debe adivinar el elegido por el alcaide. Vamos, lo mismo:
Si pensamos en un número binario de 64 cifras, la idea al final es que debes de poder agrupar los 2^64 números posibles binarios en 64 grupos (de igual tamaño) de forma que dado un número cualquiera (menor que 2^64) puedas con una operación de cambiar una cifra llevarlo siempre al grupo que quieras.
Y como no se me ocurría directamente, lo hago usando base 2 (binario), base 4 y base 16.
Primero te digo cómo tiene que traducir el segundo el preso señalado:
Lo primero es de los 64 presos hacer 16 grupos de 4 presos (podría hacerse haciendo matrices de 2x2). Cambiando un color por 1 y el otro por 0, cada matriz es un número binario que al pasarlo a decimal queda entre 0 y 15. Y hacemos esta asignación:
0, 1, 14 y 15 van a 0
2, 3, 12 y 13 van a 1
4, 5, 10 y 11 van a 2
6, 7, 8 y 9 van a 3.
Explico por qué esta asignación. Observad el primer grupo, en binario son 0000, 0001, 1110 y 1111. Observad que entre estos 4 números no hay 2 que se diferencien en exactamente 2 cifras. Y lo mismo pasa con los otros 3 grupos. Y gracias a ello observad que dado un número binario abcd, es imposible que podamos mandarlo por ejemplo al mismo grupo de dos formas distintas cambiando una cifra, ya que de ser así los dos números obtenidos se diferenciarían exactamente en 2 cifras. Así que los 4 números que se pueden generar a partir de abcd cambiando una cifra tienen que ir a conjuntos distintos y por ello cambiando una cifra podemos mandar a abcd al conjunto que queramos.
En fin, que teníamos una matriz en binario de 8x8 y ahora tenemos una matriz de 4x4 en base 4. Pues de nuevos dividimos en matrices de 2x2, cada matriz va a darnos un número de 4 cifras en base 4, y por tanto va a representar un número entre 0 y 4^4-1=2^8-1=255. Y hacemos como en el caso anterior, asignar así:
0,1,...,15, 240,241,...,255 van a 0
16,17,...31, 224,...239 van a 1
etc (salen 16 grupos, voy avanzando en los primeros 16 y retrocediendo en los segundos 16).
Igual que antes, estos grupos están formados por números en base 4 de forma que no hay 2 en el mismo grupo que se diferencien en 2 cifras (lo que nos asegura que dado un número en base 4 menor que 2^64 cambiando una cifra podremos meterlo en el grupo que queramos).
Y por último nos queda una matriz de 2x2 en base 16. Calculamos el número y repetimos. Si el número que nos sale está entre 0 y 63 o entre los 64 últimos nos quedamos con el preso 0, si está entre 64 y 127 o los 64 penúltimos con el segundo y así.
Esto le dará al preso 2 un número entre 0 y 63 y este número indicará cuál es el preso elegido.
Entendiendo esto se ve claro lo que tiene que hacer el primer preso. Ve la matriz y la convierte como hemos dicho en una matriz de 2x2 en base 16. Y sabe que variando una cifra de esas 4, podrá meterla en el grupo que quiera del preso elegido. Pero variar esa cifra se transforma en centrarse en una submatriz de 4x4 que representa al final un número de 4 cifras en base 4 y con esa matriz tiene que indicar un número entre 0 y 15. Pues para ello le basta variar una de las cifras de base 4 haciendo la asignación comentada antes. Para variar esa cifra le queda una matriz de 2x2 en binario, y ya ahí le basta cambiar un sombrero para asignar el número entre 0 y 4 que desee usando la primera asignación.
Pues esta es mi solución, en un principio muy distinta a las otras, aunque lo mismo es de alguna forma equivalente.
CC #31, #30, #18, #15, #7, #6, #5
#38 Me parece más sencilla la de la paridad la segunda no la veo, si por ejemplo el tablero es casi de un solo color, menos un par de fichas (o gorros de presos), pueden tener problemas (creo deducir)
#39, es más sencilla la otra. Pero no debería dar problema mi método por muy oscuro que sea el tablero. Dame un ejemplo práctico y la casilla a la que hay que ir y te digo qué ficha cambiar . Bueno, de hecho es fácilmente programable. Pero el otro método es más sencillo, desde luego.
#40 Pues será que no he entendido el método
#41, uhm, creo que hay un fallo en mi explicación, eso es lo que pasa al intentar escribir las cosas simplificadas . Luego lo reviso y digo exactamente cómo se hacen las asignaciones.
#41, bah, olvídate de mi método, se puede hacer, solo que las asignaciones que puse para pasar de 4 números de base 4 a un número en base 16 están mal (de hecho había puesto 16 grupos de 32 elementos, que sale 512 números en total por lo que se estaban repitiendo elementos). Las asignaciones se hacían de otra forma no tan sencilla de escribir (es más fácil pensar en la estructura que explicar a otro cómo va), y ¿sabes qué? Que en el fondo lo que me salía es un XOR de esos del binario ahí escondido, pero en su momento no lo relacioné porque no miré la otra solución hasta mucho después. Y me acabo de dar cuenta ahora que he repasado ambas
Pero bueno, la idea general de mi forma es que puedo crear una regla para que dado un número de 4 cifras en binario, cambiando una cifra y aplicando la regla puedo obtener el número de 0 a 3 que quiera. Luego con 4 cifras en base 4 puedo hacer lo mismo de 0 a 15 y con 4 cifras en base 16 lo mismo de 0 a 63.
De estos 3 pasos el primero sí que lo he puesto bien. Para los otros 2 dejo la idea.
Para el paso 2. Los números de 4 cifras en base 4 habría que agruparlos todos (256 números) en 16 conjuntos de forma que en cada conjunto no haya 2 números que tengan 2 o 3 cifras iguales
Para el paso 3 habría que hacer lo mismo que en el paso 2, pero ahora con cifras en base 16 y 64 conjuntos.
Y si tengo que especificar cómo se crean esos grupos, sale muy rollero de escribir
#43 Yo en un principio había pensado en clases de equivalencia, lo de la "distancia" entre los números binarios lo habíaa entendido, pero aún así no veo cómo con un sólo cambio podías "poner" la clase de equivalencia que quisieras ya que aún con todo eso la distancia entre cada par de clases de equivalencia (no dentro de las mismas), puede, y de hecho sería mayor que dos, por lo que no veo como se podía poner la clase de equivalencia del, pongamos 32, si la que "te encuentras" es la del 1 (o la del 64, lo mismo me da)
#45, si la distancia es el número de cambios de dígitos, la idea es que cualquier número esté a distancia 1 de todas las clases. Bueno, y de su clase un elemento a distancia 1 también.
#46 ¿Como el generador de un grupo en las congruencias?
#47, para que veas que se puede hacer así, vamos a plantearlo partiendo de una solución (hay una solución, lo hemos hecho por otro método), pues dos posiciones son congruentes si nos indican la misma casilla. Y así se crean las congruencias. La orientación pasa es que yo lo he hecho escalonadamente, pero sale un rollazo.
Anda, no te calientes la cabeza más y a resolver alguno de los problemas que quedan pendientes
#48 Perdón!, que quedó pendiente!?
#49, perdonado. Mirando solo veo uno pendiente
Número de jugadores de un partido
Número de jugadores de un partido
#50 Lamentablemente están cerrados los comentarios de ese problema
#53, anda, ni me había fijado, en este tipo de entradas deberían estar abiertos más tiempo.
#1 Zurditorium, cual fue tu solución?
#1 ¿Estás seguro que eran informáticos?
#51, no.
#7, ah, comentó que aunque no funcione me ha gustado la idea, es más simple que lo que pensé yo, y si llega a valer me habría dado vergüenza no haberlo sacado yo así
Bueno, yo no tiro por otro lado.
-El 1º preso númera las casillas del 1 al 64.
-Mira en que casilla cae el número y letra que le da el director (ejemplo: 18)
-Suma todas las casillas que tengan una ficha blanca (ejemplo: 1+5+7+16+23+54)
-Luego calcula el módulo de ese total con 64, osea se queda con el resto de su división (106%64 = 42)
--Si por casualidad el módulo (42) es igual a la casilla del director (18, en este caso no lo son), le da la vuelta la casilla 64; no importa que color tenga.
--Si no, coge el módulo y le resta la casilla del director (42-18= 24) y si hay una casilla blanca en la posición que da esa resta (24) le da la vuelta a negra.
--Pero si ya es negra, resta a 64 el módulo y le suma la casilla del director: (64-42+18= 40) y le da la vuelta a la casilla resultante a blanca.
El 2º preso lo único que tiene que hacer es sumar los valores de todas las fichas blancas y calcular su módulo con 64. El resultado es la ficha exacta (18).
#3 Sin despeinarse vaya... veo que sería como poco sospechoso que ambos prisioneros cayeran en eso, pero la verdad que yo no sé ni por donde empezar. Se me ocurren temas probabilísticos que no sabría acabar
Cc #0
#3, uhm, veo tu idea, es sumar o restar un número para que módulo 64 de el número deseado. NO FUNCIONA, tendría que pasar que el número a restar tenga ficha blanca o el a sumar tenga ficha negra (bueno, el caso 64 funciona siempre). Te pongo un ejemplo, variando tu ejemplo, pon blancas
1, 4, 5, 7, 16, 23, 20, 40, 54
He añadido 4, 20 y 40, así que da modulo 42 igualmente. Y el director ha elegido la 18.
42-18 es 24, negra así que no le damos la vuelta, pasamos al siguiente paso. Nos vamos al 40, el 40 ya es blanco, no puedes darle la vuelta a blanca.
Así que tú método faltaría en mi ejemplo. Aunque la verdad es que si no me equivoco funcionaría en más del75% de las veces.
#5, los presos hablan el día antes del juego, me ha faltado especificarlo, aunque obviamente tenía que ser así. No es que a los dos se les ocurra lo mismo, es que pueden hablar entre sí.
#8 Ja ja, mierda, es verdad
#3 Tengo que aclara que los dos últimos pasos son así porque 24 es mayor que 18. Si fuera del revés entonces se invierten los colores de esos dos últimos pasos. Lo que quiero decir que es posible siempre darle la vuelta a una sola ficha para que el módulo del total del valor de las blancas entre 64 dé siempre como resultado la ficha del director.
Indicación:
Como ya he dicho puede haber soluciones distintas. Yo me lo planteé intentando resolverlo primero para el caso de cuadrados de 2x2 (y no de 8x8). Así se puede hacer de forma medianamente fácil. Luego podéis probar a hacerlo en un tablero de 4x4 (que se puede ver como un tablero de 2x2 donde cada casilla es un nuevo tablero de 2x2).
Bueno, yo lo estructuré así, pero también podéis probar a pensar un caso más sencillo ahí, un tablero de 1x2.
Si intentáis algo de esto, poned vuestros progresos por aquí.
Por cierto, la solución no sacada por mi supuestamente usa una operación muy conocida en codificación y decodificación de mensajes con cálculo binario. Digo supuestamente porque es lo que me dijo el que me propuso el problema, pero no controlo el tema. Pero vamos, lo menciono por si a alguien se le enciende la bombilla.
#28, ups, cierto, va perfecto, no sobra ni una.
#26, bueno, de hecho en tu solución sobra una casilla, la primera no pinta nada, da igual cómo esté la moneda, ¿no? Yo de España, estaba de fiesta y por eso vi tus respuestas.
#27 Claro, pero es necesaria para el caso en que el numero representado en el tablero se corresponda con el pedido, hay que hacer un cambio obligatoriamente y es esa casilla.
A mi no se me ocurre nada
#0 yo no veo como por ningún sitio
#15, mira lo que ha hecho #13 a ver si por ahí te inspiras
#16 No, si lo he visto, pero no veo como "escalarlo"
Para un tablero 2x2.
Todas las fichas del mismo color: volteamos la ficha del director.
Una ficha es distinta: dejaremos todas iguales para indicar que es la A1; haremos que haya 2 blancas y 2 negras y la del director será la que coincida en color con la A1.
Hay 2 y 2: podremos cambiar una para que quede "sola" la ficha del director.
#13, pues para un cuadrado de 2x2 lo que dices vale (si no me equivoco). Ahora a ver si subes un nivel más .
Aún no me he puesto con el 3x3, pero pensad que tiene 3 tipos de casillas: central, esquinas y las otras (que no sé cómo llamarlas). Algo asi:
EOE
OCO
EOE
#18, uhm, no sé yo si es buena idea diferenciar casillas, cuando w realidad todas son iguales, es decir, el problema se podría hacer igualmente estando en un cuadrado o en fila.
Me faltó que antes los presos deberán acordar entre ellos de que casilla va a representar una inversión de que casillas.
Encontré una forma, no se si es la más fácil tampoco, tardé bastante más que dos horas...
y escalarlo me costó más que el kilimanjaro...
Es así:
A las primeras 7 casillas les damos los valores 0,1,2,4,8,16,32; estos se van a sumar
para dar la casilla final. (las casillas van numeradas de 0 a 63).
y con el resto de las casillas les pongo una condición a cada una de ellas, que cada una
representa una inversión de algún subconjunto de las anteriores (sin incluir la casilla 0), desde todos los subconjuntos de dos casillas hasta todas las que van de la 1 a la 7.
(pasando por las combinaciones de 3 casillas, 4 casillas, 5 casillas, 6 casillas)
Voy a necesitar 15 casillas para representar las inversiones de combinaciones de 2 casillas (estas de las primeras),
20 para las de 3, 15 para las de 4, 6 para las de 6 y 1 para las de 6.
La suma de estas casillas me da 57 (15+20+15+6+1), si le sumamos las 7 casillas iniciales
cubrimos las 64 del tablero.
Con esto no importa el tablero de origen podemos representar cualquier casilla, eligiendo
la suma original o la inversión aplicable (todo por medio de la elección de una casilla).
#20, no sé si es porque llevo 3 cubatas encima, pero no entiendo ahora mismo tu explicación. ¿Podrías intentar darla más detallada?
#23 Tengo una lista de 7 casillas que valen 0 (esta queda aparte ya que no modifica), 1,2,4,8,16,32; tengo que conseguir una combinación de unos y ceros
en esas casillas para obtener cualquier numero entre 0 y 63, sin importar el tablero inicial.
Para eso aprovecho las otras 57 casillas, supongamos que las 64 casillas están en cero (negro?),
y necesito sumar 21, eso significa 101010 (1+0+4+0+16+0)=21. La única forma de hacerlo es invertir esas tres fichas,
que no está permitido. Para eso a una ficha de entre las 57 le habíamos asignado previamente con el otro preso
que si valía 1 implicaba una inversión de esas tres fichas.
Como normalmente las otras casillas de las 57 también van a poseer unos, lo que se deberá hacer es:
1) Aplicar una por una todas las inversiones dadas por las 57 sobre las 6 casillas.
2) Ver que casillas de las 6 hay que invertir para obtener el valor deseado.
3) Buscar en una tabla de 57 entradas que casilla se corresponde con esas inversiones.
4) invertir esa casilla.
5) entra el otro preso, aplica todas las inversiones, suma el resultado y obtiene el valor deseado.
#24, vale, ahora he entendido exactamente lo que querías hacer, y parece que la solución es correcta (mañana sin efectos etílicos encima intento mirarlo de nuevo
). Y es distinta a la mía. Mañana o pasado te pongo la mía, y otra más que creo que también es distinta a la tuya.
Ah, y viendo a qué horas escribes... ¿De dónde eres? Podrías ser americano, aunque que por tu nick podrías ser hasta murciano
#25 Argentino, de la Capital; tu?, supongo que esas soluciones deben ser equivalentes. Interesante que alcance y no sobre ninguna casilla...
A ver si les va mi propuesta. Los pasos serían los siguientes:
a) Se numeran las casillas del 0 al 63, y las filas y columnas de 0 a 7. Cada casilla toma el valor numérico asignado.
b) Se realiza un XOR binario (bit por bit) de los valores de todas las casillas marcadas con 1 (por ejemplo con fichas blancas), obteniendo lo que llamaremos "valor actual", que es un número de 6 bits, entre 0 y 63.
c) Se realiza un XOR del valor actual con el valor deseado, que es otro número de 6 bits con el valor de la casilla elegida por el director, obteniendo el número de casilla de la ficha que hay que invertir.
d) Se da vuelta la ficha de la casilla del resultado
e) El nuevo valor actual, calculado como en el paso b), es el número de la casilla elegida por el director. El segundo preso sólo tiene que calcular dicho valor a partir de la configuración del tablero.
Expresando los valores en numeración octal, el primer dígito equivaldrá al de la fila y el segundo dígito al de la columna.
#30 Hola Guiver, todavía trato de entenderlo
#30 La entendí!, y es más elegante que la mía.