APMO 2020 Problema 3

Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 356
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: Ciudad Gotica

APMO 2020 Problema 3

Mensaje sin leer por Joacoini » Lun 08 Jun, 2020 11:39 pm

Determinar todos los enteros positivos $k$ para los cuales existe un entero positivo $m$ y un conjunto $S$ de enteros positivos tal que cualquier entero $n>m$ se puede escribir como suma de elementos de $S$ de exactamente $k$ maneras.
NO HAY ANÁLISIS.

Avatar de Usuario
enigma1234

OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 103
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 4
Nivel: 2

Re: APMO 2020 Problema 3

Mensaje sin leer por enigma1234 » Mié 10 Jun, 2020 12:37 am

Spoiler: mostrar
Si $S$ fuera un conjunto finito entonces cualquier número mayor a la suma de todos los elementos de $S$ no se puede expresar como suma de elementos distintos de $S$. Entonces $S$ es infinito, sea $S=\{a_1,a_2,\dots\}$ tal que $a_1<a_2<a_3<\dots$.

Lema 1: Para todo $a_n>m$ las $k$ formas de expresar cada número de la forma $a_n+l$ contienen a $a_n$ y números menores a $a_n$ como sumandos para todo $m+1\leq l\leq a_n-1$.
Demostración:
Spoiler: mostrar
Como $m+1\leq l$ entonces $l$ se puede expresar exactamente de $k$ maneras como suma de elementos de $S$, y como $l\leq a_n-1$ los sumandos son menores que $a_n$. Entonces al agregar $a_n$ a cada forma tendremos $k$ maneras distintas de expresar $a_n+l$ que contienen a $a_n$ y numeros menores a $a_n$ como sumandos.
Lema 2: Para todo $a_n\geq 2m+2$ tenemos que $a_{n+1}\geq 2a_n$.
Demostración:
Spoiler: mostrar
Si $a_n<a_{n+1}\leq a_n+m\to a_n+m+1<a_{n+1}+m+1\leq a_n+2m+1\leq 2a_n-1$ entonces por el lema 1 las $k$ maneras de expresar $a_{n+1}+m+1$ contienen $a_{n+1}$. Tambien por el lema 1 los sumandos de las $k$ maneras de expresar $a_{n+1}+m+1$ son menores e iguales a $a_n$ pero como $a_n<a_{n+1}$ es una contradicción. Entonces $a_{n+1}>a_n+m$.

Si $a_n+m+1\leq a_{n+1}\leq 2a_n-1$ entonces $a_{n+1}$ se puede expresar de $k+1$ maneras distintas($k$ maneras del lema 1 y como $a_{n+1}$) lo cual no es posible. Por lo tanto $a_{n+1}\geq 2a_n$.
Lema 3:Existe $N$ tal que para todo $a_n>N$ se cumple que $2a_n=a_{n+1}$
Demostración:
Spoiler: mostrar
Sea $a_n\geq 2m-2$.Veamos las formas de escribir $2a_n$ como suma de elementos de $S$ tal que $a_n$ es uno de esos sumandos. Claramente esto es igual a la cantidad de formas de escribir $a_n$ como suma de elementos distintos de $S$ tal que todos los sumandos son distintos de $a_n$, y esto es exactamente $k-1$ maneras (la otra es escribirlo como $a_n$). Entonces hay exactamente una manera de escribir $2a_n$ como suma de elementos distintos de $S$ tal que $a_n$ no es ninguno de los sumandos.

Sea $X_n=2a_n-a_{n-1}-a_{n-2}-\dots-a_1$. Entonces $X_{n+1}-X_n=2a_{n+1}-3a_n\geq a_n>m$. Entonces como $X_n$ es entero entonces existe $N$ tal que $X_n>0$ para todo $n$ que cumple que $a_n>N$. Entonces si $2a_n<a_{n+1}$ entonces la manera de expresar $2a_n$ como suma de elementos de $S$ tiene sumandos menores a $a_{n+1}$ y como no tiene a $a_n$ como algun sumando entonces:
$$2a_n=a_{n_1}+\dots+a_{n_k}\leq a_1+a_2+\dots a_{n-1}\to X_n\leq 0$$
Lo cual no es posible. Entonces $2a_n=a_{n+1}$ para todo $a_n>N$.
Entonces $S$ se puede expresar de la forma $S=\{b_1,b_2,\dots b_r\}\cup\{c,2c,2^2c,2^3c,\dots\}$ tal que $b_1<b_2<\dots<b_r$ y no existe $j$ tal que $2b_j=c$.
Consideremos:
$$F(x)\equiv \displaystyle\prod_{a_i\in S}^{}(1+x^{a_i})\equiv \displaystyle\prod_{i=1}^{r}(1+x^{b_i})\displaystyle\prod_{j=0}^{\infty}(1+(x^{c})^{2^j}) $$
Como:
$$\displaystyle\prod_{j=0}^{k}(1+(x^{c})^{2^j})\equiv \frac{1-x^{c\times 2^{k+1}}}{1-x^c}\to \displaystyle\prod_{j=0}^{\infty}(1+(x^{c})^{2^j})\equiv \frac{1}{1-x^c} \text{ $\forall$ $|x|<1$} $$
Claramente el coeficiente de $x^n$ es la cantidad de maneras de escribir $n$ como suma de elementos distintos de $S$ para $n>0$, entonces tendremos que:
$$F(x)\equiv \displaystyle\sum_{i=0}^{m}d_ix^i+kx^{m+1}+kx^{m+2}+\dots\equiv \displaystyle\sum_{i=0}^{m}d_ix^i+\frac{kx^{m+1}}{1-x} \text{ $\forall$ $|x|<1$} $$

Entonces tendremos que:
$$\displaystyle\prod_{i=1}^{r}(1+x^{b_i})\times \frac{1}{1-x^c}\equiv \displaystyle\sum_{i=0}^{m}d_ix^i+\frac{kx^{m+1}}{1-x} \text{ $\forall$ $|x|<1$} $$

$$\to \displaystyle\prod_{i=1}^{r}(1+x^{b_i})\equiv \left(\left(\displaystyle\sum_{i=0}^{m}d_ix^i\right)\times (1-x)+kx^{m+1}\right) \times(1+x+\dots+x^{c-1})\text{ $\forall$ $|x|<1$}\dots (1) $$
Dado a que ambos lados son polinomios tendremos que se cumple para todo $x$.
Caso 1: $c>1$
Spoiler: mostrar
Entonces tendremos que $A_t=e^{i\frac{\pi\times t}{c}}$ es raiz de $1-x^c$ y no es raiz de $1-x$($1\leq t\leq c-1$), entonces es raiz de $1+x+\dots+x^{c-1}$. Entonces $A_t$ es raiz de $\displaystyle\prod_{i=1}^{r}(1+x^{b_i})$ tendremos que existe un $j$ tal que $1+A_t^{b_j}=0$.

Las raíces de $1+x^z=\frac{1-x^{2z}}{1-x^z}$ son las raices de $1-x^{2z}$ que no son raices de $1-x^z$. Tenemos que las raíces de $1-x^{2z}$ son de la forma $e^{i\frac{\pi\times k}{2z}}$ con $0\leq k<2z$ y las raices de $1-x^z$ son de la forma $e^{i\frac{\pi\times k}{z}}$ con $0\leq k\leq z$.

Entonces las raices de $1+x^z$ son de la forma $e^{i\frac{\pi\times (2q-1)}{2z}}$ donde $1\leq q\leq z$.

Entonces al ser $A_t$ una raiz de $1+x^{b_j}$ entonces $A_t=e^{i\frac{\pi\times t}{c}}=e^{i\frac{\pi\times (2q-1)}{2b_j}}$ y como $\frac{t}{c},\frac{2q-1}{2b_j}<1$ entonces para cada $1\leq t\leq c-1$ existe $j$ y $1\leq q\leq b_j$ tal que $\frac{t}{c}=\frac{2q-1}{2b_j}$.

Si $t=2^v$ tal que $2^v<c\leq 2^{v+1}$ tendremos que existe $j$ y $1\leq q\leq b_j$ tal que:
$$2^v\times 2b_j=(2q-1)\times c\to 2^{v+1}\mid c\to 2^{v+1}\leq c\leq 2^{v+1}\to c=2^{v+1}$$
Entonces $c$ es una potencia de $2$.
Si $c=1$ tambien tendremos que es una potencia de 2, entonces $c$ siempre es una potencia de $2$.

En $(1)$ para $x=1$ tenemos que:
$$2^r=k\times (1+1+\dots 1)=kc$$
De esto claramente tendremos que $k$ debe ser una potencia de $2$(pues es entero).

Ahora veamos que $k=2^u$ cumple para todo $0\leq u$.
Spoiler: mostrar
Si $S=A\cup B$ donde $A$ y $B$ son disjuntos, $|A|=u$ y $B=\{1,2,2^2,\dots\}$. Sea $s(X)$ es la suma de los elementos del conjunto $X$(si $X$ es vacio entonces $s(X)=0$). Veamos que $m=s(A)$ cumple. Como es comocido que cada entero positivo se puede expresar exactamente de una manera como suma de potencias distintas de $2$, tenemos que para cada $n>m$ la forma de escribir $n-s(C)$ como suma de elementos de $B$ es única, donde para cada subconjunto $C$ de $A$. Entonces la cantidad de formas de escribir $n$ como suma de elementos de $S$ es la cantidad de elementos de $A$ que es $2^u$.
1  

Responder