Angel "Java" Lopez en Blog

Publicado el 16 de Agosto, 2009, 13:14

En un post anterior:

Un problema de colaboración

había planteado un problema de búsqueda de estrategia, para que los participantes pudieran pasarse información para determinar una carta que no conocen. De la misma fuente, describo hoy otro problema:

Resulta que hay 1 ayudante y 100 participantes, en este problema. Hay 100 monedas, cada una numerada: está la moneda 1, la moneda 2, ... la moneda 100. En una sala, hay cien cajas en fila, con tapa. En cada una de ellas hay una de las monedas (una y solo una), que se colocaron al azar.

El ayudante entra en la sala, destapa las 100 cajas, mira y decide hace UNA SOLA de estas operaciones:

- Deja todo tal cual
- Intercambia dos monedas

Es decir, o no hace nada, o saca una moneda de una caja y la intercambia por otra moneda de otra caja (qué operación realiza, y cuáles monedas intercambia, son parte de su estrategia).

El ayudante se retira, y ahora, les toca el turno a los participantes, que son cien, cada uno numerado: participante 1, participante 2... participante 100. Entra uno, destapa una caja (cuál, es parte de su estrategia). Mira la moneda. Si el número de la moneda coincide con su propio número de participante, termina. Sino, abre otra caja. Y sigue así hasta que encuentra la moneda que corresponde a su número. Siempre, para elegir la próxima caja, se basa en la información de las cajas y monedas que ya visitó. Al final, cierra todas las cajas, con las monedas adentro, y se retira.

El problema es: ¿cuál es la estrategia del ayudante y la estrategia a seguir por los participantes, para que éstos no tengan que destapar más de 50 cajas para encontrar su moneda?

Ayuda: prueben primero con 1 ayudante, 2 participantes, 2 monedas. Luego 1 ayudante, 4 participantes, 4 monedas...etc...

Como el anterior, encontré este interesante problema en la columna de "Juegos matemáticos" de Agustín Rayo, en la revista "Investigación y Ciencia", número de Febrero de 2009

Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez