Para el enunciado correcto del problema y demas pueden ver en http://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong/

El siguiente argumento demuestra que si los prisioneros escuchan lo que dicen los anteriores entonces se pueden salvar todos menos el primero.

Cuando hablemos de “la tira” nos referimos a la secuencia de 0,1 que en el i- esimo lugar tiene un 0 si el sombrero del i+1- esimo prisionero es blanco y un 1 si es negro (notar que no nos interesa el color del sombrero del primer prisionero).

Cada prisionero, en su turno y sabiendo que todos los anteriores salvo el primero adivinaron, conoce toda la tira salvo el digito que corresponde al color de su sombrero, esto porque cada prisionero puede ver el color de los sombreros de todos los que tiene delante suyo y escucha lo que adivinan los que tiene detras (que lo van a hacer de forma correcta).

La estrategia de los prisioneros se basa en el siguiente lema que demostramos al final:

Lema: Se puede partir a las tiras de 0 y 1 en dos conjuntos de forma que dos tiras que coinciden en todos los lugares salvo uno estan en conjuntos distintos.

Llamemos a uno de los conjuntos bueno y al otro malo. El primer prisionero en hablar dice blanco si la tira pertence al conjunto bueno y negro si pertenece al conjunto malo. Ahora, cada prisionero en su turno conoce toda la tira salvo un digito (el que corresponde a su color) y sabe si es buena o mala (porque lo dijo el primero en hablar). Pero entonces puede deducir si el digito que falta es 0 o 1 porque diferentes elecciones (0 o 1 ) da que la tira pertenece a diferentes conjuntos (bueno o malo).

Para ver que se puede dividir a las tiras en dos conjuntos como en el lema podemos proceder de dos maneras.

1) Digamos que dos tiras son parecidas si son iguales salvo por finitos lugares. Esto es una relacion de equivalencia, si partimos al conjunto de tiras en clases de equivalencias y tomamos una tira distinguida por cada clase, entonces podemos poner en el primer conjunto a las tiras que coinciden con una tira disintguida en todos los lugares salvo por una cantidad finita par y al resto en el segundo conjunto (que seran las que coinciden con una tira distingida salvo por una cantidad finita impar de digitos).

2) Notemos que esto equivale a pintar con dos colores el grafo de vertices las tiras y con aristas que corresponden a pares de tiras iguales salvo por un digito. Tenemos entonces que verificar que no tiene ciclos de longitud impar (*).  Pero como una arista equivale a cambiar un digito, entonces los ciclos deben ser pares pues debemos cambiar una cantida par de veces para volver a la misma tira.

(*) Un grafo (finito o infinito) se puede pintar con dos colores de forma que no haya dos vertices del mismo color conectados por una arista si y solo si no tiene ciclos de longitud impar.

Una respuesta to “Prisioneros”

  1. charlydif said

    Por cierto, la siguiente variante del problema me gusta:

    En una fiesta hay una cantidad infinita de personas cada una de las cuales tiene un sombrero con un numero real. Cada persona sabe los numeros de todas las demas pero no el suyo, entonces las personas tienen una estrategia para que todas adivinen su numero salvo una cantidad finita de personas (todas tienen que arriesgar al mismo tiempo).

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: