FANDOM


É 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.

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

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)Editar

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.