Invariantes

É interessante procurarmos, no problema, coisas que não variam.

Para que você consiga encontrar invariantes é útil entender bem as transformações pelo qual elas passam (ou as características principais dos elementos do problema). Por isso, é útil fazer vários exemplos para que você consiga encontrar um padrão.

Como Encontrar Invariantes

• Faça pequenos casos
• Estude como são as transformações e procure características importantes sobre elas
• Em certos momentos, você deve fazer a própria invariante aparecer.

Exemplo (OBM 2012 - 3ª Fase - Nível 2)

Quando duas amebas vermelhas se juntam, se transformam em uma única ameba azul; quando uma ameba vermelha se junta com uma ameba azul, as duas se transformam em três amebas vermelhas; quando duas amebas azuis se juntam, elas se transformam em quatro amebas vermelhas. Um tubo de ensaio tem inicialmente $201$ amebas azuis e $112$ amebas vermelhas.

(a) É possível que após algumas transformações o tubo contenha $100$ amebas azuis e $314$ amebas vermelhas?

(b) É possível que após algumas transformações o tubo contenha $99$ amebas azuis e $314$ amebas vermelhas?

Solução:

(a) Vamos pensar nas transformações apenas em termos de cores (sem levar em conta as quantidades). Podemos transformar vermelhas em azuis (e vice-versa). Já se tivermos azuis e vermelhas juntas, podemos apenas transformá-las em vermelhas. Então, é mais "fácil" obtermos vermelhas do que azuis, nesse sentido.

Por isso, uma estratégia interessante separarmos da quantidade inicial $100$ amebas azuis. As $101$ azuis e $112$ vermelhas restantes podem ser transformadas em $314$ vermelhas? Sabemos que uma azul e uma vermelha pode ser transformada em três vermelhas. Então, como temos $101$ azuis, façamos a seguinte transformação: $101$ azuis e $101$ vermelhas em $303$ vermelhas.

Assim, além das $100$ amebas azuis, teremos $303$ vermelhas (que foram transformadas) junto com outras $11$ desta mesma cor (que não foram usadas na última transformação), totalizando $303+11=314$.

(b) Encontremos uma invariante neste problema. Aqui mostraremos que a quantidade de vermelhas somado com o dobro da quantidade de azuis nunca muda com as transformações. Analisemos cada transformação.

• Duas amebas vermelhas se juntam, se transformam em uma única ameba azul.

Se tivermos inicialmente $x$ vermelhas e $y$ azuis, após esta transformação teremos $x-2$ e $y+1$ azuis. Em ambos os casos, a soma das quantidades de vermelhas com o dobro da de azuis é igual a $x+2y$.

• Uma ameba vermelha se junta com uma ameba azul, as duas se transformam em três amebas vermelhas.

Análogo ao caso anterior.

• Duas amebas azuis se juntam, elas se transformam em quatro amebas vermelhas.

Análogo ao caso anterior.

Na configuração inicial, a soma das quantidades de vermelhas com o dobro da de azuis é $514$, enquanto a configuração do item (b) tem essa quantidade igual a $512$. Logo, é impossível sair de uma e chegar na outra.

Exemplo (Cone Sul 1993)

Em uma mesa está uma pilha com $T$ discos que de forma incremental deve ser convertida em pilhas com três discos cada. Cada passo consiste em selecionar uma pilha removendo um dos seus discos. E então a pilha que sobrou é separada em duas pilhas. Existe uma sequência de passos que pode realizar este processo?

(a) $T=1000$

(b) $T=2001$

Solução: Considere $n$ e $m$ o números discos e o de pilhas, no começo, respectivamente. Vamos entender o que cada movimento faz com o número de pilhas e de discos.

O número de discos diminui em $1$ unidade (pois tiramos um disco) e o número de pilhas aumenta $1$ unidade (pois transformamos uma pilha em duas). Desta forma, a soma das quantidades de pilhas e discos é sempre a mesma (encontramos nossa invariante). Esta soma deve ser a mesma do começo, ou seja, $m+n$.

(a) Na primeira rodada, $n=T=1000$ e $m = 1$. Logo, $m+n=1001$.

Vamos pensar, agora, na última rodada. Nela haverão apenas pilhas com três discos, ou seja, o número de discos deve ser o triplo do número de pilhas. Assim, a soma do número de pilhas com o de discos de ser um múltiplo de $4$.

Mas como essa soma é sempre a mesma, segue que, $1001$ é um múltiplo de $4$. Absurdo. Logo, é impossível realizar este processo.

(b) Análogo.

Exemplo (OBM 2022 - Níveis 2 e 3)

Um jogo para uma pessoa tem as seguintes regras: inicialmente há dez pilhas de pedras, com $1, 2, 3, \ldots, 10$ pedras, respectivamente. Uma jogada consiste em fazer uma das duas seguintes operações:

(i) escolher duas pilhas, cada uma com pelo menos duas pedras, juntá-las e depois adicionar mais duas pedras a nova pilha;

(ii) escolher uma pilha com pelo menos 4 pedras, tirar duas pedras dela e separá-la em duas pilhas de quantidades de pedras positivas escolhidas pelo jogador.

O jogo continua até não ser mais possível fazer uma operação. Mostre que o número de pilhas com apenas uma pedra ao final do jogo é sempre o mesmo, independentemente de como se realizam as jogadas.

Observação: A versão do Nível 2 desse problema tem três itens:

(a) Dê um exemplo de uma sequência de jogadas que conduzem ao término do jogo.

(b) Faça uma tabela informando qual é o número total de pedras e o número de pilhas no início e após cada uma das 5 primeiras operações no seu exemplo acima.

E o item (c) é equivalente ao problema do Nível 3. Não resolveremos os primeiros dois itens.

Solução: Sejam $N_i$ e $P_i$ o número de pilhas depois de $\ i\$ jogadas; temos, claramente, que $N_0=10$ e $P_0=1+2+\ldots+9+10=55$. Os dois tipos de jogadas mudam $N$ e $P$ das seguintes maneiras:

A jogada (i) transforma $N$ em $N-1$ e transforma $P$ em $P+2$.

A jogada (ii) transforma $N$ em $N+1$ e transforma $P$ em $P-2$.

Observe que a diferença $P-N$ sempre aumenta ou diminui por 3, o que significa que o resto de $P-N$ numa divisão por 3 é sempre constante. No nosso caso, $P_0-N_0=55-10=45\equiv 0 \ \ (\text{mod } 3)$.

Outra coisa a se observar é que o jogo só acaba quando $P-N=0$. De fato, $P-N=1$ ou $P-N=2$ são impossíveis pelo que acabamos de provar, e $P-N \geq 3$ significaria que há pelo menos mais 3 pedras do que pilhas, ou seja, uma das jogadas ainda pode ser feita porque existe ou uma pilha com 4 pedras ou um par pilhas com pelo menos 2 pedras. Assim, como afirmamos, o jogo só acaba quando $P-N=0$ ou, de modo equivalente, $P=N$. Aqui, todas as $N$ pilhas no final têm uma pedra.

Seja, então, $D_i=P_i-N_i$. Inicialmente, $D_0=45$. A jogada (i) transforma $D$ em $D+3$ e a jogada (ii) transforma $D$ em $D-3$. Isso significa que as jogadas (i) e (ii) se anulam em relação ao valor de $D$, e também que um aumento no valor de $D$ significa mais jogadas (i) do que (ii), e vice-versa.

Suponha, por fim, que conseguimos fazer um jogo completo com $k$ jogadas e levamos $D_0=45$ a $D_k=0$. Como o valor de $D$ diminuiu, fizemos mais jogadas (ii) do que (i). Quantas a mais? Considerando que fizemos $n$ jogadas (ii) a mais, levamos $D_0=45$ a $D_k=D_0-3n=0$, ou seja:

$45=3n\implies n=15$

Fizemos 15 jogadas (ii) a mais, e isso levou $N_0=10$ a $N_k=N_0+n=10+15=25$ pilhas de tamanho 1 (porque agora $P=N$). De modo equivalente, poderíamos argumentar que levamos $P_0=55$ a $P_k=P_0-2n=55-30=25$, confirmando que $P=N$. Ou seja, o número de pilhas de tamanho 1 no final é sempre constante e é 25.

Exemplo (OBM 2018 - Nível 2)

Numa lousa estão escritos inicialmente os números $1,2,\ldots ,10$. Para quaisquer dois números $a$ e $b$ na lousa chamamos de $S_{a,b}$ a soma de todos os números na lousa com exceção de $a$ e $b$. Uma operação permitida é escolher dois números $a$ e $b$ na lousa, apagá-los e escrever o número $a+b+\dfrac{ab}{S_{a,b}}$ . Após realizar essa operação algumas vezes restam na lousa apenas dois números $x$ e $y$, com $x \geq y$.

a) Quantas operações foram realizadas?

b) Determine o maior valor possível para $x$.

Solução:

a) Cada operação diminui por 1 a quantidade de números na lousa (escrevemos um e apagamos dois), então, se começamos com 10 números e terminamos com 2, 8 operações foram realizadas.

b) Efetuar essa operação uma única vez parece trabalhoso especialmente por causa da parte do $a+b+\dfrac{ab}{S_{a,b}}$, fazê-la 8 vezes é ainda pior. Vamos pegar um caso menor: 1,2,3.

Se fizermos a operação com 1 e 2, apagaremos os dois e ficaremos com os números 3 e

$1+2+\dfrac{2}{3}=3+\dfrac{2}{3}=\dfrac{11}{3}$

Se fizermos a operação com 1 e 3, apagaremos os dois e ficaremos com os números 2 e

$1+3+\dfrac{3}{2}=4+\dfrac{3}{2}=\dfrac{11}{2}$

Se fizermos a operação com 2 e 3, apagaremos os dois e ficaremos com os números 1 e

$2+3+\dfrac{6}{1}=11$

Curioso... parece que sempre sobram os números $k$ e $11/k$. O que 11 tem de especial aqui? Vamos fazer outro caso e ver se ajuda: os números 2,3 e 4.

Se escolhermos o par (2,3) ficam 4 e

$2+3+\dfrac{6}{4}=\dfrac{26}{5}$

Se escolhermos (2,4) ficam 3 e

$2+4+\dfrac{8}{3}=\dfrac{26}{3}$

Finalmente, escolhendo (3,4) ficam 2 e:

$3+4+\dfrac{12}{2}=\dfrac{26}{2}$

Agora, parece que sobram $k$ e $26/k$, o que significa que 11 não era especial em geral nem 26. Vamos ver se conseguimos descobrir, com números genéricos $a, b$ e $c$:

Se fizermos a operação com $a$ e $b$, ficarão $c$ e:

$a+b+\dfrac{ab}{c} = \dfrac{ac+bc+ab}{c}$

Ou seja, sempre sobram $\dfrac{ac+bc+ab}{k}$ e $k$. Parece que a soma dos produtos dois a dois dos números é importante de alguma maneira.

Compensa analisar melhor o que essa operação faz, especialmente em casos maiores. Se os números $a,b,c,d$ estão na lousa e fazemos a operação com $a$ e $b$, ficam os números $c$, $d$ e

$a+b+\dfrac{ab}{c+d}=\dfrac{ac+ad+bc+cd+ab}{c+d}$

Aqui, não parece que sobrou algo como vimos no caso de três letras. E se experimentarmos fazer o produto desse resultado com $c$ e $d$ separadamente? Afinal, como vimos, a soma dos produtos dos números dois a dois é importante. Ficaremos, então, com:

$\dfrac{c(ac+ad+bc+cd+ab)}{c+d}$

E

$\dfrac{d(ac+ad+bc+cd+ab)}{c+d}$

Somando isso a cd, teremos:

$\dfrac{(c+d)(ac+ad+bc+cd+ab)}{(c+d)} + cd =ac+ad+bc+cd+ab+cd$

Ora, ora! Parece que, mesmo depois que fizemos a operação, a soma dos produtos dois a dois dos números não mudou! Ela é a nossa invariante, certo? Ainda não provamos isso. Vamos fazer um procedimento similar para provar o caso geral.

Sejam $p,q,a_1,a_2,\ldots,a_n$ os $n+2$ números da lousa. Se fizermos a operação com $p$ e $q$, ficaremos com $a_1, a_2, \ldots, a_n$ e o número

$p+q+\dfrac{pq}{a_1+\ldots+a_n}$

Se calcularmos a soma dos produtos dois a dois dos novos números, ficamos com:

$\left(p+q+\dfrac{pq}{a_1+\ldots+a_n}\right) a_1 + \ldots+\left(p+q+\dfrac{pq}{a_1+\ldots+a_n}\right)a_n + a_1 a_2+\ldots+a_{n-1} a_n$

$=\left(p+q+\dfrac{pq}{a_1+\ldots+a_n}\right)(a_1 + \ldots + a_n )+a_1 a_2+\ldots+a_{n-1} a_n$

$=p(a_1+\ldots+a_n )+q(a_1+\ldots+a_n )+pq+a_1 a_2+\ldots+a_{n-1} a_n$

$=pa_1+\ldots+pa_n+qa_1+\ldots+qa_n+pq+a_1 a_2+\ldots+a_{n-1} a_n$

Que é exatamente a soma dos produtos dois a dois dos nossos $n+2$ números iniciais, ou seja, é uma invariante! Agora sim estamos em condições de finalizar o problema.

Como restam apenas $x$ e $y$ na lousa, $xy$ deve ser igual à soma dos produtos dois a dois dos números de 1 até 10, que por enquanto chamaremos de $N$. Assim,

$xy=N$

Queremos maximizar $x$, o que equivale a minimizar $y$. Como a operação não nos dá números menores que 1 e o menor número na lousa inicial é 1, $y=1$ é o menor valor possível. Donde $x=N$ é o maior valor possível! Podemos calcular $N$ à mão, lembrando que $1+2+\ldots+10=55$:

$2N=1(55-1)+2(55-2)+\ldots+10(55-10)$

$2N=54+2\cdot53+3\cdot52+4\cdot51+5\cdot50+\ldots+10\cdot45$

$2N=54+106+156+204+250+294+336+376+414+450$

$2N=2640\implies N=1320$

Assim, o maior valor possível de $x$ é $1320$.

Exemplo (Cone Sul 2020)

Há uma pilha com 15 fichas sobre uma mesa. A cada passo, Pedro escolhe uma das pilhas na mesa com $a>1$ fichas, divide em duas pilhas com $b \geq 1$ e $c\geq 1$ fichas e escreve no quadro o produto $abc$. Ele continua até ter 15 pilhas com 1 ficha cada. Determine todos os valores possíveis para a soma final dos números escritos no quadro.

Observação: Esse problema é bem parecido com esse outro da OBM, mas a solução é bem diferente.

Solução: Fazendo casos pequenos, podemos notar que 2 fichas sempre resulta numa soma igual a 2, 3 fichas sempre resulta numa soma igual a 8, 4 fichas numa soma igual a 20 e 5 fichas numa soma igual a 40. Podemos começar a suspeitar que, para um determinado número de fichas, o resultado seja sempre o mesmo. Vamos fazer indução forte para provar isso: já fizemos os casos base, agora vamos supor que para algum $k$, todos os números de fichas menores que $k$ fazem Pedro calcular uma soma fixa. Vamos encontrar uma fórmula para essa soma.

Seja $S(n)$ a soma escrita com $n<k$ fichas, definindo por convenção que $S(1) = 0$. É possível notar que, se $a+b=n$, temos que $a<k$ e $b<k$ e que $S(n) = S(a) + S(b) + nab$. Assim, para $n<k$:

$S(n) = S(n-1) + \cancel{S(1)} + n(n-1) = S(n-2) + (n-1)(n-2) + n(n-1) = \ldots$

E assim por diante, até concluirmos que $S(n) = 1\cdot 2 + 2\cdot 3 + \ldots + (n-1)n$. Podemos recordar (ou talvez concluir novamente) que essa soma é igual a $\dfrac{n(n+1)(n-1)}{3}$. Assim, estamos supondo como hipótese da nossa indução forte que $S(n) = \dfrac{n(n+1)(n-1)}{3}$ para todo $n<k$. Vamos provar que $S(k) = \dfrac{k(k+1)(k-1)}{3}$.

Vamos supor que repartimos a pilha com $k$ fichas em uma de $a$ e outra de $b$, de forma que $a+b=k$:

$S(k) = S(a) + S(b) + kab$

Impondo nossa condição da soma e sabendo que $a<k$ e $b<k$, temos que, pela hipótese:

$S(k) = \dfrac{a(a+1)(a-1)}{3} + \dfrac{b(b+1)(b-1)}{3} + (a+b)ab$

Reagrupando e expandindo isso:

$S(k) = \dfrac{a(a+1)(a-1) + b(b+1)(b-1) + 3(a+b)ab}{3}$

$S(k) = \dfrac{a^3 - a + b^3 - b + 3(a+b)ab}{3}$

$S(k) = \dfrac{(a+b)(a^2-ab+b^2) - (a+b) + 3(a+b)ab}{3}$

$S(k) = \dfrac{(a+b)(a^2-ab+b^2 - 1 + 3ab)}{3}$

$S(k) = \dfrac{(a+b)((a+b)^2-1)}{3} = \dfrac{(a+b)(a+b+1)(a+b-1)}{3} = \dfrac{k(k+1)(k-1)}{3}$

Como queríamos. Assim, a única soma que Pedro pode obter é $\frac{14\cdot 15 \cdot 16}{3} = 1120$.

Exemplo (OBM 2018 - Nível 3 - Adaptada)

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. Mostre que se o número escrito é $0$, então Azambuja não poderá alcançar o seu objetivo.

Solução: A primeira coisa que incomoda é transformar o número em $q$ em $\frac{q-1}{2q-1}$, afinal se fizermos a transformação várias vezes, fica um pouco chato de calcular onde iremos parar. Por isso, vale a pena pensar melhor nessa transformar e ver se conseguimos simplificar um pouco. Considere $q'=\frac{q-1}{2q-1}$. Seria legal uma expressão mais simples que relacionasse $q$ e $q'$. Observe que

$q'=\frac{q-1}{2q-1} \Leftrightarrow q'(2q-1)=q-1 \Leftrightarrow 2qq'-q-q'+1=0.(*)$

Seria legal se conseguíssemos fatorar do lado esquerdo da última igualdade. Mas o máximo que conseguimos fazer é $q(2q'-1)-(q'-1)=0$. Ainda não dá para terminar. No primeiro parênteses aparece $2q'$, enquanto no segundo $q'$. Vamos forçar então uma boa fatoração. Como podemos fazer esse $2$ sumir? Se dividirmos os dois lados de $(*)$ por $2$:

$qq'-\frac{q}{2}-\frac{q'}{2}+\frac{1}{2}=0.(**)$

Está quase "fatorável", afinal podemos escrever $q\left(q'-\frac{1}{2}\right)-\frac{1}{2}(q'+1)=0.$Para forçarmos $q'-\frac{1}{2}$ no segundo parênteses, vamos subtrair $\frac{1}{4}$ dos dois lados de $(**)$:

$qq'-\frac{q}{2}-\frac{q'}{2}+\frac{1}{4}=-\frac{1}{4} \Leftrightarrow \left(q-\frac{1}{2}\right)\left(q'-\frac{1}{2}\right)=-\frac{1}{4}.$

Por isso, vale a pena considerarmos $u=q-\frac{1}{2}(*)$ e $u'=q'-\frac{1}{2}$. Assim $uu'=-\frac{1}{4}$. E quanto as transformações que levam $q$ em $q+1$ ou $q-1$? Observe que essas transformações levam $q-\frac{1}{2}$ em $q-\frac{1}{2}+1$ ou $q-\frac{1}{2}-1$. Por isso, $u$ pode ser levado por elas em $u+1$ ou $u-1$. Ou ainda podemos transformá-lo em $u'$ tal que $uu'=-\frac{1}{4}$.

Nosso problema pode ser reduzido a: começar com $u=\frac{1}{2}$ (afinal $q=0$ se, e somente se, $u=-\frac{1}{2}$) e somar $1$ ou $-1$ ou transformar em $u'$ de forma que $uu'=-\frac{1}{4}$. Já simplificamos. Mas parece que podemos simplificar mais. Notemos que

$uu'=-\frac{1}{4} \Leftrightarrow 4uu'=-1 \Leftrightarrow (2u)(2u')=-1.$

Se fizermos $v=2u(**)$ e $v'=2u'$, então $vv'=-1$. Nosso problema se resume às seguintes regras: começamos com $v=-1$ (afinal $u=-\frac{1}{2}$ se, e somente se, $v=-1$) podemos transformar $v$ em $v+2$ (afinal se $u$ é transformado em $u+1$, então $2u$ é transformado em $2(u+1)=2u+2$) ou em $v-2$ (pelo mesmo raciocínio) ou em $v'$ de forma que $vv'=-1$.

Agora parece mais fácil controlarmos as transformações. Como $v$ começa racional, ele vai ser racional o tempo todo. Tomemos $v=\frac{r}{s}$ com $\operatorname{mdc}(r,s)=1$. Vamos ver o que acontece com essa fração quando fazemos as transformações. Para facilitar a escrita, vamos associar a fração com um par $(r, s)$ e ver o que ocorre com ele.

Se transformarmos $v$ em $v+2$ isso equivale a transformar $(r, s)$ em $(r+2s,s)$ (afinal $\frac{r}{s}+2=\frac{r+2s}{s}$). Pelo mesmo raciocínio, levar $v$ em $v-2$ equivale a levar $(r, s)$ em $(r-2s,s)$. Finalmente, transformar $v$ em $v'$ de forma que $vv'=-1$ equivale a transformar $(r, s)$ em $(-s,r)$ (de fato, $\frac{r}{s}\left(\frac{-s}{r} \right)=-1$).

Observe que começarmos em $v=-1$ (ou seja, com o par $(-1, 1)$) e Azambuja quer parar em $v=-\frac{1008}{1009}$ (com efeito, por $(*)$ e $(**)$, $v=2q-1$ e por isso, $q=\frac{1}{2018}$ se, e somente se, $v=-\frac{1008}{1009}$), ou seja, em $(-1008,1009)$.

Será que existe algum invariante nas transformações? Observe que se $(r, s)$ é formado por dois ímpares, então $(r+2s,s)$, $(r-2s,s)$ e $(-s,r)$ também são. Desta forma, os dois números sempre serão ímpares, independente das transformações. Logo, é impossível chegar em $(-1008,1009)$.

Invariantes e Restos

Prestar atenção em restos pode ser uma estratégia interessante para encontrarmos invariantes.

Algo importante aqui é o seguinte: somar um múltiplo de $m$ a um número não altera o seu resto na divisão por $m$.

Exemplo (IMO 1996)

São dados um inteiro positivo $r$ e um tabuleiro retangular $ABCD$ com dimensões $|AB|=20$, $BC=12$. O retângulo é dividido em uma grade de $20 \times 12$ quadrados unitários. Os seguintes movimentos são permitidos no tabuleiros: pode-se mover de um quadrado para outro apenas se a distância entre os centros dos dois quadrados é $\sqrt{r}$. A tarefa é encontrar uma sequência de movimentos conduzindo do quadrado com $A$ como vértice ao quadrado que possui $B$ como vértice.

(a) Mostre que a tarefa não pode ser feita se $r$ é divisível por $2$ ou $3$.

(b) Prove que a tarefa é possível se $r=73$.

(c) A tarefa pode ser feita quando $r=97$?

Solução:

(a) Para ajudar o nosso raciocínio, vamos colocar coordenadas. Considere $X$ o conjunto de todas as coordenadas $(x,y)$ com $x$ e $y$ inteiros tais que $0 \leq x \leq 19$ e $0 \leq y \leq 11$. Queremos ir de $(0,0)$ a $(19,0)$.

Vale a pena estudar melhor como são os movimentos. Observe que cada movimento equivale a andar $a$ unidades na horizontal e $b$ na vertical. Por isso, cada movimento transforma $(x,y)$ em $(x+a,y+b)$. Mas o enunciado nos diz que só podemos fazer o movimento se a distância entre os pontos for $\sqrt{r}$. E agora, podemos calcular a distância entre $(x,y)$ e $(x+a,y+b)$? Sim ela é

$\sqrt{(x+a-x)^2+(y+b-y)^2}=\sqrt{a^2+b^2}$.

Você pode saber um pouco mais sobre isso aqui. Precisamos que

$\sqrt{a^2+b^2}=\sqrt{r} \Leftrightarrow a^2+b^2=r.$

Agora sim podemos analisar cada caso separadamente.

(i) $r$ é par

Aqui $a^2$ e $b^2$ possuem a mesma paridade, de onde segue que $a$ e $b$ também possuem. Conseguimos usar isso para encontrar alguma invariante? Sim: a paridade da soma das coordenadas não muda com os movimentos. De fato, ela passa de $x + y$ para $x+y+(a+b)$ e paridade de um número não muda se somarmos um número par (no caso $a+b$ é par, pois $a$ e $b$ possuem mesma paridade).

Logo é impossível neste caso ir de $(0,0)$ a $(19,0)$ já que a soma das coordenadas do primeiro é par e a do segundo é ímpar.

(ii) $r$ é múltiplo de $3$

Aqui também vale que $a^2+b^2=r$. Podemos dizer algo sobre a divisibilidade de $a$ ou $b$ por $3$? Sim: podemos mostrar que $a$ e $b$ são ambos múltiplos de $3$. Suponha um deles não seja. Sem perda de generalidade, podemos supor que $a$ não é múltiplo de $3$. Desta forma, $a \equiv 1 \text{ ou }2 \pmod{3}$ e assim $a^2 \equiv 1 \pmod{3}$. Além disso, $b^2 \equiv 0 \text{ ou }1 \pmod{3}$. Por isso, $a^2+b^2 \equiv 1 \text{ ou }2 \pmod{3}$. Contradição. Desta forma, $a$ e $b$ devem ser múltiplos de $3$.

Por isso, em cada movimento, estamos somando às coordenadas múltiplos de $3$ e assim os seus restos na divisão por $3$ não se altera. Desta forma, não podemos sair de $(0,0)$ e chegar em $(19,0)$.

(b) Se $r=73$, então $a^2+b^2=73$. Vamos procurar as soluções inteiras positivas dessa equação (depois conseguimos achar as soluções inteiras negativas já que $(a,b)$ é solução se, e somente se, $(\pm a, \pm b)$ também é). Repare que

$a^2 \leq a^2+b^2=73 \Rightarrow a \leq 8.$

Podemos testar $a=1,2,3,\cdots,8$. As únicas soluções que iremos encontrar aqui são $(3,8)$ e $(8,3)$. Portanto, as possíveis transformações para a coordenada $(x,y)$ são $(x\pm 3, y\pm 8)$ e $(x \pm 8, y \pm 3)$. Uma possível solução usando essas transformações é:

(c) Aqui $a^2+b^2=97$. Vamos procurar as soluções inteiras positivas desta equação

$a^2 \leq a^2+b^2=97 \Rightarrow a \leq 9.$

Ao testarmos $a=1,2,\cdots,9$ encontraremos as soluções $(4,9)$ e $(9,4)$. Assim os possíveis movimentos são aquele que transformam $(x,y)$ em $(x \pm 4,y\pm 9)$ ou $(x \pm 9, y \pm 4)$.

Se fizermos alguns movimentos, podemos perceber que as peças ficam em certas regiões específicas. Considere $Y$ o conjunto das coordenadas $(x,y)$ tais que $4 \leq y \leq 7$ e $Z$ as coordenadas de $X$ que não estão em $Y$. Onde estão os pontos depois de cada umas das transformações?

Vamos começar analisando os movimentos que transformam $(x,y)$ em $(x \pm 9, y \pm 4)$. Ao somarmos $4$ ou subtrairmos $4$ de um número menor ou igual a $4$ e menor ou igual a $7$, iremos obter um número fora desse intervalo. Desta forma, essa transformação leva pontos de $Y$ em $Z$. E quanto aos pontos de $Z$? Será que eles vão para $Y$? Repare que se um ponto $(x,y)$ está em $Z$, então $1 \leq y \leq 3$ (e nesse caso só podemos somar $4$ às coordenadas de $y$ levando o ponto para $Y$) ou $8 \leq y \leq 11$ (aqui só podemos subtrair $4$ de $y$ levando o ponto para $Y$ também). Ou seja, esse tipo de transformação leva pontos de $Z$ para $Y$.

Já os movimentos da forma $(x \pm 4,y\pm 9)$ e só podem ser aplicados em pontos de $Z$ (levando os pontos de $Z$ para $Z$).

Para sabermos onde um ponto de $Z$ (que no caso é o ponto inicial $(0,0)$) vai parar após vários movimentos, devemos saber a paridade da quantidade de movimentos que levam $(x,y)$ em $(x \pm 9, y \pm 4)$ (já que após uma quantidade par deles, paramos em $Z$ e após uma quantidade ímpar deles, paramos em $Y$). Como esse movimento muda a paridade de $x$ e devemos sair de $(0,0)$ e chegar a $(19,0)$, esse tipo de movimento será aplicado uma quantidade ímpar de vezes.

Mas isso fará com que cheguemos em $Y$ e $(19,0)$ não faz parte desse conjunto. Logo não podemos cumprir as condições do enunciado para $r=97$.

Exemplo (IMO 1993)

Em um tabuleiro de xadrez infinito, um jogo é jogado conforme as regras a seguir. No começo, $n^2$ peças são colocadas no tabuleiro em um bloco $n$ por $n$ de quadrados adjacentes, uma peça em cada quadrado. Um movimento no jogo é um pulo na direção horizontal ou na vertical sobre um quadrado adjacente ocupado para um quadrado desocupado imediatamente depois. A peça que foi pulada é removida.

Encontre todos os valores de $n$ para os quais o jogo pode terminar com apenas uma peça sobrando no tabuleiro.

Solução: Ao invés de mexer com $n$ casas de uma vez, vale a pena começarmos com casos pequenos para ver se conseguimos alguma ideia interessante. No caso $n=1$ não conseguimos fazer movimento, afinal precisamos de duas pedras para fazer um movimento. Desta forma, neste caso, irá sobrar somente uma peça e esse valor de $n$ satisfaz as condições do enunciado.

E quanto a $n=2$? Existe uma sequência de movimentos possível:

Após mexer um pouco no caso $n = 3$, ele pode parecer impossível. Mas existe um movimento interessante que podemos perceber no meio do processo:

Olha só que legal: sempre que tivermos três peças em um tabuleiro $1 \times 3$ e uma peça do lado, podemos "limpar" esse tabuleiro $1 \times 3$ e voltar a peça para a posição original. Observe que isso também vale para um tabuleiro $3\times1$. Será que isso nos ajuda a resolver o problema para o caso $n = 4$?

Vamos dividir o tabuleiro $4 \times 4$ em cinco subtabuleiros $1 \times 3$ e $3\times1$ conforme a figura anterior. Será que conseguimos "limpar" todos esses cinco subtabuleiros? Para facilitar nossa escrita, vamos chamar a peça do quadradinho da linha $i$ e coluna $j$ de $(i,j)$. Podemos

• usar a peça $(1,3)$ para limpar o 1° subtabuleiro;
• depois usar a peça $(2,1)$para limpar o 2º subtabuleiro;
• usar a peça $(2,2)$ para limpar o 3º subtabuleiro;
• usar a peça $(2,3)$ para limpar o 4° subtabuleiro;
• usar a peça $(4,4)$ para limpar o 5° subtabuleiro.

Após isso teremos apenas a peça $(4,4)$, ou seja, o caso $n = 4$ satisfaz as condições do enunciado. Será que essa ideia nos ajuda em casos mais gerais? Sim: para $n \geq 4$, podemos reduzir um quadrado $(n+3) \times (n+3)$ para um $n \times n$ usando a mesma ideia.

Desta forma, se tivermos um tabuleiro $(3k+1) \times (3k+1)$, podemos reduzi-lo para um $(3k+1-3) \times (3k+1-3)$ e assim por diante até chegar em um $1 \times 1$. Ou seja, todo $n$ que possui resto $1$ na divisão por $3$ satisfaz as condições do enunciado. De modo análogo, podemos mostrar que o mesmo vale para todo $n$ que possui resto $2$ na divisão por $3$.

Resta verificarmos o que acontece com os números que são múltiplos de $3$. Suponha, por absurdo, que podemos terminar o jogo em um tabuleiro $(3k) \times (3k)$. Sejam $S_0$, $S_1$ e $S_2$ o número de peças nos quadrados $(i,j)$ tais que $i+j$ deixe restos $0$, $1$ e $2$ na divisão por $3$. Vale a pena entendermos quanto essas quantidades valem inicialmente e o que ocorre com elas em cada movimento até encontrar uma invariante.

Vamos calcular $S_0$. Observe que $i+j$ deixa resto $0$ na divisão por $3$ nos seguintes casos:

• $i$ e $j$ deixam resto $0$;
• $i$ deixa resto $1$ e $j$ deixa resto $2$;
• $i$ deixa resto $2$ e $j$ deixa resto $1$.

Agora precisamos saber quantos números deixam restos $0$, $1$ e $2$ na divisão por $3$. Os números que deixam resto $0$ na divisão por $3$ são $3,6,9,\cdots,3k$, ou seja, existem $k$ deles. Já também existem $k$ números que deixam resto $1$. Eles são $1,4,7,\cdots,3k-2$. Finalmente os números que deixam resto $2$ na divisão por $3$ são $2,5,8,\cdots,3k-1$.

Com isso, as peças $(i,j)$ tais que $i+j$deixa resto $0$ na divisão por $3$ são

$\underbrace{k \cdot k}_{i\text{ e }j \text{ deixam resto }0}+\underbrace{k \cdot k}_{i \text{ deixa resto }1 \text{ e }j \text{ deixa resto }2}+\underbrace{k \cdot k}_{i \text{ deixa resto }2 \text{ e }j \text{ deixa resto }1}=3k^2.$

Desta maneira, $S_0=3k^2$. Analogamente, $S_1=S_2=3k^2$. E ocorre com esses valores em cada movimento? Observe como é cada tipo de movimento:

Vamos preencher os quadrados com os números $i+j$ (soma da linha com a coluna). Em qualquer um dos quatro movimentos possíveis estaremos mexendo com três valores consecutivos para $i+j$ (e assim os seus restos serão, em alguma ordem, $0$, $1$ e $2$). Observe que dois deles somem e um deles aparece. Por isso, dois dos números $S_0$, $S_1$ e $S_2$ diminuem uma unidade e o outro irá aumentar uma unidade.

Mais ainda, cada movimento muda a paridade de cada um dos números $S_0$, $S_1$ e $S_2$. Mas observe que esses números começam com a mesma paridade. Depois de cada movimento, eles continuarão tendo a mesma paridade. Mas, para sobrar uma peça, deveríamos ter no final um dos valores igual a $1$ e os outros dois iguais a zero. Isso não pode acontecer. Logo não podemos terminar com uma peça quando $n$ é múltiplo de $3$. Finalmente, o jogo termina se, e somente se, $n$ é múltiplo de $3$.

Colorações

Colorir objetos da figura te ajuda a separar. É como se você separasse os objetos para diferenciá-los.

Exemplo (Cone Sul 2000)

No plano cartesiano, considere os pontos de coordenadas inteiras. Uma operação consiste em:

Escolher um destes pontos e realizar uma rotação de $90^\circ$ no sentido anti-horário, com centro neste ponto.

É possível, através de uma sequência dessas operações, levar o triângulo de vértices $(0,0),(1,0)$ e $(0, 1)$ no triângulo de vértices $(0,0),(1,0)$ e $(1,1)$?

Solução: Considere duas cores $A$ e $B$. Pinte $(0,0)$ de $A$ e depois pinte todos os outros pontos de coordenadas inteiras com as cores $A$ e $B$, alternadamente, conforme a figura a seguir.

Vamos entender melhor como foi feita a pintura. Pintamos um ponto $(a,b)$ com a cor $A$ se, e somente se, $a$ e $b$ possuem a mesma paridade (isto é, $a+b$ é par), enquanto $(a,b)$ será pintado de $B$ se, e somente se, $a$ e $b$ possuem paridades diferentes (isto é, $a+b$ é ímpar).

Mostremos que a cor de um ponto é invariante de fazermos a operação descrita no enunciado. A imagem da rotação de $90^\circ$ no sentido anti-horário de $P=(x,y)$ em torno de $(a,b)$ será $P'=(a+b-y,x-a+b)$. Vejamos que $P$ e $P'$ possuem mesma paridade, para qualquer que seja $(a,b)$.

A soma das coordenadas de $P$ é $x + y$ enquanto a soma das de $P'$ é $a+b-y+x-a+b=2b+x-y$. Estes dois números possuem a mesma paridade, pois sua soma é par. Com efeito, $(x+y)+(2b+x-y)=2(b+x)$.

Desta forma, a rotação não altera a cor de um ponto. Assim, as cores do vértices do triângulo não alteram com a rotação. Observe que o primeiro triângulo possui um ponto da cor $A$ e dois da cor $B$, enquanto o segundo possui dois da cor $A$ e um da cor $B$. Com isso é impossível transformarmos o primeiro triângulo no segundo.

Exemplo (Cone Sul 2009)

Ana e Beto jogam em um tabuleiro de $11$ linhas e $9$ colunas. Primeiro Ana divide o tabuleiro em $33$ zonas. Cada zona é formada por $3$ casas adjacentes alinhadas vertical ou horizontalmente, como mostra a figura.

Depois, Beto escreve em cada casa um dos números $0,1,2,3,4,5$, de modo que a soma dos números de cada zona seja igual a $5$. Beto ganha se a soma dos números escritos em cada uma das $9$ colunas do tabuleiro é um número primo; caso contrário, Ana ganha. Demonstre que Beto tem uma estratégia vencedora.

Solução: Vamos colorir o tabuleiro com três cores $A, B$ e $C$ conforme a figura a seguir.

Foto retirada do site https://www.omaforos.com.ar/viewtopic.php?f=16&t=2361.

Aqui aparece a nossa invariante: não importa como Ana coloca as peças, cada uma terá uma casa da cor $A$, uma da cor $B$ e uma da cor $C$. Como Beto agora pode escrever os números de tal forma que em cada zona a soma é $5$? Basta que ele escreva $1$ nas casas de cores $A$ e $B$ e $3$ nas casas de cor $C$. Assim a soma dos números de cada zona será $1+1+3=5$.

Enquanto a soma das colunas? Observe que em todas elas, duas das cores aparecem $4$ vezes, enquanto uma delas aparece $3$ vezes. Se a cor que aparece $3$ vezes for $A$ ou $B$, então a soma dos números desta coluna será $3 \cdot 1 + 4 \cdot 1 + 4 \cdot 3 = 19$. Já se a cor que aparece $3$ vezes for $C$, então a soma dos números desta coluna será $4 \cdot 1 + 4 \cdot 1 + 3 \cdot 3 = 17$. Logo, Beto possui a estratégia vencedora.

Exemplo (Cone Sul 2014)

Em uma lousa, estão escritos os números inteiros de $1$ a $2014$, inclusive. A operação válida é escolher dois números $a$ e $b$, apagar eles e no seu lugar escrever o mínimo múltiplo comum do par $(a,b)$ e o máximo divisor comum do par $(a,b)$.

Mostre que, sem importar a quantidade de operações que sejam realizadas, a soma dos números que ficam escritos na lousa é sempre maior que $2014 \cdot \sqrt[2014]{2014!}$.

Solução: (É necessário saber Desigualdades para ler esta solução) Como

$ab=\operatorname{mdc}(a,b) \cdot \operatorname{mmc}(a,b)$,

segue que o produto dos números do quadro é invariante.

Sejam $a_1,a_2,\cdots,a_{2014}$ os números após uma sequência qualquer de operações. Pela Desigualdade das Médias,

$\frac{a_1+a_2+\cdots+a_{2014}}{2014}\geq \sqrt[2014]{a_1 a_2 \cdots a_{2014}} \Leftrightarrow \frac{a_1+a_2+\cdots+a_{2014}}{2014}\geq \sqrt[2014]{1 \cdot 2 \cdots 2014} \Leftrightarrow$

$\Leftrightarrow a_1+a_2\cdots +a_{2014} \geq 2014 \cdot \sqrt[2014]{2014!}.$

Monovariantes

Algo é chamado de monovariante se nunca aumenta ou nunca diminui.

Exemplo (Cone Sul 2011)

Em uma lousa estão escritos os números inteiros positivos de $1$ até $4^{n}$ inclusive. Em cada momento, Pedro apaga dois números da lousa, $a$ e $b$, e escreve o número $\frac{ab}{\sqrt{2a^2+2b^2}}$. Pedro repete o procedimento até que sobre apenas um número. Demonstrar que este número será menor que ${\frac{1}{n}}$, sem importar quais números Pedro escolha em cada momento.

Solução: (É necessário saber Desigualdades para ler esta solução) Existe um monovariante aqui: a soma dos inversos nunca diminui. Para isto basta provarmos que

$\frac{1}{a}+\frac{1}{b} \leq \frac{1}{\frac{ab}{\sqrt{2a^2+2b^2}}}. (*)$

A estratégia aqui é escrever de modo equivalente até que a gente tenha algo que saiba que é verdadeiro. A desigualdade anterior equivale a

$\frac{a+b}{ab} \leq \frac{\sqrt{2a^2+2b^2}}{ab} \Leftrightarrow a+b \leq \sqrt{2a^2+2b^2} \Leftrightarrow (a+b)^2 \leq 2a^2+2b^2 \Leftrightarrow a^2-2ab+b^2 \geq 0 \Leftrightarrow$

$(a-b)^2 \geq 0.$

Como esta desigualdade é verdade, segue que $(*)$ também o é. Se provarmos que, no começo, a soma dos inversos é maior do que $n$ e isso nunca diminui, logo, no final, a soma continuará sendo maior do que $n$. Em outras palavras, devemos provar que

$\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{4^n}>n.$

A estratégia aqui será dividir em várias partes aqui. Observe que

$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}>1.$

$\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}>\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}=4\cdot \frac{1}{8}= \frac{1}{2}.$

$\cdots$

$\frac{1}{2^k+1}+\frac{1}{2^k+2}+\cdots+\frac{1}{2^{k+1}}>\underbrace {\frac{1}{2^{k+1}}+\frac{1}{2^{k+1}}+\cdots+\frac{1}{2^{k+1}}}_{2^k \text{ parcelas}}=2^k.\frac{1}{2^{k+1}}=\frac{1}{2}.$

$\cdots$

$\frac{1}{2^{2n-1}+1}+\frac{1}{2^{2n-1}+2}+\cdots+\frac{1}{2^{2n}}>\underbrace {\frac{1}{2^{2n}}+\frac{1}{2^{2n}}+\cdots+\frac{1}{2^{2n}}}_{2^{2n-1} \text{ parcelas}}=2^{2n-1}.\frac{1}{2^{2n}}=\frac{1}{2}.$

Se somarmos estas $2n-1$ desigualdades e lembrarmos que $2^{2n}=4^n$,

$\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{4^n}>1+\underbrace{\frac{1}{2}+\cdots+\frac{1}{2}}_{2n-2 \text{ parcelas}}=n.$

Função Potencial

É uma função que associamos a alguma configuração do problema. Devemos encontrar alguma que nos dê uma invariância ou monovariância. Para isto, podemos forçar o resultado.

Exemplo (OBM 2001 - 3ª Fase - Nível 3)

Temos uma fileira longa de copos e $n$ pedras no copo central (copo $0$). Os seguintes movimentos são permitidos:

Movimento do tipo $A$

Se há pelo menos uma pedra no copo $i$ e pelo menos uma no copo $i+1$ podemos fazer uma pedra que está no copo $i+1$ pular para o copo $i-1$ eliminando uma pedra do copo $i$.

Movimento do tipo $B$

Se há pelo menos duas pedras no copo $i$ podemos pular uma para o copo $i+2$ e outra para o copo $i-1$.

Demonstre o seguinte fato: fazendo os seguintes movimentos do tipo $A$ ou $B$ durante um tempo suficientemente longo sempre chegaremos a uma configuração a partir da qual não é mais possível fazer nenhum desses dois tipos de movimento. Além disso essa configuração final não depende da escolha de movimentos durante o processo.

Solução: Comecemos provando a primeira parte do enunciado: que não é possível fazer nenhuma jogada depois de um certo tempo. Vamos atribuir um tipo de função potencial que faça as energias diminuírem nos dois tipos de movimento. Para isto, tomaremos uma energia associada ao sistema da seguinte forma

$E=\sum_{x} q^{\operatorname{pos}(x)},$

onde $\operatorname{pos}(x)$ é a posição da pedra $x$ e $q$ é uma valor positivo que iremos determinar que faz as energias diminuírem. Vamos entender o que acontece com a energia quando ocorre o movimento $A$. Nele, sumirão as bolas das posições $p$ e $p+1$ e aparecerá uma na posição $p-1$.

Se a energia após o movimento $A$ for $E'$ e a antes dele for $E$, então

$E'=E-q^p-q^{p+1}+q^{p-1}.$

Esta energia diminui se, e somente se,

$-q^p-q^{p+1}+q^{p-1}<0.$

Se dividirmos ambos os lados por $q^{p-1}$,

$-q-q^2+1<0 \Leftrightarrow q^2+q-1>0.(*)$

Vejamos o que acontece quando fazemos um movimento $B$.

Duas bolas na posição $p$ sumirão e aparecerão uma na posição $p-1$ e outra na posição $p+2$. Assim a energia nova será

$E'=E-2q^p+q^{p-1}+q^{p+2}.$

A energia aqui diminui se, e somente se,

$-2q^p+q^{p-1}+q^{p+2}<0.$

Se dividirmos ambos os lados por $q^{p-1}$,

$-2q+1+q^3<0.(**)$

Basta tomarmos $q$ que satisfaça $(*)$ e $(**)$. Por exemplo $q=\frac{3}{4}$. Aliás, qualquer $q$ tal que $\frac{\sqrt{5}-1}{2}<q<1$. Para este valor, a energia sempre diminui, ou seja, ela será um monovariante.

Vejamos que as pedras não podem ir tão à esquerda assim. Considere $p$ uma posição tal que $\left( \frac{3}{4} \right)^p>E_0$, onde $E_0$ é a energia inicial. Como a energia, a cada movimento, sempre diminui, segue que para quaisquer movimentos que se faça, as pedras nunca ficarão em alguma posição menor ou igual a $p$ (de fato, lembre-se que se $x \leq p$, então $\left( \frac{3}{4} \right)^x \geq \left( \frac{3}{4} \right)^p$). Ou seja, existe uma "barreira à esquerda".

Vamos usar isto para provar por indução no número $n$ de pedras que é impossível realizar uma sequência infinita de movimentos. Comecemos com o caso $n=1$. Como precisamos de pelo menos duas pedras para fazer algum dos movimentos, com $1$ é impossível fazer algum movimento, ou seja, é impossível fazer uma quantidade infinita de movimentos.

Façamos agora o passo indutivo. Consideremos $n$ pedras. Sabemos que a posição da pedra mais à esquerda nunca aumenta. De fato, nenhum dos movimento $A$ ou $B$ fará com que a pedra mais a esquerda esteja agora mais à direita. Como existe uma "barreira à esquerda", a partir de um certo ponto, a pedra à esquerda também não será mais movimentada e só restará as outras $n-1$ pedras. Por hipótese de indução, é impossível realizar infinitos movimentos com elas. Isto prova a primeira parte do problema.

Vamos agora provar a segunda parte do problema, ou seja, que a configuração inicial não depende da escolha de movimentos durante o processo. Para isto, vamos supor, por absurdo, que existam duas configurações $A$ e $B$ distintas (entenderemos aqui as configurações como conjuntos de pedras). No final, provaremos que elas são iguais.

Já sabemos que dada uma configuração, independente dos movimentos, existirá algum momento em que é impossível se mover. Vamos chamar isto de configuração parada.

Vejamos se conseguimos fazer uma energia que seja invariante a cada processo. Consideraremos $X_n$ a energia do copo $n$ e $I$ a energia total do sistema que é dada pela soma das energias de cada copo.

Lembre-se que no movimento $A$, sumirão as bolas das posições $p$ e $p+1$ e aparecerá uma na posição $p-1$. Assim, a energia nova $I'$ será

$I'=I-X_p-X_{p+1}+X_{p-1}.$

A energia irá continuar a mesma se, e somente se,

$-X_p-X_{p+1}+X_{p-1} =0 \Leftrightarrow X_{p-1}=X_p+X_{p+1}.(***)$

Já no movimento $B$, duas bolas na posição $p$ sumirão e aparecerão uma na posição $p-1$ e outra na posição $p+2$. Com isso,

$I'=I-2X_p+X_{p-1}+X_{p+2}.$

A energia será invariante se, e somente se,

$-2X_p+X_{p-1}+X_{p+2}=0 \Leftrightarrow X_{p-1}+X_{p+2}=2X_p.(****)$

Quais valores devemos escolher para $X_{p}$ que satisfaçam $(***)$ e $(****)$? Observe que parece uma sequência de Fibonacci "ao contrário", já que $F_{p+1}=F_p+F_{p-1}$ e $F_{p+2}=2F_p+F_{p-1}$. Como faremos para reajustar isto?

Tomemos $k'$ a posição mais à direita das configurações $A$ e $B$ e $k'=k+2$. Tomaremos $X_p=F_{k-p}$. Vejamos que esta escolha irá satisfazer $(***)$ e $(****)$. Comecemos com a primeira. Se combinarmos a definição de $X_{p}$ com a definição da sequência de Fibonacci,

$X_p+X_{p+1}=F_{k-p}+F_{k-(p+1)}=F_{k-p}+F_{k-p-1}=F_{k-p+1}=F_{k-(p-1)}=X_{p-1}.$

E quanto a $(****)$? Se usarmos a definição de $X_{p}$ e a definição da sequência de Fibonacci primeiro para $F_{k-p+1}$ e depois para $F_{k-p-1}+F_{k-p-2}$,

$X_{p-1}+X_{p+2}=F_{k-(p-1)}+F_{k-(p+2)}=F_{k-p+1}+F_{k-p-2}=F_{k-p}+F_{k-p-1}+F_{k-p-2}=$

$=F_{k-p}+F_{k-p}=2F_{k-p}=2X_p.$

Desta forma, esta energia $I$ é invariante. Consideremos as energias $I_A$ e $I_B$ das posições finais $A$ e $B$. Como esta energia é a mesma do começo, segue que $I_A=I_B$. Vamos mostrar que $A = B$. Para fazermos isto, usaremos um algoritmo. Ele consistirá no seguinte: tomaremos $x$ e $y$ as pedras mais à esquerda de $A$ e $B$, respectivamente. Depois mostraremos que $\operatorname{pos}(x)=\operatorname{pos}(y)$. Daí bastará repetir o processo para $A-\{x\}$ e $B-\{y\}$. O processo deverá ser feito até terminar.

Algoritmo:

(1) Sejam $x$ e $y$ as pedras mais à esquerda de $A$ e $B$, respectivamente. Provaremos que $\operatorname{pos}(x)=\operatorname{pos}(y)$. Vamos supor, por absurdo, que eles não possuem posições iguais. Podemos dizer, sem perda de generalidade, que $\operatorname{pos}(x)>\operatorname{pos}(y)$. Provaremos que, neste caso, $I_A<I_B$. Comecemos observando que

$I_A=\sum_{t \in A} F_{k-\operatorname{pos}(t)}.$

Mostraremos que o maior valor que $I_A$ pode ter é menor do que $I_B$. Mas qual o valor máximo de $I_A$? Observemos algumas características de $A$ para descobrir.

Como $A$ é uma configuração parada, não podemos ter duas pedras em posições consecutivas (de fato, se tivéssemos, poderíamos fazer o movimento $A$). Além disso, não podemos ter duas pedras no mesmo copo (pois se isto ocorresse, daria para fazer o movimento $B$).

Ou seja, para a energia ser máxima, devemos ter copos preenchidos de dois em dois. E isto vai depender da paridade de $k$ e $\operatorname{pos}(x)$. Se $k$ e $\operatorname{pos}(x)$ tiverem a mesma paridade, então $I_A$ será máxima quando todos os copos das posições $\operatorname{pos}(x),\operatorname{pos}(x)+2,\operatorname{pos}(x)+4,\cdots,k'=k-2$ tiverem pedras. Assim

$I_A \leq F_{k-\operatorname{pos}(x)}+F_{k-(\operatorname{pos}(x)+2)}+F_{k-(\operatorname{pos}(x)+4)}+\cdots+F_{k-(k-2)}=$

$=F_{k-\operatorname{pos}(x)}+F_{k-\operatorname{pos}(x)-2}+F_{k-\operatorname{pos}(x)-4}+\cdots+F_{2}.$

Por uma propriedade da sequência de Fibonacci, esta última expressão é igual a

$F_{k-\operatorname{pos}(x)+1}-1.$

Já se $k$ e $\operatorname{pos}(x)$ tiverem paridades diferentes, então $I_A$ será máxima quando todos os copos das posições $\operatorname{pos}(x),\operatorname{pos}(x)+2,\operatorname{pos}(x)+4,\cdots,k'-1=k-3$ tiverem pedras.Assim

$I_A \leq F_{k-\operatorname{pos}(x)}+F_{k-(\operatorname{pos}(x)+2)}+F_{k-(\operatorname{pos}(x)+4)}+\cdots+F_{k-(k-3)}=$

$=F_{k-\operatorname{pos}(x)}+F_{k-\operatorname{pos}(x)-2}+F_{k-\operatorname{pos}(x)-4}+\cdots+F_{3}.$

Por uma propriedade da sequência de Fibonacci, esta última expressão é igual a

$F_{k-\operatorname{pos}(x)+1}-1.$

Desta forma, se usarmos o que concluimos em ambos os casos, além de $\operatorname{pos}(x)-1 \geq \operatorname{pos}(y)$ e que a configuração $B$ possui pelo menos a pedra $y$,

$I_A \leq F_{k-\operatorname{pos}(x)+1}-1<F_{k-\operatorname{pos}(x)+1} \leq F_{k-\operatorname{pos}(y)} \leq I_B.$

Absurdo. Logo $\operatorname{pos}(x)=\operatorname{pos}(y)$.

(2) Volte para o passo 1, porém ao invés de considerar $A$ e $B$, considere $A-\{x\}$ e $B-\{y\}$.

O algoritmo deve ser repetido até as configurações acabarem. Provaremos daí que $A$ e $B$ são a mesma configuração, ou seja, a configuração final não depende da escolha de movimentos.

Lugares Para Estudar

• Invariantes I (POTI - Nível 2)
• Invariantes II (POTI - Nível 2)
• Problemas Resolvidos: Invariantes I (POTI - Nível 2)
• Problemas Resolvidos: Invariantes II (POTI - Nível 2)
• A aula do POTI - Nível 3: Arquivo:Aula 06 - Invariantes e Monovariantes.pdf
• A aula da Semana Olímpica de 2007: Invariantes (Eduardo Poço).
• A aula da Semana Olímpica de 2010: Nem Tudo Mudou... (Ramon Moreira Nunes)
• A aula da Semana Olímpica de 2012: Invariantes – Como Algo que não Muda Mudará Sua Vida (Davi Lopes)
• A aula da Semana Olímpica de 2016: Paridade, Jogos e Invariantes (Samuel Feitosa)
• A aula da Semana Olímpica de 2018: Problemas Diversos de Invariantes e Semi-invariantes (George Lucas)
• O artigo da Revisa Eureka 14: O Princípio da Invariância (Marcelo Rufino de Oliveira).

Vídeos

• Invariantes e Restos (POTI - Nível 2)
• Invariantes e Monovariantes (POTI - Nível 3)
• Invariantes I (POTI 2017)
• Invariantes II (POTI 2017)
• Semi-invariantes (POTI 2017)

Bibliografia

• D. Djukic, V. Jankovic, I. Matic, N. Petrovic : The IMO Compendium 1959-2009, Springer, 2011.