Solución del problema de marzo, 2008

El problema:

PM76: Marzo 2008   Cuatro estudiantes, Andrés, Bárbara, Clara y Daniel van a ganar un premio si todos tienen éxito en la siguiente tarea: Uno por uno serán introducidos en una habitación donde hay cuatro cortinas, numeradas de uno a cuatro. Se han escrito las letras A,B,C,D en cuatro tarjetas -- cada letra en una y sólo una tarjeta -- y las tarjetas han sido puestas al azar detrás de las cortinas, una detrás de cada cortina. Cada estudiante podrá mirar detrás de dos cortinas de su elección. El estudiante tendrá éxito si encuentra una tarjeta con su inicial detrás de una de las dos cortinas. Si todos los estudiantes tienen éxito, el grupo gana. Si uno o más fallan, el grupo pierde. Se permite a los estudiantes desarrollar una estrategia en común antes de comenzar la tarea, pero una vez que cada estudiante ha estado en la habitación, no se le permitirá comunicarse con el resto, ni con palabras ni con señales. Los estudiantes que no han estado todavía en la habitación tampoco podrán saber si los anteriores tuvieron éxito o no. Si cada estudiante mira detrás de dos cortinas elegidas al azar, tendrá una chance del 50% de ganar, y el grupo tendrá una chance de ganar del 6.25%. El desafío es desarrollar una estrategia (y justificarla) que de al grupo una probabilidad de ganar de 40% o más.

Respuestas correctas:

Encontramos este problema en una revista de la Casualty Actuarial Society, que usaba el problema sin referirse a su fuente. Pero la amabilidad de Fondanaiche nos ha provisto de una referencia. En una forma algo diferente, el problema fue inventado originalmente por el informático Peter Bro Miltersen de la Universidad de Aarhus, Dinamarca. Aparece en un paper del 2003 sobre búsqueda de subcadenas, presentado en una conferencia sobre autómatas, lenguajes y programación. [Vea las referencias en Science News Online www.sciencenews.org/articles/20060819/mathtrek.asp.]  Fue popularizado por Peter Winkler y aparecerá en el Volumen II de sus Mathematical Puzzles: A Connoisseur's Collection (A.K. Peters).  Recibimos soluciones correctas de Bojan Basic (Serbia), Gérard Billion (Francia), Lou Cairoli (USA), Philippe Fondanaiche (Francia), Jacques Mertzeisen (Francia), John T. Robinson (USA), and A. Teitelman (Israel).  Todos propusieron la misma estrategia:

La solución:

Los estudiantes comienzan por establecer una correspondencia entre sus iniciales y las cortinas, obteniendo así un ordenamiento de las cortinas sin ambigüedad. Cada estudiantes mira primero detrás de la cortina que tiene su inicial. Si la tarjeta detrás de la cortina coincide con su inicial, tiene éxito y puede irse; si tiene otra letra, mira detrás de la cortina correspondiente a esa letra. Por ejemplo, Andrés mira primero en la cortina que corresponde a la “A”, y va a tener éxito si las tarjetas detrás de las cortinas están en alguno de los 6 órdenes

ABCD, ABDC, ACBD, ACDB, ADBC, o ADCB.

Si en cambio encuentra las letras B o C o D detrás de su cortina, ganaría con los órdenes

BACD, BADC; o CBAD, CDAB; o DBCA, DCBA.

Entre estas 12 permutaciones favorables a Andrés todas salvo dos, ACDB y ADBC, son también favorables a Bárbara. Coincidentemente, las 10 restantes también llevan a Clara y Daniel al éxito, o sea que el grupo tiene éxito en 10 posibles permutaciones de las letras. Dado que el total de permutaciones es 4!=24, la probabilidad de que el grupo tenga éxito es 10/24, que es aproximadamente 41.67%.

Comentarios.

1. Este problema es un claro ejemplo de la importancia de explotar toda la información disponible para poder mejorar las chances de tomar la decisión correcta. Como se decía al enunciar el problema, si los estudiantes no usan la información obtenida por su primera elección, la chance éxito baja de 41.67% a 6.25%. Compare la situación con el estadístico que basa su decisión en promedios en lugar de usar toda la información disponible. Como ejemplo, muchos de nosotros nos preguntamos por tal estrategia cuando viajamos en aviones cuyos asientos parecen diseñados para un humano promedio sin tener en cuenta la distribución de tamaños; parece también que el promedio que usaron es el de algún siglo en que la gente era mucho menor.
   
   
2. Cuando el número de posibilidades es tan pequeño como en nuestro problema, la mejor manera de contar las posibles soluciones es hacer una lista. Tanto Billion como Robinson estudiaron generalizaciones que involucran un mayor número de participantes, donde una lista ya no es práctica. Consideremos el problema con n estudiantes, cada uno con dos posibilidades, y la misma estrategia. Sea N_n el número de permutaciones exitosas de sus nombres. El número de permutaciones exitosas para el primer estudiante es igual al número de permutaciones exitosas para los restantes n – 1 participantes, esto es N_n–1. También puede tener éxito si el nombre detrás de la primera cortina lo lleva a una cortina donde está su nombre; esto lleva al éxito del grupo en (n – 1)N_n–2 permutaciones (N_n–2 permutaciones para cada uno de los n – 1 nombres posibles detrás de la primera cortina). Entonces N_n = N_n-1 + (n – 1)N_n-2. La probabilidad de que el grupo de n estudiantes tenga éxito es P_n= N_n/n!.  Como N₁ = 1 y N₂ = 2, los primeros valores son
               N₃ = 4      P₃ = 4/6 ≈ .67
               N₄ = 10      P₄ = 10/24 ≈ .417
               N₅ = 26      P₅ = 26/120 ≈ .217
               N₆ = 76      P₆ = 76/720 ≈ .106.
         Billion y Robinson consideraron también la posibilidad de que el grupo de n estudiantes pudiera elegir k cortinas para mirar. La estrategia es la misma, es decir cada estudiante comienza con la cortina correspondiente a su nombre, luego elige la cortina correspondiente al nombre que encontró, y así siguiendo hasta encontrar su nombre o fallar k veces. Vemos que el grupo va a ganar siempre que la permutación de los nombres detrás de las cortinas no tenga ciclos de longitud mayor que k.  Contar el número de permutaciones con k o menos ciclos es fácil (con una computadora) con una fórmula recursiva tal como la que se encuentra en la enciclopedia de sucesiones de Sloan,
   http://www.research.att.com/~njas/sequences/A057693.
         El problema original de Winkler mencionado al comienzo era encontrar la probabilidad de éxito cuando n = 100 estudiantes tienen cada uno k = 50 elecciones.  Aquí es más fácil contar el número de permutaciones que fallan – esto es, las permutaciones que tienen un ciclo de longitud 50 o más. La probabilidad de éxito es
   1 – 1/51 – 1/52 – … – 1/100 ≈ .3118.
         Esta probabilidad de 31% es realmente notable cuando se compara con la casi imposibilidad de éxito con una estrategia menos efectiva. Detalles referidos a esta versión del problema y su implementación pueden ser encontrados en The College Mathematics Journal, 34:4 (Septiembre, 2006) páginas 260, 285, y 289.