Con muchos prisioneros, los acertijos de sombreros ya son extraños. Con infinitos, aparece una idea aún más rara: no intentar salvar a cada uno por separado, sino hacer que todos se equivoquen solo en un pequeño número de lugares.
Los prisioneros infinitos
Enunciado
Hay infinitos prisioneros en fila, numerados:
Cada uno lleva un sombrero blanco o negro.
Supondremos que la visión es ideal: el prisionero número n puede ver perfectamente todos los sombreros de los prisioneros con número mayor que él:
Es decir, ve una secuencia infinita de sombreros. No ve su propio sombrero ni los sombreros de los prisioneros con número menor.
Antes de empezar, los prisioneros pueden acordar una estrategia común. Después se colocan los sombreros, y todos deben decir a la vez el color de su propio sombrero, sin comunicarse.
¿Pueden garantizar que solo se equivoque un número finito de prisioneros, pase lo que pase?
Ver solución
Solución
Sí.
Imaginemos una configuración completa de sombreros como una secuencia infinita:
Diremos que dos configuraciones son casi iguales si solo se diferencian en un número finito de posiciones.
Por ejemplo, si dos configuraciones solo cambian en los prisioneros 2, 17 y 104, las consideramos casi iguales.
Ahora agrupamos todas las configuraciones infinitas en clases: dos configuraciones están en la misma clase si son casi iguales.
Antes de empezar, los prisioneros hacen este pacto: de cada clase eligen una configuración representante.
Ahora veamos qué hace el prisionero número $n$.
Él ve todos los sombreros desde $n+1$ en adelante. No conoce los primeros $n$ sombreros: los de los prisioneros $1,2,\ldots,n$.
Pero eso es solo un número finito de sombreros. Por tanto, cualquier configuración compatible con lo que ve el prisionero $n$ solo puede diferir de la configuración real en esas primeras $n$ posiciones.
Así que todas las configuraciones compatibles con lo que ve pertenecen a la misma clase. Es decir: el prisionero $n$ no sabe cuál es la configuración exacta, pero sí sabe a qué clase pertenece.
Entonces consulta el representante pactado de esa clase y dice el color que ese representante tiene en la posición $n$.
Todos los prisioneros hacen lo mismo.
¿Por qué funciona? Porque la configuración real y el representante elegido pertenecen a la misma clase. Eso significa que solo difieren en un número finito de posiciones.
Los prisioneros se equivocarán exactamente en las posiciones donde la configuración real y el representante no coincidan. Y como esas posiciones son finitas, solo habrá un número finito de errores.
Esta estrategia es no constructiva. Demuestra que existe una forma de elegir las respuestas, pero no da una receta práctica y finita para escribir todos esos representantes.
Esa es precisamente la rareza del acertijo: la solución no consiste en adivinar sombreros uno por uno, sino en acertar una configuración que sea igual a la real salvo en un número finito de lugares.
Respuesta: sí. Pueden garantizar que solo se equivoque un número finito de prisioneros.