Problema 5 de IMO 2010 resolvido colaborativamente no projecto Mini-Polymath2

Decorreu recentemente no The polymath blog e sob a organização de Terence Tao, a resolução conjunta do Problema 5 das Olimpíadas Internacionais de Matemática deste ano. Em vez do Problema 6, tradicionalmente o mais difícil, Terence Tao escolheu este por considerá-lo um pouco mais estimulante e interessante. A solução encontrada foi publicada no wiki Mini-Polymath2 criado para o efeito. Algum eventual leitor meu o melhor que fará será ler a discussão havida no The polymath blog, para ver como as ideias foram surgindo, ou ir directamente para a solução exposta no wiki.
Claro que o idioma em que tudo está escrito é o inglês. Mas o enunciado existe também em português no IMO 2010.

« Problema 5 .  Em cada uma de seis caixas B_{1}, B_{2}, B_{3}, B_{4}, B_{5}, B_{6} há inicialmente só uma moeda. Dois tipos de operações são possíveis:

Tipo 1: Escolher uma caixa não vazia B_{j}, com 1\leq j\leq 5. Retirar uma moeda de B_{j} e adicionar duas moedas a B_{j+1}.

Tipo 2: Escolher uma caixa não vazia B_{k}, com 1\leq k\leq 4. Retirar uma moeda de B_{k} e trocar os conteúdos das caixas (possivelmente vazias) B_{k+1} e B_{k+2}.

Determine se existe uma sucessão finita destas operações que deixa as caixas B_{1}, B_{2}, B_{3}, B_{4}, B_{5} vazias e a caixa B_{6} com exactamente 2010^{2010^{2010}} moedas. (Observe que a^{b^{c}}=a^{(b^{c})}.) »

\bigskip

Vou adaptar e dar uma interpretação pessoal da solução que está descrita no wiki. Quaisquer erros são da minha
responsabilidade exclusiva. Digo desde já que a dificuldade deste problema me impediria de resolvê-lo durante uma prova como esta.

Uso a notação \left( a,b,c,d,e,f\right) para representar a distribuição de a,b,c,d,e e f moedas pelas caixas B_{1}, B_{2}, B_{3}, B_{4}, B_{5} e B_{6} (nos originais — blog e wiki — foram usados parênteses rectos).

O enunciado corresponde a descobrir, sendo possível, uma sucessão que parte da distribuição inicial \left( 1,1,1,1,1,1\right) e chega a \left( 0,0,0,0,0,T\right), com T=2010^{2010^{2010}}. Existe uma sequência finita de operações que verifica esta condição: a que passa sucessivamente pelas distribuições de moedas a seguir indicadas. A ideia chave é a colocação de um número X muito elevado de moedas na caixa B_{4}, no passo 3, seguida do seu esvaziamento parcial até se atingir o número adequado T/4, no passo 4. O número X é uma torre de potências, obtida pela resolução de um sub-problema, a que chamei abaixo propriedade Q (Move 4, no original).

\bigskip

1. A=\left( 1,1,1,1,1,1\right) \longrightarrow \longrightarrow B=\left( 0,0,140,0,0,0\right)

2. B\longrightarrow C=\left( 0,0,139,2,0,0\right)

3. C\longrightarrow \longrightarrow D=\left( 0,0,0,X,0,0\right) , em que X>>T/4

4. D\longrightarrow \longrightarrow E=\left( 0,0,0,T/4,0,0\right)

5. E\longrightarrow \longrightarrow F=\left( 0,0,0,0,0,T\right)

\bigskip

Notação:

1. a dupla seta representa uma sequência de operações do tipo 1 e/ou 2, uma seta única indica uma só operação.

2. as letras colocadas sobre as setas indicam as operações efectuadas.

Uma operação  do tipo 1, que aumenta o número de moedas total, é indicada por A; uma do tipo 2, que o diminui, por S. O número a seguir à letra indica a caixa de onde se retira a moeda. Aj é a operação do tipo 1 aplicada às caixas B_{j} e B_{j+1} e Sk é a do tipo 2 executada sobre as caixas B_{k},B_{k+1},B_{k+1}.

A repetição de uma mesma operação que retira moedas sempre da mesma caixa é indicada por um número antes da letra. Assim, 3A4 indica 3 operações A4.

A mesma operação, efectuada sobre caixas diferentes, é indicada pelos números das caixas, como em A1,2,3,4,5, que corresponde à  sequência A1\rightarrow A2\rightarrow A3\rightarrow A4\rightarrow A5.

Operações diferentes são separadas por uma vírgula: A3,3A4 significa uma operação A3 seguida de três A4.

\bigskip

Em grande parte a sequência 1 a 5 atrás indicada foi descoberta andando do fim para o princípio. Por exemplo, a passagem de E a F é obtida pela aplicação repetida da operação do tipo 1 às caixas B_{5} e B_{6}.

\bigskip

  • Passagem de E a F: retiram-se primeiro T/4 moedas de B_{4} ficando o dobro (T/2) em B_{5}, que se esvazia de seguida, colocando, no fim, T em B_{6}, ou seja o dobro das que estavam em B_{5}:

E=\left( 0,0,0,T/4,0,0\right) \overset{T/4A4}{\longrightarrow\longrightarrow }\left( 0,0,0,0,T/2,0\right)

\overset{T/2A5}{\longrightarrow\longrightarrow }F=\left( 0,0,0,0,0,T\right)

\bigskip

  • Passagem de D a E: retiram-se moedas de B_{4} até ficarem apenas T/4.

D=\left( 0,0,0,X,0,0\right) \overset{S4}{\longrightarrow }\left( 0,0,0,X-1,0,0\right) \overset{S4}{\longrightarrow }

\cdots \overset{S4}{\longrightarrow }E=\left( 0,0,0,T/4,0,0\right)

\bigskip

  • Passagem de A a B: é obtida pelas seguintes operações combinadas

A=\left( 1,1,1,1,1,1\right) \overset{A1,2,3,4,5}{\longrightarrow\longrightarrow }\left( 0,2,2,2,2,3\right)

\overset{A3,3A4}{\longrightarrow\longrightarrow }\left( 0,2,1,1,8,3\right) \overset{8A5}{\longrightarrow \longrightarrow }\left( 0,2,1,1,0,19\right)

\overset{S4,3,2}{\longrightarrow \longrightarrow }\left( 0,1,19,0,0,0\right) \overset{18A3}{\longrightarrow \longrightarrow }\left(0,1,1,36,0,0\right)

\overset{35A4,70A5}{\longrightarrow \longrightarrow }\left( 0,1,1,1,0,140\right) \overset{S4,3,2}{\longrightarrow \longrightarrow }\left( 0,0,140,0,0,0\right) =B

\bigskip

  • Passagem de B a C: operação A3

B=\left( 0,0,140,0,0,0\right) \overset{A3}{\longrightarrow }\left( 0,0,139,2,0,0\right) =C

\bigskip

  • Passagem de C a D:

C=\left( 0,0,139,2,0,0\right) \longrightarrow \longrightarrow D=\left( 0,0,0,X,0,0\right)

\bigskip

Antes de mostrar como se passa de C a D é necessário apresentar duas propriedades que passo a descrever.

\bigskip

Propriedade P: se \left( \ldots \left\vert x,y,z\right\vert\ldots \right) representar uma distribuição de moedas x,y,z por, respectivamente, 3 caixas B_{l}, B_{l+1}, B_{l+2} com l=1,2,3,4 é possível passar da distribuição P=\left( \ldots \left\vert a,0,0\right\vert \ldots \right) à P^{\prime }=\left( \ldots\left\vert 0,2^{a},0\right\vert \ldots \right) através da sequência de operações a seguir indicada.

\bigskip

Notação: os números entre parênteses a seguir às letras designam as posições relativas das caixas da esquerda para
a direita: (1) é a 1.ª caixa a contar da esquerda, (2) a 2.ª caixa, etc.

\left( \ldots \left\vert a,0,0\right\vert \ldots \right) \overset{A(1)}{\longrightarrow }\left( \ldots \left\vert a-1,2,0\right\vert \ldots \right)

\overset{2A(2)}{\longrightarrow \longrightarrow }\left( \ldots \left\vert a-1,0,2^{2}\right\vert \ldots \right) \overset{S(1)}{\longrightarrow }\left(\ldots \left\vert a-2,2^{2},0\right\vert \ldots \right)

\overset{2^{2}A(2)}{\longrightarrow \longrightarrow }\left( \ldots\left\vert a-2,0,2^{3}\right\vert \ldots \right) \overset{S(1)}{\longrightarrow }\left( \ldots \left\vert a-3,2^{3},0\right\vert \ldots\right)

\overset{2^{3}A(2)}{\longrightarrow \longrightarrow }\left( \ldots\left\vert a-3,0,2^{4}\right\vert \ldots \right) \overset{S(1)}{\longrightarrow }\cdots \overset{2^{a-2}A(2)}{\longrightarrow\longrightarrow }\left( \ldots \left\vert 2,0,2^{a-1}\right\vert \ldots\right)

\overset{S(1)}{\rightarrow }\left( \ldots \left\vert 1,2^{a-1},0\right\vert\ldots \right) \overset{2^{a-1}A(2)}{\longrightarrow \longrightarrow }\left(\ldots \left\vert 1,0,2^{a}\right\vert \ldots \right)

\overset{S(1)}{\rightarrow }\left( \ldots \left\vert 0,2^{a},0\right\vert\ldots \right)

ou abreviadamente

P=\left( \ldots \left\vert a,0,0\right\vert \ldots \right) \overset{P(1)}{\longrightarrow \longrightarrow }\left( \ldots \left\vert 0,2^{a},0\right\vert \ldots \right) =P^{\prime }

\bigskip

Propriedade Q: se \left( \ldots \left\vert p,q,r,s\right\vert\ldots \right) representar uma distribuição de moedas p,q,r,s por, respectivamente, 4 caixas B_{i},B_{i+1},B_{i+2}, B_{i+3} com i=1,2,3 é possível passar da distribuição Q=\left( \ldots\left\vert a,b,0,0\right\vert \ldots \right) à Q^{\prime }=\left(\ldots \left\vert a-1,2^{b},0,0\right\vert \ldots \right) por aplicação da propriedade P à caixa com b moedas, seguida de S(1):

Q=\left( \ldots \left\vert a,b,0,0\right\vert \ldots \right) \overset{P(2)}{\longrightarrow \longrightarrow }\left( \ldots \left\vert a,0,2^{b},0\right\vert \ldots \right)

\overset{S(1)}{\longrightarrow }\left( \ldots \left\vert a-1,2^{b},0,0\right\vert \ldots \right) =Q^{\prime }

ou condensadamente

Q=\left( \ldots \left\vert a,b,0,0\right\vert \ldots \right) \overset{Q(1)}{\longrightarrow \longrightarrow }\left( \ldots \left\vert a-1,2^{b},0,0\right\vert \ldots \right) =Q^{\prime }

\bigskip

A aplicação sucessiva da propriedade Q gera uma torre de potências. Por exemplo, aplicada 3 vezes, obtém-se:

Q\overset{Q(1)}{\longrightarrow \longrightarrow }Q^{\prime }=\left( \ldots\left\vert a-1,2^{b},0,0\right\vert \ldots \right)

\overset{Q(1)}{\longrightarrow \longrightarrow }\left( \ldots \left\vert a-2,2^{(2^{b})},0,0\right\vert \ldots \right)

\overset{Q(1)}{\longrightarrow \longrightarrow }\left( \ldots \left\vert a-3,2^{\left( 2^{(2^{b})}\right) },0,0\right\vert \ldots \right)

\bigskip

Passa-se de C a D, aplicando 139 vezes a propriedade Q às caixas B_{3}, B_{4}, B_{5} e B_{6}:

C=\left( 0,0,139,2,0,0\right) \overset{Q3}{\longrightarrow \longrightarrow }\left( 0,0,138,2^{2},0,0\right)

\overset{Q3}{\longrightarrow \longrightarrow}\left( 0,0,137,2^{2^{2}},0,0\right)\overset{Q3}{\longrightarrow \longrightarrow }\left( 0,0,137,2^{2^{2^{2}}},0,0\right)

\overset{Q3}{\longrightarrow\longrightarrow }\cdots \overset{Q3}{\longrightarrow \longrightarrow }\left( 0,0,0,X=\underset{140\text{ dois}}{\underbrace{2^{2^{2^{\cdot ^{\cdot^{\cdot ^{2}}}}}}}},0,0\right)

\bigskip

Como

2010^{2010^{2010}}=2^{\log _{2}\left( 2010\right) \times 2010^{2010}}

=2^{2^{2010\log _{2}\left( 2010\right) +\log _{2}\left( \log _{2}\left( 2010\right) \right) }}<2^{2^{2010\times 11+\log _{2}\left( 11\right) }}

<2^{2^{22114}}<2^{2^{2^{15}}}<\underset{6\text{ dois}}{\underbrace{2^{2^{2^{2^{2^{2}}}}}}}

fica justificada a majoração requerida no passo 3 (de C para D):

\dfrac{1}{4}T=\dfrac{1}{4}2010^{2010^{2010}}<\dfrac{1}{4}\underset{6\text{ dois}}{\underbrace{2^{2^{2^{2^{2^{2}}}}}}}<X=\underset{140\text{ dois}}{\underbrace{2^{2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}}}}

* * *

   Adenda de 21-07-2010: Comunicado da SPM de 14-07-2010

 « Portugal ganha medalha de bronze nas Olimpíadas Internacionais de Matemática
Aluno do 9º ano conquista Menção Honrosa

A equipa que este ano representou Portugal nas Olimpíadas Internacionais de Matemática (IMO) é uma das mais jovens de sempre. Tão jovem que um aluno do 9º ano conseguiu o feito de ser seleccionado e ainda o de conquistar uma Menção Honrosa estando a competir com alunos na sua maioria de 11º e 12º ano. Miguel Martins Santos é assim uma promessa para as próximas competições. Ricardo Moreira, que este ano compete pela última vez, arrecadou a única medalha de bronze da equipa.
    (…)
  » 

Adenda de 26-07-2010: O participante dinamarquês nas Olimpíadas Anders Eller Thomson descreve  neste pdf  a estratégia que lhe permitiu resolver este problema, como referido no post IMO 2010, do blogue Absolutely useless

About these ads

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Matemática, Olimpíadas, Problemas com as etiquetas , , , . ligação permanente.

3 respostas a Problema 5 de IMO 2010 resolvido colaborativamente no projecto Mini-Polymath2

  1. Fico muito feliz que gostou do post sobre Média Harmônica. Publiquei ele a algum tempo e resolvi divulgá-lo no carnaval da Matemática. Irei usar este espaço para divulgar outros posts já publicados do blog.

    Faço pesquisas e procuro estudar constantemente, mas estou longe de ter muitos conhecimentos. Aliás, o seu blog também tem muita qualidade.

  2. Entretanto o blogue Absolutely useless disponibilizou mais esta estratégia de resolução, de Mathias Bæk Tejs Knudsen, no post referido na adenda de 26-07-2010.

Deixar uma resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

WordPress.com Logo

Está a comentar usando a sua conta WordPress.com Log Out / Modificar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Log Out / Modificar )

Facebook photo

Está a comentar usando a sua conta Facebook Log Out / Modificar )

Google+ photo

Está a comentar usando a sua conta Google+ Log Out / Modificar )

Connecting to %s