IMO 2019 - P5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

IMO 2019 - P5

Mensaje sin leer por Matías V5 »

El Banco de Bath emite monedas con una $H$ en una cara y una $T$ en la otra. Harry tiene $n$ monedas de este tipo alineadas de izquierda a derecha. Él realiza repetidamente la siguiente operación: si hay exactamente $k>0$ monedas con la $H$ hacia arriba, Harry voltea la $k$-ésima moneda contando desde la izquierda; en caso contrario, todas las monedas tienen la $T$ hacia arriba y él se detiene. Por ejemplo, si $n=3$ y la configuración inicial es $THT$, el proceso sería $THT \rightarrow HHT \rightarrow HTT \rightarrow TTT$, que se detiene después de tres operaciones.

(a) Demostrar que para cualquier configuración inicial que tenga Harry, el proceso se detiene después de un número finito de operaciones.

(b) Para cada configuración inicial $C$, sea $L(C)$ el número de operaciones que se realizan hasta que Harry se detiene. Por ejemplo, $L(THT)=3$ y $L(TTT)=0$. Determinar el valor promedio de $L(C)$ sobre todas las $2^n$ posibles configuraciones iniciales de $C$.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
FOFO 9 años - Jurado-FOFO 9 años OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 402
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 13
Nivel: Exolímpico

Re: IMO 2019 - P5

Mensaje sin leer por jujumas »

Solución:
Spoiler: mostrar
Sea $f(n)$ el promedio de $L(C)$ sobre las $2^n$ posibles configuraciones iniciales de $C$, notemos que $f(1)=\frac{1}{2}$. Notar que si $f(k)$ está definido, entonces la parte (a) del problema se cumple para $n=k$, ya que tenemos acotado $L(C)$ para todo $C$ con $k$ monedas.


Lema Si $f(n-1)$ está definido, entonces $f(n)$ está definido y $f(n)=f(n-1)+\frac{n}{2}$.

Demostración:
Spoiler: mostrar
Notemos que si nuestra configuración inicial de monedas $X$ termina con un símbolo $T$, entonces esta moneda puede ser ignorada, ya que para que esta pueda ser volteada se necesitaría que todas las monedas muestren una $H$ en el momento inmediatamente anterior, pero en ese momento esa moneda muestra una $T$ por hipótesis. Luego, la moneda nunca aporta a la cantidad de símbolos $H$ presentes, y podemos tratar a $X$ como a la configuración compuesta por sus primeras $n-1$ monedas. Luego, el promedio de $L(C)$ sobre las configuraciones iniciales que terminan en $T$ es exactamente $f(n-1)$, que está definido.

Ahora, si nuestra configuración inicial de $n$ monedas $Y=y_1y_2\dots y_n$ termina con un símbolo $H$ ($y_n=H$), hacemos los siguiente:

Vamos a decir que dos sucesiones de $n-1$ monedas $A$ y $B$ son "opuesto-inversas", si al cambiar todo $T$ por $H$ y todo $H$ por $T$ a la sucesión que es el reflejo de $A$ se obtiene $B$. (Por ejemplo, $TTHHT$ y $HTTHH$ son "opuesto-inversas")

Miremos entonces las primeras $n-1$ monedas de $Y$ $y_1y_2\dots y_{n-1}$ y consideremos la configuración de $n-1$ monedas opuesto-inversa a $y_1y_2\dots y_{n-1}$, a la que llamaremos $D=d_1d_2\dots d_{n-1}$. Voy a demostrar entonces que si le aplico una operación a $Y$ (la configuración de $n$ monedas original), y miro como quedaron sus primeras $n-1$ monedas, voy a obtener la opuesto-inversa de el resultado de aplicarle la operación a $D$.

Para demostrar esto basta ver que si volteo $y_i$ y $d_j$, entonces $i+j=n$. Supongamos entonces que en $y_1y_2\dots y_{n-1}$ aparece $m$ veces la letra $H$. Luego, en $D$, $H$ aparece $n-1-m$ veces. Al hacer la operación en $Y$, como $Y$ tiene $m+1$ letras $H$ (ya que termina en $H$) voy a voltear las monedas $y_{m+1}$ y $d_{n-1+m}$, y se cumple lo que quiero demostrar.

Entonces, mientras nuestra configuración siga terminando en $H$, $Y$ y $D$ se van a seguir comportando de la misma manera. Notemos entonces que la única forma de que $Y$ deje de terminar en $H$ es que en el movimiento anterior halla $n$ monedas que muestren la $H$, por lo que todas las monedas lo hacen. Veamos entonces que esto es análogo a que $D$ llegue a mostrar solamente la cara $T$, que sabemos que pasa porque estamos asumiendo que $f(n-1)$ está definido. Luego, entre todas las configuraciones de $n$ monedas que terminan en $H$, tardamos en promedio $f(n-1)$ en llegar a que todas las monedas muestren la letra $H$. Para terminar, entonces, notemos que tardamos $n$ movidas en llegar de una configuración con todo $H$ a una con todo $T$ (en cada movida giramos la $H$ más a la izquierda), y hay tantas configuraciones de monedaas que terminan en $T$ como configuraciones que terminan en $H$. Luego, $f(n)=\frac{f(n-1) + (f(n-1) + n)}{2} = f(n-1) +\frac{n}{2}$, y la demostración del lema está completa.
Notemos que por inducción, el lema implica trivialmente la parte (a) para toda cantidad de monedas, y que ahora podemos demostrar que $f(n)=\frac{1}{2}+\frac{2}{2}+\frac{3}{2}+\dots+\frac{n}{2}=\frac{n(n+1)}{4}$ y la solución de ambas partes está completa.
1  
Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Re: IMO 2019 - P5

Mensaje sin leer por Fran5 »

Comentario con spoiler
Spoiler: mostrar
Lo loco de este problema es demostrar que toda configuración se va a todas $T$, usando en el medio que una configuración se va a todas $T$ si y sólo si otra configuración se va a todas $H$
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: IMO 2019 - P5

Mensaje sin leer por Gianni De Rico »

Otra distinta
Solución:
(a)
Spoiler: mostrar
Veamos por inducción en $n$ que para toda configuración el proceso se detiene tras un número finito de operaciones, y que una configuración llega a tener todas las monedas en posición $H$ si y sólo si su última moneda está en posición $H$.
El caso base $n=1$ es cierto, pues las únicas dos configuraciones posibles son $H$ y $T$. La primera resulta $H\to T$, y termina. La segunda resulta $T$, y termina. Además, la única configuración que tiene todas las monedas en posición $H$ es la que tiene su última moneda en posición $H$.
Supongamos como hipótesis inductiva que el resultado vale para $n=m$. Veamos que vale para $m+1$.
En efecto, tenemos dos casos
Caso 1: La última moneda está en posición $T$
Spoiler: mostrar
Vemos que hay a lo sumo $m$ monedas en posición $H$, por lo tanto, luego de aplicar la operación la última moneda está en posición $T$, y por lo tanto hay a lo sumo $m$ monedas en posición $H$. Entonces la posición de la última moneda es invariante bajo la operación, por lo que siempre será $T$.
Luego, siempre tenemos a lo sumo $m$ monedas en posición $H$ en la fila, y están entre las primeras $m$ posiciones. Por hipótesis inductiva, el proceso en la fila de $m$ monedas termina en un número finito de pasos, esto es, las primeras $m$ monedas están todas en posición $T$ en un número finito de pasos, luego, todas las monedas están en posición $T$ en un número finito de pasos.
Caso 2: La última moneda está en posición $H$
Spoiler: mostrar
Si en algún momento todas las monedas están en posición $H$, entonces la última moneda pasa a estar en posición $T$, y estamos en el caso anterior.
Supongamos que nunca ocurre que todas las monedas estén en posición $H$. Como la única forma de cambiar la posición de la última moneda es que todas las monedas estén en posición $H$, entonces la última moneda está siempre en posición $H$. Por lo tanto, si entre las primeras $m$ monedas hay $k$ en posición $H$, entonces en total hay $k+1$ monedas en posición $H$, por lo que el resultado es equivalente al de aplicar la operación a la permutación de las primeras $m$ monedas que se obtiene de llevar la moneda en la posición $x$ a la posición $x-1$, con los índices módulo $m$.

IMO 2019 P5.png

Pero una permutación de una configuración es una configuración, por lo que llegará a ser $\underbrace{TTT\ldots T}_{m}H$ en un número finito de pasos.
Veamos ahora que si tenemos una configuración de la forma $\underbrace{HHH\ldots H}_{m-r}\underbrace{TTT\ldots T}_{r}H$, entonces llegará a $\underbrace{HHH\ldots H}_{m+1}$ en $r$ pasos. Lo haremos por inducción en $r$.
El caso base $r=0$ es válido, pues $\underbrace{HHH\ldots H}_{m-0}H=\underbrace{HHH\ldots H}_{m+1}$, y llega a esa configuración en $0$ pasos.
Supongamos como hipótesis inductiva que vale para $r=t$. Veamos que vale para $t+1$.
En efecto, si tenemos una configuración de la forma $\underbrace{HHH\ldots H}_{m-(t+1)}\underbrace{TTT\ldots T}_{t+1}H$, entonces hay $m-(t+1)+1=m-t$ monedas en posición $H$, luego, la operación es $\underbrace{HHH\ldots H}_{m-(t+1)}\underbrace{TTT\ldots T}_{t+1}H\to \underbrace{HHH\ldots H}_{m-t}\underbrace{TTT\ldots T}_{t}H$. Por hipótesis inductiva, $\underbrace{HHH\ldots H}_{m-t}\underbrace{TTT\ldots T}_{t}H$ llega a $\underbrace{HHH\ldots H}_{m+1}$ en $t$ pasos, en total realizamos $t+1$ pasos. La inducción está completa.
Veamos ahora que si tenemos una configuración de la forma $\underbrace{HHH\ldots H}_{r}\underbrace{TTT\ldots T}_{m+1-r}$, entonces llegará a $\underbrace{TTT\ldots T}_{m+1}$ en $r$ pasos. Lo haremos por inducción en $r$.
El caso base $r=0$ es válido, pues $\underbrace{TTT\ldots T}_{m+1-0}=\underbrace{TTT\ldots T}_{m+1}$, y llega a esa configuración en $0$ pasos.
Supongamos como hipótesis inductiva que vale para $r=t$. Veamos que vale para $t+1$.
En efecto, si tenemos una configuración de la forma $\underbrace{HHH\ldots H}_{t+1}\underbrace{TTT\ldots T}_{m+1-(t+1)}=\underbrace{HHH\ldots H}_{t+1}\underbrace{TTT\ldots T}_{m-t}$, entonces hay $t+1$ monedas en posición $H$, luego, la operación es $\underbrace{HHH\ldots H}_{t+1}\underbrace{TTT\ldots T}_{m-t}\to \underbrace{HHH\ldots H}_{t}\underbrace{TTT\ldots T}_{m-t+1}$. Por hipótesis inductiva, $\underbrace{HHH\ldots H}_{t}\underbrace{TTT\ldots T}_{m-t+1}$ llega a $\underbrace{TTT\ldots T}_{m+1}$ en $t$ pasos, en total realizamos $t+1$ pasos. La inducción está completa.

Por lo tanto, la configuración $\underbrace{TTT\ldots T}_{m}H$ llega a $\underbrace{HHH\ldots H}_{m+1}$ en $m$ pasos, y llega a $\underbrace{TTT\ldots T}_{m+1}$ en otros $m+1$ pasos. Entonces llega a $\underbrace{TTT\ldots T}_{m+1}$ en un número finito de pasos, además de llegar a tener todas las monedas en posición $H$.
Entonces vimos que si la última moneda está en posición $T$, nunca llega a tener todas las monedas en posición $H$, y si la última moneda está en posición $H$, entonces llega a tener todas las monedas en posición $H$. Por lo que una configuración llega a tener todas las monedas en posición $H$ si y sólo si su última moneda está en posición $H$.
Además, en ambos casos la configuración llega a $\underbrace{TTT\ldots T}_{m+1}$ en un número finito de pasos, por lo que el proceso se detiene tras un número finito de operaciones. La inducción está completa.
Entonces para todo $n$, para cualquier configuración inicial de monedas, el proceso se detiene tras un número finito de operaciones.
(b)
Spoiler: mostrar
Sean $\mathcal{C}_n$ el conjunto de todas las configuraciones de $n$ monedas, $P(n)$ el promedio de los valores de $L(C)$ para $C\in \mathcal{C}_n$, y $T(n)=\sum\limits_{C\in \mathcal{C}_n}L(C)$. Luego, $P(n)=\frac{T(n)}{2^n}$.
Sean $T_T(n)$ y $T_H(n)$ la cantidad de operaciones que se realizan sobre las configuraciones de $n$ monedas que tienen a su última moneda en posición $T$ y las configuraciones de $n$ monedas que tienen a su última moneda en posición $H$, respectivamente. Luego, $T(n)=T_T(n)+T_H(n)$.
Ahora, en (a), vimos que las operaciones que se realizan para cada configuración de $n$ monedas que tiene a su última moneda en posición $T$ son exactamente las mismas que las que se realizan para la configuración de $n-1$ monedas que se obtiene de retirar la última moneda. Por lo tanto, $T_T(n)=T(n-1)$.
Además, en (a) vimos que cada configuración de $n$ monedas que tiene a su última moneda en posición $H$ tiene dos opciones
Caso 1: Llega a $\underbrace{TTT\ldots T}_{n-1}H$
Spoiler: mostrar
Entonces tras realizar $n-1$ operaciones llega a $\underbrace{HHH\ldots H}_{n}$, y tras realizar otras $n$ operaciones llega a $\underbrace{TTT\ldots T}_{n}$. En total se realizaron $2n-1$ operaciones.
Caso 2: Llega a $\underbrace{HHH\ldots H}_{n}$ sin pasar por $\underbrace{TTT\ldots T}_{n-1}H$
Spoiler: mostrar
Entonces tras realizar $n-1$ operaciones llega a $H\underbrace{TTT\ldots T}_{n-1}$, y con una operación más llega a $\underbrace{TTT\ldots T}_{n}$.
Notemos que hay $2^{n-1}$ configuraciones que tienen a su última moneda en posición $H$, que para llegar a todas las configuraciones de la forma $\underbrace{TTT\ldots T}_{n-1}H$ o $\underbrace{HHH\ldots H}_{n}$ se realizan $T(n-1)$ operaciones (pues ya vimos en (a) que nunca cambiamos la última moneda y que aplicamos las operaciones a una permutación de las primeras $n-1$ monedas), y que hay $2^{n-2}$ configuraciones que llegan a $\underbrace{TTT\ldots T}_{n-1}H$ y $2^{n-2}$ configuraciones que llegan a $\underbrace{HHH\ldots H}_{n}$ (pues ya vimos en (a) que una configuración de $n-1$ monedas llega a tener todas las monedas en posición $H$ si y sólo si la moneda $n-1$ está en posición $H$, y al estar trabajando con la permutación, esto ocurre si y sólo si la moneda $n-2$ está en posición $H$). Luego, en cada configuración del Caso 1 aplicamos $2n-1$ operaciones más, y en cada configuración del Caso 2 aplicamos $1$ operación más (pues ya vimos en (a) que la configuración $\underbrace{HHH\ldots H}_{n-1}$ llega a $\underbrace{TTT\ldots T}_{n-1}$ en $n-1$ pasos), por lo tanto, en total aplicamos $2^{n-2}(2n-1)+2^{n-2}=2^{n-1}n$ operaciones más. Entonces, $T_H(n)=T(n-1)+2^{n-1}n$.
Por lo tanto, $T(n)=T_T(n)+T_H(n)=T(n-1)+T(n-1)+2^{n-1}n=2T(n-1)+2^{n-1}n$.

Veamos por inducción en $n$ que $T(n)=2^{n-2}n(n+1)$.
El caso base $n=1$ es cierto, pues la única operación que se realiza es $H\to T$, y $2^{1-2}\cdot 1\cdot (1+1)=2^{-1}\cdot 2=2^0=1$.
Supongamos como hipótesis inductiva que vale para $n=m$. Veamos que vale para $m+1$.
En efecto $$T(m+1)=2T(m)+2^m(m+1)\underset{HI}{=}2\cdot 2^{m-2}m(m+1)+2^m(m+1)=2^{m-1}(m(m+1)+2(m+1))=2^{m-1}(m+1)(m+2)$$
La inducción está completa.
Por lo tanto $P(n)=\frac{T(n)}{2^n}=\frac{2^{n-2}n(n+1)}{2^n}=\frac{n(n+1)}{4}$.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
♪♫ do re mi función lineal ♪♫
Responder