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.

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

Prof. Paulo Sérgio diz:

16 de Julho de 2010 às 22:07

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.

Responder
- Américo Tavares diz:
  
  16 de Julho de 2010 às 22:48
  
  Prof. Paulo Sérgio
  
  Ao ver a data do seu post, surgiu-me logo a ideia de eventualmente vir a aproveitar o Carnaval da Matemática, para divulgar algum(u)s dos meus posts.
Américo Tavares diz:

3 de Agosto de 2010 às 12:54

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.

Responder

Deixe um comentário Cancelar resposta

Este site utiliza o Akismet para reduzir spam. Fica a saber como são processados os dados dos comentários.

	Louis Augusto em Conjectura de Collatz ou probl…
	Arthur Antônio. em Perímetro da astróide
	Arthur Antônio. em Perímetro da astróide
	Tarso Coelho em A Matemática é uma Ciência? ::…
	António Ferrão em Redes Neuronais Artificiais
	maria eclair em Exercício de aplicação dos teo…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…

	Louis Augusto em Conjectura de Collatz ou probl…
	Arthur Antônio. em Perímetro da astróide
	Arthur Antônio. em Perímetro da astróide
	Tarso Coelho em A Matemática é uma Ciência? ::…
	António Ferrão em Redes Neuronais Artificiais
	maria eclair em Exercício de aplicação dos teo…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…