OBM 2019 - Nível 3 - P4

Problema 4

Prove que para todo inteiro positivo $m$, existe um inteiro positivo $n_m$ tal que para todo inteiro positivo $n\geq n_m$, existem inteiros positivos (não necessariamente distintos) $a_1, a_2, . . . , a_n$ tais que

$\frac{1}{a^m_1}+\frac{1}{a^m_2}+. . .+\frac{1}{a^m_n}=1$.

Solução de Caio Hermano:

Se existem $a_1,a_2,...,a_t\in \mathbb{Z}^*_+$ tais que $\frac{1}{a^m_1}+\frac{1}{a^m_2}+. . .+\frac{1}{a^m_t}=1$, dizemos que $t$ é $<i>m$-intelectual. Queremos provar que $\exists n_m\in \mathbb{Z}^*_+$ tal que todo inteiro positivo $n\geq n_m$ é $<i>m$-intelectual.

Observe que $\frac{1}{a^m_i}=\frac{A^m}{A^ma^m_i}=\frac{1}{(Aa_i)^m}+(A^m-1) \cdot \frac{1}{(Aa_i)^m}$. Assim, conseguimos acrescentar $(A^m-1)$ termos na soma para todo $A\in \mathbb{Z}^*_+$, isto é, se $t$ é $m$-intelectual $\Rightarrow t+(A^m-1)$ também é $m$-intelectual. Iterando esse processo $x$ vezes, então $t+x(A^m-1)$ é $m$-intelectual. Ainda, podemos realizar a operação anterior $y$ vezes com outro inteiro positivo $B$, concluindo que o número $t+x(A^m-1)+y(B^m-1)$ é, também, $m$-intelectual.

Lema: Sejam $a,b\in \mathbb{Z}^*_+$ primos entre si, isto é, tais que $mdc(a,b)=1$. Existe um inteiro positivo $N$ tal que todos os inteiros positivos $n\geq N$ podem ser representados da forma $n=ax+by, x,y\in \mathbb{Z}^*_+$.

Pelo Teorema de Bezout, existem $x_0,y_0\in \mathbb{Z}$ tais que $ax_0+by_0=mdc(a,b)=1 \Rightarrow$ $a(nx_0) + b(ny_0) = n$. Seja que $(x,y)\in \mathbb{Z}^2$ uma solução qualquer da equação $ax+by=n$ diferente do par $(nx_0,ny_0)=(c,d)$ por conveniência, daí: $ax+by=ac+bd\Rightarrow$ $a(x-c)=b(d-y)\Rightarrow$ $\frac{a}{b}= \frac{d-y}{x-c}\Rightarrow$ $\exists k\in \mathbb{Z} | d-y=ka$ e $x-c=kb \Rightarrow$ $(x,y)=(c+kb,d-ka)$. Verificamos facilmente que todos os pares dessa forma são, de fato, soluções da equação $ax+by=n$ ($a(c+kb)+b(d-ka)=ac+bd=n$).

Considere $n\geq 2ab$ um inteiro, vimos que há infinitas soluções $(x,y)=(c+kb,d-ka)$ da equação $ax+by=n$. Suponha por absurdo que sempre teremos $x$ ou $y$ não positivos, daí: $c+kb\leq 0 \iff k\leq -\frac{c}{b}$ ou $d-ka\leq 0 \iff k\geq \frac{d}{a}$. Então, temos que: $\frac{d}{a}-(-\frac{c}{b})<2$, pois senão haveria um inteiro $k | \frac{d}{a}>k>-\frac{c}{b} \Rightarrow n=ac+bd<2ab$. Logo, haverá uma solução com entradas inteiras e positivas para a equação $ax+by=n$ para todo $n\geq N=2ab$.

Veja que $\frac{1}{1^m}=1 \Rightarrow 1$ é $m$-intelectual. Daí, todos os números da forma $1+x(A^m-1)+y(B^m-1)$ também são $m$-intelectuais. Tomando $n_m=N-1$, pelo Lema, todos os inteiros positivos $n\geq N=n_m+1$ pode ser representado da forma $1+x(A^m-1)+y(B^m-1)$. Portanto, existe um inteiro positivo $n_m$ tal que para todo inteiro positivo $n\geq n_m$ é $m$-intelectual.

Observação: A cota de $N$ no lema acima não é optimal. Para saber mais, considere ler o Exemplo 12 deste material do POTI sobre MMC, MDC e Algortimo de Euclides. Temos no artigo a melhor cota atingível que é $N=(a-1)(b-1)$.