Selectivo Cono Sur 1998 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: 1131
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Selectivo Cono Sur 1998 P5

Mensaje sin leer por Matías V5 »

En el pizarrón están escritos [math] números: el primero igual a [math] y los restantes [math] iguales a [math].
La operación permitida es borrar dos números del pizarrón, a elección, y en cada uno de los dos lugares que quedaron vacíos escribir el promedio de los dos números recién borrados. Al finalizar cada operación permitida se tienen nuevamente [math] números escritos en el pizarrón.
Hallar todos los valores de [math] para los cuales es posible, mediante una sucesión de operaciones permitidas, tener finalmente escritos en el pizarrón [math] números iguales.
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
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: 1131
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Re: Semana de Entrenamiento para la Cono Sur - Día 6

Mensaje sin leer por Matías V5 »

Spoiler: mostrar
Afirmamos que en todo momento los números escritos en el pizarrón son números racionales que se pueden escribir como una fracción cuyo denominador es una potencia de [math]. Esto es claramente cierto al principio del proceso, pues todos los números son enteros así que se pueden escribir como una fracción con denominador [math]. Para ver que esta propiedad se mantiene a lo largo del proceso, basta ver que al promediar dos números de esa forma se vuelve a obtener un número de esa forma: [math], es decir una fracción con denominador igual a una potencia de [math], como queríamos ver.
Observemos además que la suma de todos los números del pizarrón también se mantiene invariante. Inicialmente esta suma es [math], por lo tanto, si se pudiera lograr que queden [math] números iguales en el pizarrón, estos números deberían ser todos [math]. Pero esta fracción es irreducible, pues [math] y [math] son coprimos, entonces por lo que dijimos antes necesariamente [math] debe ser una potencia de [math].
Hasta acá vimos que para que se pueda lograr el objetivo [math] tiene que ser potencia de [math], ahora veamos que si [math] es potencia de [math] efectivamente se puede cumplir el objetivo. Sea [math]. En el primer paso elegimos un [math] y un [math], hacemos la operación y nos quedan en el pizarrón dos números iguales a [math] y [math] unos. En el segundo paso hacemos dos operaciones, cada una de las cuales involucra a un [math] y a un [math]. Nos quedan en el pizarrón cuatro números iguales a [math] y [math] unos. En el tercer paso hacemos cuatro operaciones con un [math] y un [math] y nos quedan ocho [math] y [math] unos. Continuamos este proceso, al cabo de [math] pasos nos quedan [math] números iguales a [math] y la misma cantidad de unos, luego haciendo [math] operaciones permitidas más conseguimos que todos los números sean iguales a [math].
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
Avatar de Usuario
biank
Mensajes: 81
Registrado: Vie 02 Dic, 2022 9:57 pm
Nivel: 3

Re: Selectivo Cono Sur 1998 P5

Mensaje sin leer por biank »

Spoiler: mostrar
Afirmo que es posible para $N$ potencia de $2$. Primero veamos que es posible en estos casos. Vamos a demostrarlo por inducción.
El caso base es $N = 2^1 = 2$, que claramente se puede porque $[0, 1] \rightarrow \left[\frac{1}{2}, \frac{1}{2}\right]$.
Entonces ahora supongamos por hipótesis inductiva que que para algún $N = 2^k$, se puede transformar la lista $[0, \overbrace{1, \dots, 1}^{2^k - 1\text{ veces}}]$ en $\bigg[\overbrace{\frac{2^k - 1}{2^k}, \dots, \frac{2^k - 1}{2^k}}^{2^k \text{ veces}}\bigg]$ en $2^k - 1$ pasos.
Entonces consideremos el caso $N = 2^{k + 1}$. Por hipótesis inductiva, podemos transformar los primeros $2^k$ en todos iguales en $2^k - 1$ pasos, luego podemos aplicar $2^k$ operaciones entre un $\frac{2^k - 1}{2^k}$ y un $1$ para obtener dos $\frac{2^{k + 1} - 1}{2^{k + 1}}$ en un total de $2^k - 1 + 2^k = 2^{k + 1} - 1$ operaciones, como queríamos. $$
\big[ 0, \overbrace{1, \dots, 1}^{2^{k + 1} - 1 \text{ veces}} \big]
\overset{2^k - 1 \text{ pasos}}{\longrightarrow}
\bigg[
\overbrace{\frac{2^k - 1}{2^k}, \dots, \frac{2^k - 1}{2^k}}^{2^k \text{ veces}},
\overbrace{1, \dots, 1}^{2^k \text{ veces}}
\bigg]
\overset{2^k \text{ pasos}}{\longrightarrow}
\bigg[
\overbrace{\frac{2^{k + 1} - 1}{2^{k + 1}}, \dots, \frac{2^{k + 1} - 1}{2^{k + 1}} }^{2^{k + 1} \text{ veces}}
\bigg]
$$
Por lo tanto por inducción es posible para cualquier $N=2^k$ con $k\geq 1$.

Falta entonces probar que es imposible en el resto de casos. Para ello veremos que siempre los números del pizarrón se pueden expresar como una fracción irreducible $\frac{p}{q}$ donde $q=2^c$.

Al principio esto ocurre ya que son todos enteros, por lo que $q=1=2^0$. Entonces veamos que esto se mantiene esta propiedad al aplicar la operación en dos números cualquiera $\frac{p_1}{q_1}$ y $\frac{p_2}{q_2}$ que por hipótesis $q_1=2^{c_1}$ y $q_2=2^{c_2}$. $$\frac{\frac{p_1}{q_1} + \frac{p_2}{q_2}}{2} = \frac{\frac{p_1q_2 + p_2q_1}{q_1q_2}}{2} = \frac{p_1q_2 + p_2q_1}{2q_1q_2} = \frac{p_1 \cdot 2^{c_2} + p_2 \cdot 2^{c_1}}{2^{c_1 + c_2 + 1}}
$$ Cuando lo escribamos como fracción irreducible, el denominador va a ser necesariamente un divisor de $2^{c_1 + c_2 + 1}$, es decir una potencia de $2$.

Además, al aplicar la operación es claro que se mantiene la suma, porque $x + y = \frac{x + y}{2} + \frac{x + y}{2}$, por lo que para un pizarrón con $N$ números siempre va a haber suma $N - 1$ y para que los $N$ números sean iguales necesitamos entonces que sean $\frac{N - 1}{N}$. Como esta fracción es irreducible por lo que vimos antes $N$ debe ser potencia de $2$, que es el caso que ya habíamos visto que siempre se podía.

Por lo tanto, es posible para cualquier $N = 2^k$ con $k \in \mathbb{N}$. $\blacksquare$
Responder