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
-ésima contando desde la izquierda; en caso contrario, todas las monedas tienen la
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
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: …TH…, …TTH…, …TTTH…, etc.
Con estas observaciones podemos demostrar que el algoritmo acaba siempre en TT…TT , aplicando inducción sobre el número de monedas con la H hacia arriba (k).
1) Para k=0 es cierto (ya hemos acabado).
2) Sea k>0 el número de monedas con la H hacia arriba, por la Obs2, o bien la moneda número k de la fila es una H (le damos la vuelta y ahora tenemos k-1 monedas con la H hacia arriba => hipótesis de inducción)
T’s hasta la primera H. Para poder aplicar la hipótesis de inducción, la idea es ver que, eventualmente, el algoritmo matará esta H y dejará las T’s como estaban:
o bien la moneda número k de la fila es una T seguida de
Giramos la primera T (la de la posición k), y ahora habrá k+1 H’s así que giramos la segunda T (la de la posición k+1), y ahora habrá k+2 H’s, así que giramos la tercera T (la de la posición k+2), etc etc etc. Después de estos m+1 pasos, alcanzaremos la moneda H.
Cuando le demos la vuelta a la moneda H, por primera vez, el número total de H’s habrá disminuido! Además, las monedas k, k+1, …, k+m tienen la H hacia arriba. Por lo tanto tocará dar marcha atrás y girar la moneda k+m, k+m-1, k+m-2, etc hasta llegar a la moneda k. Cuando le volvamos a dar la vuelta a la moneda k, estaremos exactamente donde empezamos, por la H habrá desaparecido, así que solo habrá k-1 H’s. (hipótesis de inducción).
QED.
Añado un ejemplo de la parte final con m=2
…TTTH…
le damos la vuelta a la primera T, y ahora habrá k+1 H, así que volteamos la siguiente T, etc etc, hasta llegar a girar la moneda H.
…TTTH… -> …HTTH… -> …HHTH… -> …HHHH… -> …HHHT…
Ahora, el número de H’s acaba de disminuir! Así que tocará volver a deshacer los giros de las T’s:
…HHHT… -> …HHTT… -> …HTTT… -> …TTTT…
y ahora hay k-1 H’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 añade una H al final, el número de operaciones se incrementa en 2d+1, donde d es la distancia entre la posición inicial k y el extremo derecho. Es decir,
.
Entonces, se tiene:
La distribución de las posiciones iniciales viene dada por los números combinatorios. Por tanto:
Llevándolo a la expresión general:
Y queda demostrado.