OMCC 2018 - P6

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 686
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

OMCC 2018 - P6

Mensaje sin leer por Gianni De Rico » Mié 18 Jul, 2018 1:41 am

En La Habana se realiza un baile con $2018$ parejas. Para el baile, se dispone de una circunferencia donde inicialmente se marcan $2018$ puntos distintos, etiquetados con los números $0,1,\ldots ,2017$. Las parejas son ubicadas sobre los puntos marcados, una en cada punto. Para $i\geqslant 1$, se define $s_i$ como el resto de dividir $i$ entre $2018$ y $r_i$ como el resto de dividir $2i$ entre $2018$. El baile comienza en el minuto $0$. En el $i-$ésimo minuto después de iniciado el baile $(i\geqslant 1)$, la pareja ubicada en el punto $s_i$ (si la hay) se mueve al punto $r_i$, la pareja ubicada en el punto $r_i$ (si la hay) se retira, y el baile continúa con las parejas restantes. El baile termina después de $2018^2$ minutos. Determine cuántas parejas quedarán al terminar el baile.

Nota: Si en el minuto $i$, $s_i=r_i$, la pareja que está en $s_i$ (si la hay) se mantiene en su lugar y no sale del baile.
[math]

Avatar de Usuario
jhn

OFO - Medalla de Plata
Mensajes: 504
Registrado: Mié 10 Oct, 2012 3:25 pm
Medallas: 1
Nivel: Otro
Ubicación: Venezuela
Contactar:

Re: OMCC 2018 - P6

Mensaje sin leer por jhn » Jue 19 Jul, 2018 9:24 am

Spoiler: mostrar
Al finalizar el minuto $j$, para $j=1,2,\ldots, 1008$, la pareja en la posición $j$ pasa a la posición $2j$. Como $2j>j$, las posiciones 1, 2,\ldots, 1008 van quedando sucesivamente desocupadas y no se vuelven a ocupar. En el minuto 1009 se desocupa la posición 1009 (y se ocupa la 0, que ya estaba ocupada), y las posiciones 1010, 1011,\ldots, 2017 están todas ocupadas. Durante los minutos $1009+j$ con $j=1,2,\ldots, 1008$, la posición $1009+j$ se desocupa y se ocupa la posición $2j$. Como $j<1009$ se tiene $2j<1009+j$ y la posición $2j$ no se vuelve a desocupar. Entonces al finalizar el minuto 2017 las posiciones ocupadas serán 0, 2, 4, 6,\ldots, 2016. En el minuto 2018 la posición 0 queda ocupada (como estaba). Durante los minutos $2018+1$ al $2018+1009=3027$ se van desocupando las posiciones 2, 4, 6,\ldots, 1008 y no se vuelven a ocupar. Durante el minuto $3027+j$ con $j=1,2,\ldots, 1008$, si $j$ es par no ocurre nada pero si $j$ es impar se desocupa la posición $1009+j$ y se ocupa la $2j$. Por lo tanto en el minuto 4036 las posiciones ocupadas serán 0, 2, 6,\ldots, 2014.

Durante el minuto $4036+j$ con $1\le j\le 1009$, si $j$ es par se desocupa la posición $j$ y se ocupa la $2j$. Así al finalizar el minuto $4036+1009=5045$ las posiciones ocupadas serán 0, 1010, 1012,\ldots, 2016. A continuación durante los minutos $5045+j$ con $j=1,2,\ldots, 1008$, si $j$ es par no ocurre nada pero si $j$ es impar se desocupa la posición $1009+j$ y se ocupa la $2j$. Por lo tanto en el minuto 6054 las posiciones ocupadas serán 0, 2, 6,\ldots, 2014.
Es claro que este proceso se vuelve a repetir una y otra vez, por lo tanto al cabo de $2018k$ minutos con $k\ge 2$ quedarán 505 parejas.
Todo problema profana un misterio; a su vez, al problema lo profana su solución.
https://jhnieto.000webhostapp.com/

Responder