Un amigo mío se enteró por un amigo suyo del siguiente problema que, según el amigo de mi amigo, sigue abierto? El juego es el siguiente: Hay 100 personas con nombres diferentes, sus nombres están escritos en trozos de papel y se colocan dentro de 100 cajas (cada caja con un nombre y todas las cajas con un nombre diferente).
Las personas entran una por una en la habitacion con las cajas y seleccionan cincuenta de ellas, miran dentro de ellas y si encuentran su nombre sacan el trozo de papel y se lo muestran al "Game Master" que a su vez les perdona la vida, si su papel no esta dentro son asesinados.Note que las otras personas no pueden saber que habia dentro de las cajas que abrio o si murio o no.Despues de que la persona pasa todas las cajas se cierran de nuevo, y entonces la siguiente persona entra y hace lo mismo. Así sucesivamente hasta que todas las personas hayan muerto. ¿Podemos encontrar una estrategia en la que haya al menos un $20\%$ ¿es posible que sobrevivan todos?
Como no obtenemos más información a medida que avanza el juego, tenemos que planificarlo desde el principio, lo que equivale a decir a cada persona qué cajas tiene que abrir.
En la teoría de grafos cada estrategia será un grafo bipartito diferente $G$ donde las dos partes $X$ y $Y$ ambos tienen $100$ y los vértices de $X$ todos tienen título $50$ . Observe que si todas las personas sobreviven, las aristas entre las casillas con los nombres de las personas y las personas proporcionarán una correspondencia perfecta, por lo que el número de permutaciones de las casillas en las que sobreviven todas las personas es igual al número de correspondencias perfectas del grafo $G$ tiene.
Obsérvese que para que una estrategia tenga al menos un $20\%$ probabilidad de que todos sobrevivan necesitamos que su gráfico correspondiente tenga al menos $99!\cdot20$ emparejamientos perfectos, ¿es esto posible?
¿Dónde puedo encontrar información sobre problemas similares a éste, o sobre la teoría que se está utilizando para abordarlo en la actualidad?
