Olimpíada Gaúcha de Matemática

Semana 1, Nível 3

Considere um tabuleiro quadriculado infinito cujos centros de suas casas são os pontos de coordenadas inteiras. A casa central é a casa cujo centro é (0, 0), e as diagonais principais aquelas casas cujo centro tem coordenadas (i, i) ou (i, -i), conforme está destacado na figura:

Cada casa do tabuleiro possui oito casas vizinhas, aquelas que possuem em comum um lado ou um vértice.

Inicialmente, existe uma ameba na casa central e todas as outras casas estão vazias. A partir daí, em cada turno (unidade de tempo), todas as amebas existentes no tabuleiro se reproduzem. A reprodução de uma ameba é feita da seguinte forma: ela continua viva em sua casa e dá origem a outras 8 (oito) amebas, cada uma das quais em uma de suas casas vizinhas. Em cada casa do tabuleiro, podem existir qualquer número de amebas e uma ameba nunca morre. Nas três figuras abaixo, estão indicadas, nas casas, a quantidade de amebas presentes nelas. São mostrados os três primeiros turnos:

Pede-se: calcular o número de amebas em cada turno e provar que a quantidade de amebas na casa central e nas casas das diagonais é sempre um quadrado perfeito.

Solução de
Platão Gonçalves Terra Neto, 15 anos, Escola Liberato de Novo Hamburgo, RS, postada em 6/11/03

(a) Seja a(k) a quantia de amebas no k-ésimo turno. Vemos que no próximo turno, todas as amebas do turno anterior transformam-se em outras 8, portanto a(k+1)=8.a(k)+a(k)=9.a(k). A fórmula de a(k) parece com 9^(k-1), podemos demonstrá-la por indução, notanto que a(1) = 1 = 9^(1-1) e que se a(k) = 9^(k-1) então a(k+1) = 9.a(k) = 9.9^(k-1) = 9^k.

(b) Há bastante simetria no tabuleiro. Se transpusermos o tabuleiro, trocando linhas por colunas, ainda teremos o mesmo tabuleiro, e se invertermos a ordem das linhas ou das colunas ainda teremos o mesmo tabuleiro.

Para o k-ésimo turno podemos associar a(k, (m,n)) à quantidade de amebas na casa (m,n). O relevante, no turno n, são aquelas casa cujas coordenadas m e n de (m,n) estão entre -k e k, pois as demais casas são todas formadas por zeros.

Conjectura. A quantidade de amebas em cada casa é igual ao produto da quantidade de amebas da última casa não vazia acima (ou abaixo, pela simetria) e da última casa não vazia à esquerda (ou direita, pela simetria). Esta conjectura pode ser escrita algebricamente como a(k, (m,n)) = a(k, (m, k-1)) . a(k, (k-1,n).

Esta conjectura pode ser confirmada para os três primeiros turnos, de modo mecânico. Podemos demonstrar esta propriedade, então, por indução. Para as casas que estão na borda do tabuleiro, esta propriedade sempre vale, pois as casas das diagonais valem sempre 1. Escolhamos uma casa (m,n) fora da bora, em um turno k. Para simplificar a notação, escrevemos as 8 casa vizinhas em um quadro, sem tanta precisão na notação:

a(m-1).a(n+1)	a(m).a(n+1)	a(m+1).a(n+1)
a(m-1).a(n)	a(m).a(n)	a(m+1).a(n)
a(m-1).a(n-1)	a(m).a(n-1)	a(m+1).a(n-1)

Cada a(i) está representando a(k, (k-1,i)) ou a(k, (i,k-1)), que é o mesmo pela simetria. No próximo turno, a casa (m,n) terá a quantidade de amebas igual à soma das amebas nessas nove casas. Se somarmos, e fizermos uma fatoração, teremos ( a(n-1)+a(n)+a(n+1) ).( a(m-1)+a(m)+a(m+1) ). Na linha mais de cima com amebas, a casa (m, k) terá exatamente a(m-1)+a(m)+a(m+1) amebas no próximo turno, e os mesmo vale para a casa (k, n). O que demonstra a propriedade por indução.

Para finalizar, reparamos que a(k, (i,i) ) = a(k, (i, -i)) = a(i)^2 é um quadrado perfeito.

"Nunca desencorage alguém que continuamente faz progressos, não importa quanto lentos eles sejam."
Platão, filósofo Grego