OBM 2018 - Nível 3 - P2

Problema 2

Azambuja escreve um número racional $q$ em uma lousa. Uma operação consiste em apagar $q$ e substituí-lo por $q+1$; ou por $q-1$; ou por $\frac{q-1}{2q-1}$ se $q\neq \frac{1}{2}$. O objetivo final de Azambuja é escrever o número $\frac{1}{2018}$ após realizar uma quantidade finita de operações.

a) Mostre que se o número inicial escrito é $0$, então Azambuja não poderá alcançar seu objetivo.

b) Encontre todos os números iniciais para os quais Azambuja pode atingir seu objetivo.

Solução de Caio Hermano:

a) Primeiramente vejamos que se $q=\frac{a}{b}$ é o número racional escrito na lousa, com $a,b\in \mathbb{Z},b>0$ e $mdc(a,b)=1$, então Azambuja pode trocá-lo por algum dos seguintes números racionais $\frac{a}{b}+1=\frac{a+b}{b}$ (operação $1$); ou $\frac{a}{b}-1=\frac{a-b}{b}$ (operação $2$); ou $\frac{\frac{a}{b}-1}{2\frac{a}{b}-1}=\frac{a-b}{2a-b}$ se $(a,b)\neq (1,2)$ (operação $3$) e note que $mdc(a-b,2a-b)=mdc(a-b,a)=mdc(a+b,a)=mdc(a,b)=1$. Observe ainda que o novo denominador será $b$ ou $|2a-b|$, ou seja, possui a mesma paridade que $b$, pois $2a-b\equiv -b\equiv b$ $(mod$ $2)$. Assim, temos como invariante a paridade do denominador do número escrito na lousa. Daí, como o denominador de todo inteiro ($0$ inclusive) é $1$ que é ímpar, e o denominador de $\frac{1}{2018}$ é $2018$ que é par, Azambuja não poderá alcançar seu objetivo.

b) Vamos demonstrar que Azambuja conseguirá alcançar seu objetivo sempre que o número inicial $q=\frac{a}{b}$ escrito na lousa, com $a,b\in \mathbb{Z},b>0$ e $mdc(a,b)=1$, satisfaz que $b>1$ é par. O resultado encontrado no item a) nos mostra que, para que Azambuja consiga chegar em $\frac{1}{2018}$, o denominador do número que ele recebe deve ser, de fato, par. Vejamos agora que todo número nessas condições satisfaz o enunciado. Mostraremos inicialmente que conseguimos chegar de $q$ a $\frac{1}{2}$ e, depois, que podemos ir de $\frac{1}{2}$ até $\frac{1}{2018}$.

Faça $a=tb+r$ com $t,r\in \mathbb{Z}$ e $0<r<b$ (Algoritmo da Divisão). Se $t\geq 0$, realize $t$ vezes a operação $2$ e chegaremos ao número $q-t=\frac{a}{b}-t=\frac{(tb+r)-tb}{b}=\frac{r}{b}$ e, se $t<0$, realize $|t|$ vezes a operação $1$ e chegaremos ao número $q+|t|=q-t=\frac{a}{b}-t=\frac{(tb+r)-tb}{b}=\frac{r}{b}$. Assim, a partir de qualquer número racional $q=\frac{a}{b}$, Azambuja consegue chegar em $\frac{r}{b}$, com $0<r<b$ e $mdc(r,b)=mdc(a,b)=1$.

Considere agora $b=2k,k\in \mathbb{Z}^*_+$, veremos que é possível diminuir o denominador de $q=\frac{a}{b}$ até chegar em $2$ a partir das operações dadas. Se $k>1$, pelo parágrafo anterior conseguimos chegar de $\frac{a}{2k}$ em $\frac{r}{2k}$, com $0<r<2k$ e $r\neq k$ pois $mdc(r,2k)=1$. Realizando a operação $3$, chegamos em $\frac{r-2k}{2r-2k}=\frac{\pm (r-2k)}{2|r-k|}$, mas $0<r<2k\Rightarrow -k<r-k<k\Rightarrow 2|r-k|<2k$. Logo, alcançamos um número com denominador menor que o anterior e, iterando esse procedimento diversas vezes, encontraremos eventualmente um número na lousa de denominador igual a $2$ (uma vez que, enquanto $k>1$, podemos continuar repetindo esse processo, que não pode se prolongar infinitamente pois há apenas finitos naturais menores que $2k$). Novamente pelo parágrafo anterior, de $\frac{x}{2}$ podemos chegar em $\frac{r'}{2}$, com $0<r'<2\Rightarrow r'=1$. Por conseguinte, Azambuja consegue chegar em $\frac{1}{2}$.

Vejamos agora, que partindo de $\frac{1}{2}$, é possível alcançar $\frac{1}{2018}$. Provaremos por indução em $n\in \mathbb{Z}^*_+$, que conseguimos chegar em $\frac{1}{2n}$ a partir de $\frac{1}{2}$.

Caso inicial: $n=1$ é óbvio.

Hipótese: Suponha que chegamos em $\frac{1}{2k},k\in \mathbb{Z}^*_+$.

Passo Indutivo: Realize a operação $1$ seguida da operação $3$ e chegaremos em $\frac{1}{2k}+1=\frac{2k+1}{2k}$ e, depois, em $\frac{(2k+1)-2k}{2(2k+1)-2k}=\frac{1}{2(k+1)}$. E o resultado segue por indução.

Fazendo $n=1009$, concluímos que Azambuja consegue concluir seu objetivo.

RESPOSTA: $\frac{a}{b}$ com $a,b\in \mathbb{Z},b>0,mdc(a,b)=1$ e $b$ par.