Simulacro Nacional 2022 Politecnico - Nivel 3 Problema 6

Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Simulacro Nacional 2022 Politecnico - Nivel 3 Problema 6

Mensaje sin leer por Fedex »

Decimos que un conjunto de enteros positivos distintos es perfecto si la suma de cualquier elección de números distintos del conjunto es una potencia perfecta. Si ninguna de estas sumas es una potencia perfecta, decimos que es anti-perfecto.

a) Demostrar que existe un conjunto perfecto de $2022$ elementos.
b) Demostrar que existe un conjunto anti-perfecto de $2022$ elementos.

Aclaración: Una potencia perfecta es un número de la forma $n^k$ donde $n$ y $k$ son ambos números naturales mayores o iguales que $2$.
This homie really did 1 at P6 and dipped.
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Simulacro Nacional 2022 Politecnico - Nivel 3 Problema 6

Mensaje sin leer por Fedex »

Este problema es una delicia, viva el fubol.

a)
Spoiler: mostrar
Consideramos un conjunto cualquiera de $2022$ elementos $A = \lbrace a_1, a_2, \cdots, a_{2022} \rbrace$ donde todas las sumas son $s_1, s_2, \cdots, s_{2^{2022}-1}$. Sea ahora un $C$ súper grande de la forma $C = s_1^{e_1} \cdot s_2^{e_2} \cdot s_3^{e_3} \cdots$ (es decir, el producto de todas las sumas esas elevadas a alguna potencia).

Si construimos el conjunto $C \cdot A = \lbrace C \cdot a_1, C \cdot a_2, \cdots, C \cdot a_{2022} \rbrace$, entonces lo que antes era la suma $s_i$, ahora es $C \cdot s_i$. Elegimos los $e_1, e_2, e_3, \cdots$ de modo que:
$$e_1 \equiv e_2 \equiv \cdots \equiv e_{i-1} \equiv e_{i+1} \equiv \cdots \equiv e_{2^{2022}-1} \equiv 0 \; (p_i)$$
$$e_i \equiv -1 \; (p_i)$$
Para todo $1 \leq i \leq 2^{2022}-1$ en un conjunto de primos $p_1, p_2, \cdots, p_{2^{2022}-1}$ distintos. Entonces, todos los exponentes en $C \cdot s_i$ son divisibles por $p_i$, es decir, este numero es una potencia $p_i$-ésima.

Quedaría ver que efectivamente podemos elegir los exponentes para que pase eso. Notemos que entonces, un exponente $e_i$ solo debe verificar:
$$e_i \equiv 0 \; (p_1p_2 \cdots p_{i-1}p_{i+1} \cdots p_{2^{2022}-1})$$
$$e_i \equiv -1 \; (p_i)$$
Donde, como ambos módulos son coprimos, por el Teorema Chino del Resto existe este $e_i$ para todo $1 \leq i \leq 2^{2022}-1$.

Concluimos entonces que el conjunto $C \cdot A$ es un conjunto perfecto de $2022$ elementos.
b)
Spoiler: mostrar
Nos construiremos un conjunto anti-perfecto de $n$ elementos para cualquier $n$ de forma inductiva. Para $n = 1$ simplemente nos tomamos un numero que no sea una potencia.

Para el paso inductivo, sea $A = \lbrace a_1, a_2, \cdots, a_n \rbrace$ un conjunto anti-perfecto de $n$ elementos. Queremos agregar un elemento $b$ de forma que este conjunto siga conservando la propiedad. Notemos que las sumas que no involucran a $b$ siguen sin ser potencias por hipótesis. Para que aquellas que si lo involucran, digamos, hago una cierta suma $s_i$ (posiblemente vacía) de elementos de $A$ y añado a $b$ quiero que:
$$s_i + b \equiv p_i \; (p_i^2) \Rightarrow b \equiv p_i - s_i \; (p_i^2)$$
De esta forma, seguro que la suma no es una potencia porque es divisible por $p_i$ pero no por $p_i^2$.

Entonces, si me tomo $2^n$ primos distintos $p_1, p_2, \cdots , p_{2^n}$ (uno por cada suma de $A$). Tenemos que $b$ debe satisfacer un sistema de congruencias de $2^n$ ecuaciones con todos sus módulos coprimos. Por el Teorema Chino del Resto, infinitos de estos $b$ existen (en particular uno que sea distinto a los otros $n$ números) y lo podemos agregar a $A$ haciendo un conjunto anti-perfecto de $n+1$ elementos.

Inductivamente probamos lo que queríamos. En particular, existe un conjunto anti-perfecto de $2022$ elementos.
1  
This homie really did 1 at P6 and dipped.
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: Simulacro Nacional 2022 Politecnico - Nivel 3 Problema 6

Mensaje sin leer por Fran5 »

Para b)
Spoiler: mostrar
Tomemos los números $a_1= 2^1, a_2 = 2^2, \ldots, a_{2022}=2^{2022}$. Cualquier suma será múltiplo de $2$ y menor ó igual a $2^{2023}$.
Para que no sean potencia perfecta, podemos buscar un factor primo mayor a $2^{2023}$ cuyo exponente también sea un primo mayor a $2023$. Esto es, consideremos $C = p^q$ para $p \geq 2^{2023}$ y $q \geq 2023$ primos. Luego los números $b_1 = Ca_1, \ldots, b_{2022} = Ca_{2022}$ son antipotencia:

Cualquier suma $S$ verifica que $p^q \mid \mid S$ ya que ninguna suma de los $a_i$ puede generar un nuevo factor $p$, de donde, si $S$ es potencia perfecta, necesariamente $S = (2 \cdot p \cdot algo)^q$. Sin embargo, no es verdad que $2^q \mid S$, de modo que no puede ser una potencia perfecta.
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Responder