martes, 26 de abril de 2011

C-El problema de los 30 sombreros

Me cachis... para una vez que acierto, otras 424 personas también lo hacen y no me toca el sorteo. El sabado os comentaba lo de "El País" y la Real Sociedad Matemática Española, que han preparado un concurso con problemas de matemática recreativa para que la gente concurse. Yo lo he pillado tarde y me enteré en el sexto problema.
En un principio, se me ocurrió una solución simple en 5 minutos y la expuse por si alguien queria participar porque no era mi intención, ya que a mi solo me valen de entretenimiento y para picarme (¿Que yo me pico?).
El problema vino después, al acostarme, que mi mente dijo que "nanai" y que había que optimizar la solución. El enlace con el problema y la solución esta aquí, pero ahora os expongo, si os da curiosidad, como llegué a la solución y de que manera más estupida perdí horas de sueño. Esto fue lo que les escribí a los de "El País":
El numero de presos que se salvan seguro con esta estrategia es 29.
Sea X el numero de sombreros blancos entre los sombreros del 1 al 29.
Al ser 29 un numero impar, habrá diferencia de paridad entre X y 29-X.
La estrategia a seguir será que el 30º indique blanco si X es par y negro si es impar.
Los presos 1º al 29º, con la informacion del 30º, saben si X es par o impar. El i-esimo preso (i=1,...,29) cuenta el numero de sombreros blancos, tanto los que ve como los que han dicho sus compañeros con posicion posterior en la cola (excepto el 30º). Si la paridad de X-{sombrero i} es distinta de X, el color del sombrero del preso i-esimo es blanco para conservar la paridad de X. En caso de que la paridad de X-{sombrero i} sea la misma que la de X, entonces el color del sombrero i-esimo es negro.

El proceso para llegar a esto fue el siguiente (llegue a los 29 presos a las 3:35 de la mañana ya que no podía quitármelo de la cabeza):
-15 presos salvados: Empecé con lo más lógico, si el preso 30º decía el color predominante entre los predecesores, se garantizaba que se salvaran 15 presos.
-20 presos salvados: Si el preso 30º indicaba blanco si el color del 28º y el 29º son el mismo y negro en caso contrario, tanto el 28º como el 29º sabrán su color pues el 29º sabe el color del 28º y viceversa.
-25 presos salvados: Se usan los presos 26º al 30º para definir el número de gorros blancos del 1º al 25º en forma binaria (blanco=0, negro=1). Con 5 presos se puede definir del 0 al 31, que es lo necesario para obtener el 25 como máximo. Como los 25 primeros saben el color de los restantes 24, se salvarían.
-26, 27, 28 y 29 presos salvados: Me di cuenta de que no hacia falta poner en binario el número entero de gorros blancos pues haciendolo por módulos tambien era posible determinarlo con exactitud, así que fui reduciendo el numero de presos que definían el numero de gorros blancos en forma binaria hasta llegar a modulo 2.

Si veís la solución, casi la calqué. Pensaba, tontamente, que creía que me iba a tocar porque mi solución era muy original y posiblemente esté por ahí en algún libro de acertijos. Como ahora direis que es muy facil decir "yo lo sabía" con la solución por delante, me comprometo a poner la solución, y el proceso de como he llegado a ella, del próximo desafío.
Seguro que ahora lo ponen muy difícil y hago el mayor de los ridículos, o todo el mundo me copia la solución y se ganan los libros a mi costa. No hay que ser avaricioso y compartiré mis ideas para que otros ganen (fantasma!!!!).

No hay comentarios:

Publicar un comentario