Azarosa taba
Concurso de El Pais, octubre de 2011
Si lanzamos repetidas veces una moneda que no esté trucada y anotamos 1 cuando sale cara y 0 cuando sale cruz, conseguimos una serie de cifras binarias o bits que es aleatoria y no tiene sesgo. Por ejemplo, yo he conseguido una que empieza así:
0 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1
Decimos que la serie no tiene sesgo porque en cada tirada la probabilidad de 1 es igual a la probabilidad de 0. Decimos que la serie es aleatoria porque nunca se puede adivinar el resultado que saldrá en la siguiente tirada, a diferencia de lo que, por ejemplo, pasa con estas otras series:
0 1 0 1 0 1 0 1....
0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1...
dentro de las cuales detectamos un patrón con el que, si conocemos unos cuantos bits de la serie, podemos adivinar cuál será el siguiente bit. (Apostaríamos tranquilos a que las dos últimas series no han sido obtenidas lanzando una moneda).
¿Para qué sirven las series de bits aleatorias y sin sesgo? Por ejemplo, para generar números aleatorios del tipo que se usan para sortear el ganador en cada desafío matemático de EL PAÍS. Pero esta semana no tenemos ninguna moneda. ¿Que podemos hacer?... Por suerte, hemos conseguido unas tabas.
La taba es un hueso que los mamíferos tenemos en el pie. Las de los corderos se usan para jugar desde tiempo inmemorial: aparecen en estatuas romanas y también en el cuadro Juegos de niños de Brueghel el Viejo. Los habitantes de algunos lugares de España mantienen una ancestral tradición de reunirse para apostar usando tabas. Por ejemplo, estas que me han prestado vienen de Colmenar Viejo, cerca de Madrid, en donde se juega con ellas los días de San Andrés y de Santa Lucía.
Cualquier taba está cargada porque no es simétrica respecto a su centro de gravedad y, aunque tiene cuatro formas distintas de caer, nosotros tendremos en cuenta dos posibles resultados. Vamos a lanzar 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. Notemos que los tamaños y las formas de las tabas varían y por eso cada taba tiene su propia carga, distinta de las demás.
El desafío de esta semana es el siguiente: a partir de la serie aleatoria de bits conseguida lanzando repetidamente una misma taba, obtener 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.
La solución a este desafío debe incluir una breve explicación de las operaciones y los pasos que llevan desde la serie de bits de la taba hasta una serie aleatoria de bits sin sesgo. La solución ha de funcionar usando una única taba, que puede ser cualquiera: por ejemplo, una de las tres que yo tengo aquí u otra taba que vosotros tengáis.
1 comentario:
Se me ocurren tres soluciones, cada una con pros y contras:
1) Se podría buscar una forma de eliminar el n-ésimo resultado (por ejemplo, si para que no tenga sesgo tiene que eliminarse el quinto 1 que salga de la serie de modo que quede equilibrado).
Por ejemplo: tenemos 100101111010111101100111. Hay 16 unos y 8 ceros. Sobran 8 unos, por ello, eliminamos cada segundo uno:
100(1)01(1)1(1)010(1)1(1)10(1)100(1)1(1),
nos queda 1000110101101001
Esta primera opción tiene el problema de que si sabemos cuántos unos (o ceros) llevamos, podemos apostar con comodidad a lo que tiene más probabilidad de salir. Es decir, globalmente carece de sesgo, pero localmente sí. Además, tenemos que hacer unas cuantas tiradas anteriormente para ver cuál es la probabilidad de cada opcíon. Y por otro lado, si queremos precisión se complica (si el 1 aparece el 63.12% de las veces, ¿qué hacemos?).
2) Se podría invertir el valor de un bit en función de la tirada. Por ejemplo sea la tirada n-ésima. Si n es par, el valor del bit correspondiente se contabiliza tal y como se ha comentado. Si n es impar, se invierte el valor del bit. De este modo, si la secuencia original es:
100101111010111101100111
invirtiendo las posiciones pares queda:
110000101111101000110010
Esto tiene la ventaja de que es más sencillo (no necesita cálculos de reajuste a posteriori), y no elimina información. Sin embargo, si sabemos en qué tirada estamos, sigue siendo posible saber qué tenemos que apostar para tener más probabilidad de ganar.
3) La tercera forma elimina mucha información, pero hace imposible saber qué apostar incluso si sabemos en qué tirada estamos: a) agrupamos los resultados por parejas. b) cuando haya dos parejas iguales (11 ó 00), no se contabiliza. c) cuando sean diferentes (10 ó 01), se contabiliza sólo el primer bit. Así, en el ejemplo anterior, si tenemos:
110000101111101000110010
Por parejas sería:
10,01,01,11,10,10,11,11,01,10,01,11
Siguiendo estas reglas, se traduciría por:
1, 0, 0, -, 1, 1, -, -, 0, 1, 0, -
Que es lo mismo que:
10011010
Publicar un comentario