De nuevo tenemos problema de la Olimpiada Matemática Internacional (IMO, según sus siglas en inglés). Hoy le toca al quinto de los seis problemas que se han propuesto en la de este año 2019, celebrada en Bath (Reino Unido).
Ahí va:
El Banco de Bath emite monedas con una
en una cara y una
en la otra. Harry tiene
monedas de este tipo alineadas de izquierda a derecha. Él realiza repetidamente la siguiente operación: si hay exactamente
monedas con la
hacia arriba, Harry voltea la moneda
-ésima contando desde la izquierda; en caso contrario, todas las monedas tienen la
hacia arriba y él se detiene. Por ejemplo, si
y la configuración inicial es
, el proceso sería
que se detiene después de tres operaciones.
a) Demostrar que, para cualquier configuración inicial que tenga Harry, el procso se detiene después de un número finito de operaciones.
b) Para cada configuración inicial
, sea
el número de operaciones que se realizan hasta que Harry se detiene. Por ejemplo,
y
. Determinar el valor promedio de
sobre todas las
posibles configuraciones iniciales de
.
A por él.
Recuerdo que la idea de publicar estos problemas es que los intentemos resolver nosotros, no que alguien busque la solución en internet y la copie aquí. Confío en vuestro buen criterio en este sentido.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
haciendo pruebas se intuye que el número promedio es (n+1)n/4, pero la demostración…
La demostración de que el proceso termina es sencilla conceptualmente pero me resulta engorrosa de escribir:
Casos si H consecutivas o no. Si son consecutivas las monedas con H desde la izquierda, k disminuye a cada paso, y si no lo son, k aumenta haciendo que sean consecutivas desde la izquierda. Utilizando índices y contemplando los casos me sale una buena parrafada poco inteligible.
Obs1. Sea k>0 el número de monedas con la H hacia arriba y sea la posición de la moneda con la H arriba más a la derecha de la fila, entonces, mientras juguemos, el número de monedas con la H arriba nunca superará . (Porqué como mucho solo habrá las primeras monedas con la H hacia arriba) Obs2. sea k>0 el num de monedas con la H hacia arriba, por la Obs1, la moneda número k de la fila es: 1) o bien una H. 2) o bien una T (posiblemente seguida de varias T) hasta una H. Por ejemplo:… Lee más »
El promedio es . Esto es lo mismo que decir que la suma de todas las operaciones para todas las configuraciones iniciales es: Vamos a demostrar esta expresión por inducción. Es fácil comprobar que para n=2 se cumple. Suponemos que la expresión se cumple para n. Para n+1, las configuraciones iniciales se pueden obtener a partir de las configuraciones iniciales para n, añadiendo al final una T o una H. Si se añade una T al final, las operaciones no cambian. Por lo tanto, la suma de las operaciones para las configuraciones iniciales acabadas en T será . Si se… Lee más »