PAGMO 2021 - P5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Nando

OFO - Mención-OFO 2019
Mensajes: 191
Registrado: Mar 31 Jul, 2018 7:39 pm
Medallas: 1

PAGMO 2021 - P5

Mensaje sin leer por Nando »

Celeste tiene un número ilimitado de dulces de cada uno de $n$ tipos distintos, etiquetados tipo $1$, tipo $2$, ..., tipo $n$. Inicialmente ella toma $m>0$ dulces y los pone en fila sobre una mesa. Después escoge repetidamente una de las siguientes operaciones y la ejecuta (puede que no tenga siempre ambas opciones).
  1. Ella se come un dulce de tipo $k$ y pone en su lugar dos dulces: uno de tipo $k-1$ seguido por uno de tipo $k+1$. Consideramos el tipo $n+1$ como tipo $1$, y el tipo $0$ como tipo $n$.
  2. Ella escoge dos dulces del mismo tipo que sean adyacentes y se los come.
Determinar todos los enteros positivos $n$ para los que Celeste puede dejar la mesa vacía después de realizar un número finito de las operaciones anteriores, para todo valor de $m$ y toda configuración de dulces en la mesa.
Avatar de Usuario
Kechi

OFO - Medalla de Bronce-OFO 2023 OFO - Medalla de Plata-OFO 2024
Mensajes: 76
Registrado: Mié 21 Sep, 2022 1:41 pm
Medallas: 2
Nivel: 2

Re: PAGMO 2021 - P5

Mensaje sin leer por Kechi »

Spoiler: mostrar
Celeste puede dejar la mesa vacía para todo $n$ no múltiplo de $3$.

Definamos una súper operación sobre un dulce de tipo $k$ que resume las siguientes operaciones:
$$k\longrightarrow k-1,~k+1\longrightarrow k-1,~k,~k+2\longrightarrow k-1,~k-1,~k+1,~k+2\longrightarrow k-1,~k-1,~k+1,~k+1,~k+3\longrightarrow k+1,~k+1,~k+3\longrightarrow k+3$$
donde las primeras $4$ son de tipo $1$ y las últimas $2$ de tipo $2$. Es decir, la súper operación convierte un dulce de tipo $k$ en uno de tipo $k+3$.

Veamos ahora que para todo $n$ tal que $3\nmid n$ los números $1\cdot3,2\cdot3,\ldots,n\cdot3$ recorren todas las congruencias módulo $n$. Efectivamente en caso contrario deberían existir dos enteros positivos distintos $a$ y $b$ menores o iguales a $n$ tales que $3a\equiv 3b \pmod{n}$, y como $3$ es coprimo con $n$ esto es equivalente a que $a\equiv b \pmod{n}$ lo que es absurdo por como definimos $a$ y $b$.

De lo ya visto podemos deducir que dado un dulce de tipo $k$ le podemos aplicar $r$ súper operaciones tales que el dulce resultante sea del tipo que queramos (será del tipo $k+3r$, pudiendo elegir $r$ adecuadamente).

Ahora vamos a desarrollar una estrategia para Celeste: primero, de ser necesario, debe aplicar la operación $1$ en un dulce al azar para que la cantidad total de dulces sea par. Luego debe emparejar los dulces y a través de súper operaciones hacer que los de cada pareja sean del mismo tipo para luego aplicarles la operación $2$. Con esto logra dejar la mesa vacía.

Consideremos ahora un $n$ múltiplo de $3$. Vamos a demostrar que si en la mesa hay un sólo dulce de tipo $1$ Celeste no puede dejarla vacía.

Sean $A$ y $B$ las cantidades de dulces de un tipo congruente a $1$ y $2$ módulo $3$, respectivamente y consideremos el número $A-B$.
  • Si Celeste aplica una operación $1$ en un dulce de un tipo congruente a $0$ módulo $3$, $A$ y $B$ aumentan en $1$, y $A-B$ permanece igual.
  • Si Celeste aplica una operación $2$ en un dulce de un tipo congruente a $0$ módulo $3$, $A$, $B$ y por lo tanto $A-B$ no varían.
  • Si Celeste aplica una operación $1$ en un dulce de un tipo congruente a $1$ módulo $3$, $A$ disminuye en $1$ mientras que $B$ aumenta en $1$, por lo que $A-B$ disminuye en $2$.
  • Si Celeste aplica una operación $2$ en un dulce de un tipo congruente a $1$ módulo $3$, $A$ disminuye en $2$ y $B$ permanece igual, por lo que $A-B$ también disminuye en $2$.
  • Si Celeste aplica una operación $1$ en un dulce de un tipo congruente a $2$ módulo $3$, $A$ aumenta en $1$ mientras que $B$ disminuye en $1$, por lo que $A-B$ aumenta en $2$.
  • Si Celeste aplica una operación $2$ en un dulce de un tipo congruente a $2$ módulo $3$, $A$ permanece igual y $B$ disminuye en $2$, por lo que $A-B$ aumenta en $2$.
Notemos que sin importar la operación que se haga, la diferencia $A-B$ mantiene su paridad. Si la mesa quedara vacía $A-B=0$ sería par, pero con un dulce de tipo $1$ en la mesa $A-B=1-0=1$ es impar, entonces con esta configuración Celeste no puede cumplir su objetivo. $\bigstar$
"La suma de las raíces cuadradas de dos lados de un triángulo isósceles es igual a la raíz cuadrada del lado restante."
Responder