Mes: noviembre 2011

Vadym Paziy, estudiante de Doctorado en el Grupo de Física Nuclear de la Universidad Complutense y antiguo guía en la Olimpiada Matemática Internacional celebrada en 2008 en Madrid presenta el 34 desafío con que EL PAÍS celebra el centenario de la Real Sociedad Matemática Española.

Envía tu respuesta antes de las 0.00 horas del martes 8 de noviembre (medianoche del lunes, hora peninsular española) a problemamatematicas@gmail.com.

Desafío: Dos hermanos gusanitos de seda han discutido quién de los dos llega antes a casa desde un punto que está en la base de una colina. La colina tiene forma de cono recto con una base circular de 1 metro de radio y una ladera de longitud 2 metros, como se muestra en este dibujo. La casa se encuentra en el punto diametralmente opuesto a aquel en el que se encuentran los gusanitos. Uno de los gusanitos es más astuto y sabe calcular el camino más corto, mientras que su hermano es más alegre y escoge el primer camino que encuentra, la base del cono.

Sin embargo, ninguno de los dos sabe que en su casa les está esperando una golondrina muerta de hambre que se comerá al primero que llegué. En el instante que el gusanito alegre echa a andar el astuto se pone a calcular la trayectoria óptima, en lo que emplea exactamente 3 minutos. Una vez la tiene empieza su camino. Suponiendo que los dos gusanos se desplazan con la misma velocidad de 1 mm/s, el desafío consiste en determinar quién será la víctima de la golondrina ¿el gusanito alegre o el gusanito astuto?

Para que la respuesta sea considerada correcta habrá que indicar no sólo el gusanito-víctima, sino también los cálculos que han llevado a la conclusión.

Recordemos el desafío. Lanzamos repetidas veces una misma taba y anotamos 1 cuando queda hacia arriba la parte hundida del hueso y anotamos 0 si la taba cae de cualquier otra forma. La taba tiene carga, así que -casi seguro- obtendremos una serie aleatoria de bits con sesgo. Lo que pedíamos era un procedimiento para obtener, a partir de la serie aleatoria de bits conseguida lanzando la taba, una serie de bits -que necesariamente será más corta que la serie de partida- que no se pueda distinguir de la que produce una moneda sin trucar, es decir: obtener una serie de bits aleatoria y sin sesgo.

Llamamos serie resultado a la serie de bits que se pide construir en el desafío. Una solución sencilla es la siguiente:

1) Tomamos la primera pareja de la serie de bits generada con la taba.

1.a – Si la pareja es repetitiva (es decir o bien 00 o bien 11) la desechamos.

1.b – En otro caso (es decir o bien 01 o bien 10) nos quedamos con el primer bit de la pareja, que será el primer bit de la serie resultado.

2) Repetimos el primer paso con la siguiente pareja de la serie de bits de la taba. Si no es repetitiva, el bit que extraemos de esta pareja se añade al final de lo que llevamos de la serie resultado. Y así sucesivamente hasta agotar la serie de bits de la taba.

Para demostrar la validez de esta solución vamos a usar la letra p refiriéndonos a la probabilidad de que, tras lanzar la taba, queden hacia arriba las partes hundidas del hueso, lo que corresponde a un 1. En consecuencia la probabilidad del 0 es 1-p. Calculamos la probabilidad de que, en la serie de la taba, salga una pareja no repetitiva. Como cada lanzamiento es independiente del anterior multiplicamos las probabilidades individuales:

Probabilidad del suceso 01 = (1-p) × p

Probabilidad del suceso 10 = p × (1-p)

Sabemos que el orden los factores no altera el producto y entonces notamos que ambos sucesos 01 y 10 tienen la misma probabilidad de ocurrir dentro de la serie de la taba. Por este motivo la serie obtenida siguiendo este método no tiene sesgo. Además conserva la propiedad de ser aleatoria que le viene de que también es aleatoria la serie original de la taba. No sabemos cuál es el valor concreto de p, sin embargo ¡no hace falta saberlo! Si usamos una taba distinta tendrá posiblemente otra carga y en consecuencia otro valor para p, sin embargo esto no impide que la solución siga funcionando.

La mayoría de las respuestas que han resuelto correctamente el desafío han seguido este camino. Varias recuerdan expresamente que este algoritmo se atribuye a J. von Neumann. Continuar leyendo “Solución: Cómo eliminar el sesgo de una taba”