1r ciclo Infinitos prisioneros

[angel relativamente]

Este problema es un clásico, aunque no he visto que se haya posteado antes en la web. La solución es lo suficientemente bonita para intentarlo. Dejaré pistas si se me piden

En una prisión infinita tenemos un número infinito de prisioneros. Les dicen que al día siguiente les van a poner en fila india y sabrán qué posición de la fila ocupan, de modo que el que esté en la posición n-ésima verá a los infinitos que tiene delante pero no a los n-1 que tiene detrás, ni a sí mismo. Después les colocarán un sombrero a cada uno que saben que puede ser o bien de color rojo o bien de color azul. Al unísono, tendrán que gritar todos el color del que creen que tienen su sombrero. Si aciertan los liberan y si fallan mueren. El día anterior les dejan pactar una estrategia. Suponiendo que los prisioneros tienen una capacidad infinita de cálculo y procesamiento, ¿qué estrategia pueden pactar para que solo muera un número FINITO de prisioneros?


Bonus: ¿Y si en lugar de haber sombreros rojos o azules puede haber de cualquier longitud de onda visible $\lambda \in \mathbb{R}$?

[Richard R Richard]

Re: Infinitos prisioneros

Hola Angel bonito problema. Espere un tiempo prudencial para enviar mi solución muy naif

Ocultar contenido

Mostrar solución Ocultar solución

solo podría morir 1 y si tiene suerte no muere

la estrategia infantil sería tomar distancia en la fila india extendiendo un brazo, el izquierdo por ejemplo si es azul, y derecho si es rojo el sombrero del que tiene delante, con solo tocarle el hombro sabra el color que tiene ,por lo que el $-\infty$ que se supone no tiene a nadie detrás, tiene un 50% de chances de vivir o morir.

cualquier decisión basada en probabilidad dará un numero infinito de muertos.

[angel relativamente]

Re: Infinitos prisioneros

Hola.
En efecto la solución no va por ahí. Ni se pueden tocar, ni se pueden decir cosas al oído, ni se pueden comunicar de ninguna manera.
Por otro lado, cuando digo que cada uno sabe qué posición tiene ($n$), tomo $n\in \mathbb{N}$ y no entero. Quiero decir con esto que no hay un prisionero $-\infty$ (si es que acaso eso tiene sentido), sino que empieza en $n=1$ hasta el infinito.

Dejo una pista:

PISTA

Ocultar contenido

Mostrar solución Ocultar solución

Cada persona ve quasi-toda la cadena, pues la ve toda salvo un número finito. Es decir que lo que ven el prisionero 1 y el prisionero 1000 es prácticamente lo mismo...

[angel relativamente]

Re: Infinitos prisioneros

Dejo la solución ya que ha pasado un tiempo prudencial y el problema es muy bonito:

Ocultar contenido

Mostrar solución Ocultar solución

Cuando les coloquen los sombreros, se formará una sucesión infinita de sombreros rojos y azules, que representaré con 0s y 1s por comodidad. La idea es que los prisioneros han de saber qué sucesión les ha tocado, a excepción de un número finito de términos. Pero eso ya lo saben pues cada prisiomero ve toda la sucesión, salvo un número finito (el suyo y los que están detrás), por lo que solo les quedará pactar una estrategia para que todos se identifiquen en la misma sucesión. La estrategia es como sigue: Definen la siguiente relación de equivalencia (se deja como ejercicio para el lector demostrar que lo es): Dos secuencias infinitas de ceros y unos están relacionadas si son iguales a partir de un término. Por ejemplo las secuencias 0110000000... y 10000000... están relacionadas. Con esta relación les sale una partición de todo el conjunto de secuencias infinitas de ceros y unos en clases de equivalencia, y como es habitual de cada clase de equivalencia escogen un representante. Pues ya está, el día de la verdad les ponen los sombreros y ven delante de ellos toda la cola de la sucesión. No tienen ni idea qué sucesión es, porque desconocen los primeros términos, pero sí saben a qué clase de equivalencia pertenece. Y como todos identifican la clase y saben su posición, tomarán como si la sucesión que les ha tocado fuese la representante que previamente habían pactado de esa clase. Por ejemplo, si la sucesión que han escogido como representante es la 01001... El primero dira cero, el segundo dirá uno, etcétera. Obviamente esta sucesión no tiene por qué ser la que les ha tocado, pero como está en la misma clase solo diferirá en un número finito de términos, que son los prisioneros que morirán

Aun con la solución sé que es dificil de entender, releedla hasta convenceros que merece la pena. Si aun así no la entendeis preguntad

[Richard R Richard]

Re: Infinitos prisioneros

Si claro ángel suponiendo capacidad de cálculo ilimitada en cada uno para determinar de que clase se trata.

Ocultar contenido

Mostrar solución Ocultar solución

Pero segun lo que explicas cada uno debe ver hasta el final de la cola para reconocer la coincidencia con una clase y se me hace que es imposible

Y aunque estén relacionadas las series no se pueden saber los términos anteriores justamente lo que previo a la determinacion de la clase .o no lo he entendido

[Weip]

Re: Infinitos prisioneros

Me lo he estado pensando durante el día pero no me ha salido. La solución que has puesto es brutal.