Processing math: 100%

1 votos

8 monedas en la mesa; puedes voltear una a la vez; ¿cuál es el número mínimo de volteos para obtener todas caras o todas cruz?

Las reglas del juego son las siguientes:

(1) Puedes voltear (dar la vuelta) una moneda a la vez.

(2) No puedes ver las monedas, pero puedes preguntar después de cada volteo si has alcanzado el estado de todas las caras o todas las cruces.

(3)

Aparentemente la respuesta es 2n11=271=127 (esta fórmula se generaliza a cualquier n, número de lanzamientos).

No tengo idea de dónde proviene esta fórmula. ¿Podría alguien explicar?

http://people.csail.mit.edu/nbenbern/CoinFlipping.pdf, pero aún no logro entender cómo funciona.

1voto

PiGuy314 Puntos 111

Dado n número de monedas en la mesa, hay 2n posibles secuencias de caras o sellos. Puedes ignorar la primera moneda, y luego pasar por cada permutación posible de las otras n1. Mientras estás revisando cada permutación, una de ellas está garantizada a ser todas caras o todos sellos. Esto te da un mínimo de 2n1 volteos. Sin embargo, debido a que hay una permutación original de monedas que no es todas caras o todas sellos, hay una posición que no tendrás que revisar, resultando en la expresión final de 2n11.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X