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?

Question

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 $2^{n-1} - 1 = 2^{7} - 1 = 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.

Answer 1

Dado $n$ número de monedas en la mesa, hay $2^n$ posibles secuencias de caras o sellos. Puedes ignorar la primera moneda, y luego pasar por cada permutación posible de las otras $n-1$. 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 $2^{n-1}$ 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 $2^{n-1}-1$.