Embed Size (px)
Citation preview
NOTAS DE AULA:RESOLUCAO DE PROBLEMAS
Figura - Fonte: http://www.texample.net/tikz/examples/nontech/decorative-drawings/
Autor: Benedito Tadeu Vasconcelos Freire
2014
Sumario
1 Introducao 2
2 Estrategias 5
3 Antes de fazer, tente entender! 5
4 A busca do plano 5
5 Procure semelhancas com outros problemas. 7
6 Comecar pelo facil torna facil o difıcil. 10
7 Experimente, procure algo que seja invariante. 11
8 Faca um desenho e, dependendo da situacao, pinte as cores. 14
9 Modifique o enunciado, para ver se lhe ocorre um caminho possıvel. 19
10 Explore a simetria. 21
11 Reducao ao Absurdo. 23
12 Suponha o problema resolvido (ou olhe de tras para diante). 25
13 Problemas Diversos 28
14 Legenda 47
15 Bibliografia 48
1
1 Introducao
Da pratica da nossa convivencia com os estudantes, verificamos que a maioria deles nao
tem facilidade para resolver problemas. Estas notas pretendem mostrar algumas ideias
que poderao apontar ao estudante caminhos facilitadores no sentido de tornar a ativi-
dade de resolucao de problemas menos arida.
Para resolver problemas de forma clara, o estudante tem que comunicar suas ideias
de maneira coerente, com organizacao e com argumentos estruturados, permitindo a ele
proprio e aos outros o entendimento facil de seus argumentos e a intrepretacao perfeita
de suas ideias.
A Matematica e a linguagem apropriada para a resolucao de problemas nas diversas
areas do conhecimento, por ser concisa, ter muitos recursos e nao permitir ambiguidades.
Galileu Galilei 1 foi quem introduziu a matematica como linguagem da ciencia.
Como um reconhecimento por suas qualidades indispensaveis a formacao do cidadao,
a Matematica e a unica disciplina que e estudada em todos os paıses do mundo e em
todos os nıveis educacionais.
De acordo com Paul Halmos 2, o coracao da matematica sao seus proprios problemas.
1GALILEU GALILEI Galileu Galilei (1564 -1642 ), italiano, foi um fısico, matematico, astronomo
e filosofo. Galileu Galilei foi personalidade fundamental na revolucao cientıfica. Foi o mais velho dos
sete filhos do musico italiano, alaudista, Vincenzo Galilei e de Giulia Ammannati. Viveu a maior parte
de sua vida em Pisa e em Florenca, na epoca integrantes do Grao-Ducado da Toscana.
Galileu Galilei desenvolveu os primeiros estudos sistematicos do movimento uniformemente acelerado e
do movimento do pendulo. Descobriu a lei dos corpos, enunciou o princıpio da inercia e o conceito de
referencial inercial, ideias precursoras da mecanica newtoniana. Galileu melhorou significativamente o
telescopio refrator e com ele descobriu as manchas solares, as montanhas da Lua, as fases de Venus,
quatro dos satelites de Jupiter, os aneis de Saturno, as estrelas da Via Lactea. Estas descobertas con-
tribuıram decisivamente na defesa do heliocentrismo. Contudo a principal contribuicao de Galileu foi
para o metodo cientıfico, pois a ciencia assentava numa metodologia aristotelica.
O fısico desenvolveu ainda varios instrumentos como a balanca hidrostatica, um tipo de compasso
geometrico que permitia medir angulos e areas, o termometro de Galileu e o precursor do relogio de
pendulo. O metodo empırico, defendido por Galileu, constitui um corte com o metodo aristotelico mais
abstrato utilizado nessa epoca, devido a isto Galileu e considerado como o ”pai da ciencia moderna”.
Fonte: http : //pt.wikipedia.org/wiki/GalileuGalilei. Acessado em 17/03/2014.2PAUL HALMOS - (1916 - 2006) foi um matematico estadunidense nascido na Hungria, que fez
avancos fundamentais nas areas de Logica Matematica, Teoria da Probabilidade, Estatıstica, Teoria dos
2
”A maior parte de cada vida significativa e passada com a solucao de problemas; uma
parte consideravel da vida profissional de tecnicos, engenheiros, cientistas, etc., e vivida
na busca de solucao de problemas de matematica. E dever de todos os professores e dos
professores de matematica em particular, expor seus alunos para problemas muito mais
do que aos fatos”, disse ele.
O uso da Matematica com linguagem exige um conhecimento mınimo para poder
ser utilizada. Por isso, o estudante necessita de situacoes que permitam exercitar essa
linguagem, e uma delas sao os empregos dos metodos de resolucao de problema.
Uma referencia no estudo da arte de resolver problema sao os trabalhos do professor
Polya 3
Operadores, Teoria Ergodica e Analise Funcional (em especial, nos espacos de Hilbert ). Ele tambem foi
reconhecido como um grande expositor da matematica.
Halmos chegou em os EUA aos 13 anos de idade, mas nunca perdeu seu sotaque hungaro. Halmos obteve
seu Bacharelado na Universidade de Illinois, graduando em filosofia e especializando-se em matematica.
Ele levou apenas tres anos para obter o grau, e tinha apenas 19 anos quando se formou. Comecou um
doutorado (Ph.D.) na filosofia, mas, passou para a matematica, graduando-se em 1938 sob a orientacao
do Professor Joseph L. Doob, com a dissertacao intitulada: A Invariantes de Certas Transformacoes
Estocasticos: A Teoria Matematica de Sistemas de Jogos.
Pouco depois de sua formatura, Halmos foi para o Instituto de Estudos Avancados. Seis meses depois,
ele estava trabalhando com John von Neumann, que se revelou uma experiencia decisiva. Na sua per-
maneencia no Instituto de Estudos Avancados, Halmos escreveu seu primeiro livro, Espacos Vetoriais
de Dimensoes Infinitas, que imediatamente estabeleceu sua reputacao como um excelente expositor da
matematica.
Halmos ensinou na Universidade de Syracuse , na Universidade de Chicago (1946-1960), na Univer-
sidade de Michigan, na Universidade da California, em Santa Barbara (1976-1978), na Universidade
do Havaı, e na Universidade de Indiana, onde se aposentou. Desde sua aposentadoria, em 1985, ate
sua morte, ele era ligado ao departamento de Matematica da Universidade de Santa Clara. Fonte:
http://en.wikipedia.org/wiki/PaulHalmos.Acessadoem17/03/2014.3GEORG POLYA - George Polya (1887 1985) hungaro, professor de matematica de 1914 a 1940
no Instituto Federal de Tecnologia de Zurique, na Suıca, de 1940 a 1953 na Stanford University, nos
Estados Unidos. Polya permaneceu como Professor Emerito da Stanford o resto de sua vida e carreira.
Ele trabalhou em uma variedade de topicos matematicos, incluindo series, teoria dos numeros, analise
matematica, geometria, algebra, combinatoria e probabilidade.
No inıcio de sua carreira, Polya escreveu com Gabor Szego, matematico hungaro famoso, dois influentes
livros de problemas: Problemas e Teoremas em Analise (I: Serie, Calculo Integral, Teoria das Funcoes
e II, Teoria das Funcoes, Zeros de polinomios, Determinantes, Teoria dos Numeros ,Geometria.....).
Mais tarde, ele se dedicou ao estudo da Heurıstica, um metodo ou processo criado com o objetivo de
encontrar solucoes para um problema, para identificar metodos sistematicos de resolucao de problemas
a uma maior descoberta e invencao em matematica para os estudantes, professores e pesquisadores. Ele
3
Para oportunizar a resolucao de problemas, apresentamos no texto problemas de
Olimpıada de Matematica de varios paıses, por serem intrigantes, criativos e desafiado-
res.
E comum uma diferenciacao entre problema e exercıcio, veja, por exemplo em [6],
pagina x. O exercıcio e uma questao que testa o domınio do estudante numa tecnica
que esta sendo focada ou que foi recentemente coberta. Exercıcios podem ser difıceis ou
faceis, mas, de uma maneira geral, eles nunca sao intrigantes, e normalmente fica claro
como proceder no sentido de como encontrar a solucao. Por outro lado, um problema
e uma questao que nao pode ser respondida imediatamente. Problemas sao muitas
vezes abertos, paradoxais, as vezes indecifraveis e exigem investigacao antes que se pode
chegar a uma solucao.
Esperamos que os estudantes possam apreciar as ideias que permitem a resolucao
dos problemas aqui apresentados.
Todos os erros e equıvocos sao de nossa responsabilidade. Receberemos com alegria
comentarios apontando eventuais erros, como tambem formas de melhorar o texto.
Natal, abril de 2014
Benedito Tadeu Vasconcelos Freire
escreveu cinco livros sobre o assunto: How to Solve it, traduzido para o portugues como A Arte de
Resolver Problema, Matematica e Raciocınio Plausıvel (Volume I: Inducao e Analogia em Matematica,
e Volume II: Padroes de Plausıvel Inference) e descoberta matematica: Na compreensao, aprendizado e
ensino Problem Solving (volumes 1 e 2).
Em How to Solve It, Polya fornece sugestoes heurısticas para resolver uma gama de problemas, incluindo
os problemas matematicos e os nao-matematicos. O livro inclui conselhos para ensinar os alunos de
matematica e uma mini-enciclopedia de termos heurısticos. Foi traduzido para varias lınguas e ja vendeu
mais de um milhao de copias. O fısico russo Zhores I. Alfyorov, (Premio Nobel em 2000), elogiou,
lembrando que ele era um fa. O livro ainda e usado em educacao matematica.
Alem de suas obras que abordam diretamente a resolucao de problemas, Polya escreveu outro livro
chamado Metodos Matematicos em Ciencias, com base em um trabalho de 1963 apoiado pela National
Science Foundation, editado por Leon Bowden, e publicado pela Associacao Matematica da America
(MAA), em 1977. FONTE: http : //en.wikipedia.org/wiki/GeorgeP olya.
4
2 Estrategias
Ja e classica e bem conhecida, a formulacao que fez Polya das quatro etapas essenciais
para a resolucao de um problema, que constituem o ponto de partida de todos os estudos
posteriores:
• Antes de fazer, tente entender
• Tracar um plano para resolve-lo
• Colocar o plano em pratica
• Comprovar os resultados
3 Antes de fazer, tente entender!
Quando alguem lhe propoe um problema, um jogo, um quebra-cabeca, inicialmente,
assegure-se que entendeu a fundo os dados do problema, as regras do jogo e o possıvel
lugar que tem cada uma dessas informacoes, como elas se encaixam umas com as outras.
Para resolver um problema, e imprescindıvel que voce conheca o que e dado e, exata-
mente, o que o problema pede.
Faca a si mesmo as seguintes perguntas:
• Qual e a incognita?
• Quais sao as quantidades dadas?
• Quais sao as condicoes dadas?
• O que o problema pede?
A solucao do problema consiste em ligar, por passos logicos, os dados do problema
ao que nele se pede .
4 A busca do plano
Uma das tecnicas de criatividade, chamada tempestade de ideias (em ingles brainstor-
ming), geralmente feita em grupo, revela que a quantidade gera a qualidade. O metodo
foi popularizado nos anos de 1930 pelo americano Alex Faicney Osborn. A fase em que
voce procura um plano capaz de levar a solucao de um problema e uma situacao parecida
com a tempestade de ideia, so que exercida muitas vezes solitariamente por voce. Esta
5
fase do processo de resolucao do problema e aquela em que deve nascer da sua cabeca
muitas ideias, mesmo que possam parecer totalmente inocuas.
Durante este processo, nenhuma ideia deve ser descartada ou julgada como errada ou
absurda. As vezes, as ideias em que voce menos aposta podem se revelar as mais apro-
priadas. Por isso, anote todas as suas ideias.
Se voce ja tem algumas estrategias possıveis para atacar o problema, a tarefa a seguir
e meditar sobre as suas ideias e deixar que o seu subconsciente trabalhe, a seu gosto,
esse amontoado de ideias que voce preparou para ele. E aconselhavel que voce faca uma
lista das melhores ideias, a princıpio sem mistura-las. Explore cada ideia da lista com
decisao e confianca, de forma ordenada, em paz, sem precipitacoes.
Se, ao colocar em pratica uma ideia, lhe ocorrer outra, totalmente desligada da primeira,
e que voce avalia que pode lhe ajudar, nao va despreza-la. Coloque-a na sua lista. Mas,
tambem nao desvie sua atencao da que agora esta explorando.
Um ponto importante que deve sempre ser lembrado: voce nao pode desistir facilmente.
Por outro lado, nao deve teimar demais so com uma ideia. Se as coisas complicarem
demais, havera provavelmente outro caminho. Um caminho que foi muito usado na
historia de matematica foi o da tentativa e erro, tentativa e erro, tentativa e erro, voce
nao pode esquecer este fato.
Ao concluir sua resolucao, voce precisa ter certeza disso. Reveja sua solucao com cui-
dado.
Uma verdade: as meias ideias e as meias solucoes de pouco servem!
E preciso certificar de que, realmente, voce chegou a solucao.
Se voce conseguir resolver o problema, otimo.
Se trabalhou horas a fio e nao conseguiu vislumbrar uma solucao, nao se preocupe. Muitas
vezes se aprende profundamente com os problemas que se tenta, com interesse, deter-
minacao e persistencia ...... e nao se consegue resolver, do que com os que se resolve a
primeira vista.
Um conselho deve ser lembrado: e mais importante a qualidade do que a quantidade.
Nao se apresse em demasia. Ao concluir a solucao de um problema, e preciso que voce
reflita sobre o processo, para que tenha uma ideia das dificuldades, dos becos sem saıdas
em que se meteu e, principalmente, como deve proceder no futuro para resolver melhor
outros problemas, parecidos ou nao.
Uma reflexao sobe o nosso proprio processo de pensamento e interessante na medida
em que podemos tirar bons proveitos para o futuro. Cada um tem seu proprio estilo de
conhecimento. Visual ou analıtico? Depende muito da expressao verbal ou da forma
escrita? Tem tendencia para o compromisso com ideia unica, sem flexibilidade? Tem
6
tendencia a pensar em cırculo obsessivamente? Como se pode fomentar o fluxo de ideias
novas, variadas, originais? Reflexoes como essas ajudam, a saber, que tipo de problemas
voce pode se ocupar com sucesso e em quais deles sua probabilidade de exito nao e tao
grande.
5 Procure semelhancas com outros problemas.
Como nao ha nada de novo debaixo do ceu, e conveniente procurar semelhancas do pro-
blema dado com outros que voce ja conhece.
Pergunte a si mesmo: o que e que esse problema me faz lembrar?
Se seu problema for generico, tente primeiro alguns casos particulares. Caso o problema
envolva a geometria tridimensional, voce podera tentar primeiro um problema bidimen-
sional analogo.
Problema 5.1 - Resolva a equacao x4 − 5x2 + 6 = 0.
Solucao
Se a equacao dada parece difıcil, troque x2 por t, obtendo a equacao
t2 − 5t+ 6 = 0 (∗),
que e mais facil de resolver. Assim, as solucoes da equacao (*) sao t = 2 e t = 3, o que
implica x2 = 2 ou x2 = 3. Portanto, as solucoes da equacao dada sao: ±√
2 e ±√
3.
Problema 5.2 - Numa caixa retangular fechada, veja Figura a seguir, no vertice A te-
mos uma formiga e no vertice B temos outra formiga. A formiga na posicao A quer
encontrar a formiga na posicao B.
7
Qual e o caminho mais curto sobre a caixa, ligando A ate B?
Solucao
O que e que esse problema me faz lembrar?
Se a questao fosse num retangulo, figura plana, em vez de uma caixa retangular, figura
tridimensional, a questao seria resolvida simplesmente procurando o menor caminho
sobre o plano ligando dois pontos, que sabemos ser um segmento de reta. O que temos
que fazer e tornar a caixa tridimensional um objeto bidimensional. Como fazer isso?
Abrindo a caixa, marcando os dois pontos e tracando o segmento de reta ligando os
pontos A e B, veja figura a seguir.
Depois disso, recompomos a caixa, mostrando o menor caminho ligando os pontos A e
B, veja figura a seguir.
8
Problema 5.3 - Qual e a soma dos n termos da series 7 + 77 + 777 + 7777 + · · ·?Solucao
Se em vez de 7 + 77 + 777 + 7777 + · · · tivessemos
9 + 99 + 999 + 9999 + · · ·?
Neste caso, reescreverıamos a series como:
9 + 99 + 999 + 9999 + · · · = (10− 1) + (100− 1) + (1000− 1) + (10000− 1) + · · · =
= (10 + 100 + 1000 + 10000 + · · ·)− n
As potencias de 10 formam uma progressao geometrica de n termos cuja soma e igual a10n+1−10
9 . Assim,
9 + 99 + 999 + 9999 + · · · =
= (10− 1) + (100− 1) + (1000− 1) + (10000− 1) + · · · = 10n+1 − 10
9− n.
Agora, observe que para encontrar a soma pedida, basta observar que 7 e igual a 79 de 9,
o que implica que a soma pedida e igual a
7+77+777+7777+ · · · = 7(1+11+111+1111+ · · ·) =7
9×9(1+11+111+1111+ · · ·) =
=7
9(9 + 99 + 999 + 9999 + · · ·) =
[10n+1 − 10
9− n
]=
7
81(10n+1 − 9n− 10).
9
Problema 5.4 - Numa sala de aula existem 25 alunos sentados em 5 filas com 5 lugares
em cada fila. Um dia o professor pede aos alunos para mudar os lugares como segue:
cada aluno deve mover um assento para a frente ou para tras ou um assento a esquerda
ou a direita - movimento em diagonal nao e permitido.
E possıvel que todos os 25 alunos sigam estas instrucoes?
Solucao
A abordagem tradicional e tentar varios movimentos. Isso geralmente nao resolve
o problem e causa certa frustracao. A ideia aqui e resolver um problema analogo mais
simples. Assim, faca um desenho da sala e numere os assentos, veja figura a seguir.
Agora, observe que, dos numeros inteiros de 1 a 25, temos 13 numeros ımpares
e somente 12 numeros pares. Com os movimentos permitidos, cada aluno passa de
uma cadeira de numero ımpar para uma cadeira de numero par, e vice-versa. Como a
quantidade de numeros pares difere da quantidade de numeros ımpares, vai haver um
aluno que que nao pode se movimentar.
Portanto, e impossıvel que todos os 25 alunos sigam as instrucoes do professor.
6 Comecar pelo facil torna facil o difıcil.
Talvez o problema seja complicado porque ha muitos elementos. Tente tornar o problema
mais facil. Construa um, menos complicado, com menos dados. Talvez essa situacao
venha lhe revelar algo que facilite a solucao do problema mais complexo.
Problema 6.1 - (BW - 2005) E possıvel encontrar 2014 numeros inteiros positivos dis-
tintos, cada um deles um quadrado perfeito, tal que a soma seja tambem um quadrado
perfeito?
Solucao
10
A resposta e sim.
Se o problema fosse encontrar dois numeros inteiros positivos quadrados perfeitos cuja
soma fosse um quadrado perfeito, usarıamos o teorema de Pitagoras:
32 + 42 = 52.
Agora, vamos ver que esta situacao mais simples nos revela uma saıda par o problema
mais complexo. De fato, multiplique cada lado da ultima igualdade por 52, obtendo
32.52 + 42.52 = 52.52
e substitua 52 na primeira parcela do lado esquerdo por 32 + 42. Assim, obtemos
32(32 + 42) + 42×52 = 52 ⇐⇒ 32.32 + 32.42 + 42.52 = 52.52.
Novamente, multiplicando cada lado da ultima igualdade por 52, obtemos
32.32.52 + 32.42.52 + 42.52.52 = 52.52.52
e usando na primeira parcela a esquerda a substituicao de 52 por 32 + 42, obtemos:
32.32.32 + 32.32.42 + 32.42.52 + 42.52.52 = 52.52.52.
Continuando esse processo, encontraremos 2014 numeros inteiros positivos distintos, que
sao quadrados perfeitos, tal que a soma seja tambem um quadrado perfeito.
7 Experimente, procure algo que seja invariante.
Muita matematica foi feita por tentativa, errando, corrigindo, aperfeicoando, avancando.
As vezes pode ser vantajoso introduzir no problema algo novo, um auxılio extra, para que
facilite voce na percepcao entre o que foi dado e o que foi pedido.
Problema 7.1 - Tem-se quarenta e tres pedacos de palitos, cujos comprimentos sao
1, 2, 3, · · · , 42, 43 centımetros, respectivamente.
Diga, justificando, se e possıvel formar um quadrado usando todos estes pedacos, sem
quebrar qualquer um deles, nem sobrepor dois ou mais deles.
E se em vez de um quadrado for um retangulo?
Solucao
11
Aqui e conveniente observar que
1 + 2 + 3 + · · ·+ 42 + 43 =43× (43 + 1)
2= 43× 22 = 946.
Se fosse possıvel formar um quadrado, de lado medindo x, usando todos estes pedacos,
sem quebrar qualquer um deles, nem sobrepor dois ou mais deles, terıamos necessari-
amente que o perımetro do quadrado seria igual a 946. Ou seja, 4x = 946, o que e
impossıvel, pois x tem de ser um numero inteiro e o numero 946 nao e divisıvel por 4.
Se em vez de um quadrado for um retangulo, com lados medindo a e b centımetros,
terıamos o perımetro do retangulo como sendo igual a 2a+2b = 946, ou seja a+b = 473.
Neste caso, a resposta e sim. Se os quatro lados do retangulo medem a, a, b, b, poderıamos
tomar:
a = 1 + 2; e a = 3, e
b = (4 + 43) + (6 + 41) + (8 + 39) + (10 + 37) + · · ·+ (18 + 29) + (20 + 27) + (22 + 25)
e
b = (5 + 42) + (7 + 40) + (9 + 38) + (11 + 36) + · · ·+ (19 + 28) + (21 + 26) + (23 + 24).
Problema 7.2 - Um tabuleiro 10 × 10 pode ser coberto por 25 dominos de dimensoes
1× 4?
Solucao
Aqui o invariante mais obvio e a area, que infelizmente nao ajuda na solucao do
problema. Por outro lado, podemos escrever um numero em cada um dos 100 quadrados
unitarios do tabuleiro com a propriedade que, nao importa como nos colocamos um dos
dominos cobrindo 4 quadrados, a soma dos numeros em quatro quadrados coberto seja
igual a zero; no entanto, a soma de todos os 100 numeros em todo o tabuleiro nao e
zero. Entao, obviamente, a cobertura e impossıvel.
Como associar os numeros aos quadrados unitarios do tabuleiro do modo com pre-
vemos acima?
Defina os valores an, para n = 1, 2, 3, · · · , 9, 10, da seguinte maneira:
a1 = 1 a2 = 1 a3 = 1 a4 = −3 a5 = 1 a6 = 1 a7 = 1 a8 = −3 a9 = 1 a10 = 1
Nesta sequencia, qualquer bloco consecutivo de quatro termos tem soma igual a 0, mas
a soma de todos os dez nao e 0. Agora, escrevemos no quadrado unitario do tabuleiro
12
que esta na linha m e coluna n o numero am × an, que nos sugere uma pintura para o
tabuleiro usando tres cores distintas, veja figura a seguir.
Problema 7.3 - (AUMO - 1978) Tres maquinas caca-nıqueis imprimem pares de in-
teiros positivos em cartoes. As maquinas caca-nıqueis trabalham da seguinte maneira.
A primeira maquina caca-nıquel depois de ler um cartao (a, b) imprime um novo cartao
(a + 1, b + 1); a segunda maquina caca nıquel depois de ler um cartao (a, b) imprime
um novo cartao (a2 ,b2). Esta maquina so funciona se os numeros a e b forem pares. A
terceira maquina caca-nıquel, depois de ler dois cartoes (a, b) e (b, c) imprime um novo
cartao (a, c). Alem disso, as maquina caca-nıquel devolvem todos os cartoes lidos.
E possıvel comecar com um cartao (4, 18) e chegar num cartao (1, 100)?
Solucao
A resposta e nao.
Para qualquer cartao (a, b) chame D(a, b) a diferenca a − b. Seja S a colecao de todos
os cartoes obtidos a partir do cartao (4, 18) por meio de operacoes consecutivas das
maquinas caca-niquel.
Vamos mostrar que D(a, b) e divisıvel por 7, para cada (a, b) ∈ S. Isto e, o resto da
divisao de D(a, b) por 7 e um invariante.
Para mostrar isso, vamos usar inducao sobre o numero de sucessivos usos das maquinas.
Observe que D(4, 18) = 4− 18 = −14. Logo, o resto da divisao de D(4, 18) por 7 e zero:
−14 = (−2)× 7 + 0. Vamos supor que depois do n−esimo uso das maquinas tenhamos
um cartao (a, b), com o resto da divisao de D(a, b) por 7 igual a zero.
13
Vamos considerar o (n + 1)−esimo uso das maquinas caca-niquel. Existem tres casos
possıveis:
• Usando a primeira maquina, depois de colocar o cartao (a, b), obtemos o cartao
(a + 1, b + 1). Neste caso, D(a + 1, b + 1) = (a + 1) − (b + 1) = a − b, que, por
hipotese de inducao, e divisıvel por 7;
• Usando a segunda maquina, depois de colocar o cartao (a, b), obtemos o cartao
(a2 ,b2). Neste caso, D(a2 ,
b2) = a
2 −b2) = 1
2(a − b), que, por hipotese de inducao, e
divisıvel por 7.
• Usando a terceira maquina, depois de colocar os cartoes (a, b) e (c, d), obtemos o
cartao (a, c). Neste caso, D(a, c) = a− c = a− b+ b− c = (a− b) + (b− c), que,
por hipotese de inducao, e divisıvel por 7, por ser soma de dois numeros multiplos
de 7.
Assim, em todos os tres casos, o resto da divisao de D(a, b) por 7 no novo cartao
e nulo. O mesmo e verdade para o caso do cartao obtido a partir de (4, 18) nas tres
maquinas caca-niquel. Mas, D(1, 100) = 1 − 100 = −99 = (−15) × 7 + 6. Portanto,
D(1, 100) deixa resto 6 na divisao por 7, consequentemente nao e possivel obter o cartao
(1, 100) a partir do cartao (4, 18).
8 Faca um desenho e, dependendo da situacao, pinte as
cores.
Muitos de nos pensamos melhor com um desenho, esquema, imagem, do que com pala-
vras. Diz o ditado popular: uma imagem vale mais do que mil palavras.
Logo, sempre que puder, faca um esquema auxiliar, um desenho, pinte as cores. Essas
atitudes, quase sempre revelam caminhos surpreendentemente elegantes e faceis de com-
provar.
Problema 8.1 - Considere um tabuleiro de xadrez 8×8 e 32 dominos de dimensao 2×1.
Os dominos podem ser arranjados sobre o tabuleiro de modo a cobri-lo inteiramente,
cada domino cobrindo perfeitamente dois quadrados unitarios. Dois quadrados unitarios,
situados nos cantos do tabuleiro, sao retirados, veja Figura a seguir.
14
Diga, justificando, se 31 dominos cobrem completamente o tabuleiro reduzido.
Solucao
A resposta e nao.
A ideia aqui e pintar o tabuleiros de modo que as casas fiquem alternadamente pretas e
brancas, veja figura a seguir.
Observe que os dois quadrados situados nos cantos do tabuleiro possuem a mesma cor e
que cada domino por inteiro cobre sempre uma casa de cada cor, independente de como
voce o coloca sobre o tabuleiro na horizontal ou vertical. Assim, se a cobertura fosse
possıvel deverıamos ter no tabuleiro a mesma quantidade de casas de cada cor, o que
nao ocorre com a retirada de duas casas de mesma cor.
15
Portanto, 31 dominos nao cobrirao completamente o tabuleiro reduzido.
Problema 8.2 - O rei, peca do jogo de xadrez, se movimenta uma unica casa em to-
das as direcoes. Pode o rei, comecando do quadrado mais abaixo, a esquerda, ir ate
o quadrado mais acima a direita, visitando cada uma das casas restantes do tabuleiro
exatamente uma unica vez?
Solucao
A resposta e nao.
Pinte as casas do tabuleiro alternadamente pretas e brancas. Agora, basta observar que
o rei vai de uma casa de uma cor para a casa de cor oposta. omo o rei tem que fazer
63 movimentos, o ultimo ira deixa-lo em uma casa da cor oposta a cor da primeira
casa. Mas, a primeira casa e a ultima possuem a mesma cor, o que e uma contradicao.
Portanto, o rei nao pode, comecando do quadrado mais abaixo, a esquerda, ir ate o
quadrado mais acima a direita, visitando cada uma das casas restantes do tabuleiro
exatamente uma unica vez.
Problema 8.3 - Bolas de tenis de mesmo raio r sao hermeticamente embaladas em
latas cilındricas com 3 bolas, onde elas apenas tocam a lata na superfıcie lateral, no topo
e no fundo.
Qual e maior: a altura da lata de embalagem ou a medida da circunferencia de cada
bola?
Solucao
A resposta e: a medida da circunferencia de cada bola.
Facamos um desenho da situacao.
Observe que a altura da lata e igual a 3d, onde d e o diametro da circunferencia de
cada bola. A medida da circunferencia de cada bola e igual 2πr = 2π d2 = πd > 3d, pois
π = 3, 14 · · · > 3.
16
Problema 8.4 - (BW - 2003) Diga, justificando, se e possıvel escolher 1000 pontos do
plano de tal modo que no mınimo 6000 distancias entre dois deles sejam iguais.
Solucao
A resposta e sim.
Comece com uma configuracao de 4 pontos e 5 distancias, veja figura a seguir.
Agora tome a figura acima e mais duas copias congruentes a ela, obtidas por movimentos
paralelos (e nao coincidentes), veja figuta a seguir.
Neste caso, tem-se 3 × 4 = 12 pontos e 3 × 5 + 12 = 27 distancias. Agora junte mais
tres copias da figura acima, obtendo:
3× 12 = 36 pontos e 3× 27 + 36 = 117 distancias.
Agora, forme uma figura com 9 figuras congruentes a figura inicial, obtidas dela por
movimentos paralelos (e nao coincidentes). Desse modo, temos
3× 36 = 108 pontos e 3× 117 + 108 = 459 distancias.
Procedendo desta maneira, sempre juntando mais 3 copias da figura inicial, vamos ob-
tendo gradativamente:
3× 108 = 324 pontos e 3× 459 + 324 = 1701 distancias.
17
3× 324 = 972 pontos e 3× 1701 + 972 = 6075 distancias.
Problema 8.5 - Do piso 13× 13 de uma sala retira-se o quadrado unitario central.
E possıvel ladrilhar o restante da sala usando ladrilhos retangulares de dimensoes 1× 4
ou 4× 1?
Solucao
Nao.
Pinte os quadrados do assoalho de preto e branco no padrao seguinte. Na primeira
linha acima, pinte de preto os dois quadrados mais a esquerdal, pinte de branco os dois
seguintes (da esquerda para direita), os dois proximos pinte de preto, os dois proximos de
branco, e assim por diante, de modo que na extremidade direita fique um unico quadrado
preto. Na segunda linha, pinte a linha de forma alternada com a pintura da primeira
linha: dois quadrados brancos, dois quadrados pretos e assim por diante. Numerando as
linhas de 1 a 13, temos que todas as linhas ımpares sao pintadas de forma identica que a
pintura da primeira linha e todas as linhas numeradas com numeros pares sao pintadas
de forma identica que a pintura da linha de numero 2, veja figura a seguir.
Observe que existem mais quadrados unitarios pretos do que quadrados brancos. Por
outro lado, cada ladrilho 4×1, nao importa como seja colocado, cobre precisamente dois
quadrados unitarios pretos e dois brancos. Assim, se um ladrilhamento deixar um unico
quadrado descoberto, este quadrado tem de ser preto. Mas, o quadrado central e branco.
Portanto, tal ladrilhamento e impossıvel.
18
9 Modifique o enunciado, para ver se lhe ocorre um cami-
nho possıvel.
Quando o problema parecer difıcil demais, modifique o enunciado, transforme o problema
em outro, isto pode levar a um caminho que lhe mostre a saıda.
Problema 9.1 - Calcule o valor da expressao E = (tan 15o).(tan 30o).(tan 45o).(tan 60o).(tan 75o).
Solucao
A ideia aqui e observar que se x+ y = 90o, entao
tan (x+ y) =tan x+ tan y
1− tan x. tan y= tan 90o =∞.
Ou seja, 1− tan x. tan y = 0, que e o mesmo que tan x. tan y = 1, ou ainda
tan x =1
tan y=
1
tan (90o − x)= cot (90o − x)
Logo, temos que
tan 75o = cot (90o − 75o) = cot 15o;
tan 60o = cot (90o − 60o) = cot 30o.
Portanto,
E = (tan 15o).(tan 30o).(tan 45o).(tan 60o).(tan 75o) =
= (tan 15o).(cot 15o).(tan 30o).(cot 30o).(tan 45o) = 1.1.1 = 1.
Problema 9.2 - (BW 2004) Escreve-se em cada uma das seis faces de um cubo um
numero inteiro positivo. Para cada vertice do cubo, calcula-se o produto dos numeros
nas tres faces adjacentes a ele. A soma desses produtos e igual a 1001
Qual e a soma dos seis numeros escritos nas faces do cubo?
Solucao
Em vez de tomar aleatoriamente os seis numeros escritos nas faces do cubo, vamos
considerar os numeros dois a dois, escritos nas faces opostas. Assim, sejam a1, a2, b1, b2, c1, c2
os numeros escritos nas faces dos cubos de tal maneira que a1, a2 estao escritos em fa-
ces opostas, b1, b2 numeros ecritos em faces opostas e c1, c2 numeros escritos em faces
opostas. Agora, a soma dos oito produtos:
a1.a2 + a1.b1 + a1.b2 + a1.c1 + · · ·+ c1.c2 = 1001.
19
Por outro lado,
a1.a2 + a1.b1 + a1.b2 + a1.c1 + · · ·+ c1.c2 = (a1 + a2).(b1 + b2).(c1 + c2) =
= 1001 = 7.11.13
. Portanto, a soma dos oito numeros escritos nas faces do cubo e igual a:
(a1 + a2) + (b1 + b2) + (c1 + c2) = 7 + 11 + 13 = 31.
Problema 9.3 - (BW 2001) Pintam-se ou de vermelho ou de verde 2001 pontos dis-
tintos sobre um cırculo. Em cada etapa, todos os pontos sao simultaneamente pintados
novamente da maneira seguinte:
se dois pontos sao vizinhos imediatos de um ponto P e possuem a mesma cor que P ,
entao a cor de P nao se altera, caso contrario P muda de cor.
Comecando com a primeira pintura F1, obtemos as pinturas F2, F3, · · ·, depois de aplicar
varias etapas de pinturas.
Prove que existe um numero n0 ≤ 1000 tal que Fn0 = Fn0+2. Isto e verdade se o numero
1000 for substituıdo pelo numero 999?
Solucao
A resposta e nao.
Vamos denotar os pontos sobre o cırculo por 1, 2, 3, · · · , 2001, de tal modo que os pontos
i, j sejam vizinhos se |i− j| = 1 ou {i, j} = {1, 2001}.Vamos dizer que k pontos formam um segmento monocromatico de comprimento k se os
pontos sao consecutivos sobre o cırculo e se eles possuem a mesma cor.
Para uma pintura F , chamamos de d(F ) o comprimento maximo de um segmento mo-
nocromatico. Observe que d(F ) > 1, para todo n, pois 2001 e ımpar. Se d(F ) = 2001,
entao todos os pontos possuem a mesma cor, portanto, F1 = F2 = F3 = · · · e, neste
caso, podemos escolher n0 = 1.
Seja 1 < d(F1) < 2001. Valem as seguintes propriedades:
(i) Se 3 < d(Fn) < 2001, entao d(Fn+1) = d(Fn)− 2;
(ii)Se d(Fn) = 3, entao d(fn+1) = 2;
(iii) Se d(Fn) = 2, entao d(Fn+1)=d(Fne fn+2 = fn;
Se valem as tres propriedades acima, segue de (i) e (ii) que d(F1000) ≤ 2 e por
(iii) temos que F1000 = F1002. Alem disso, se F1 e a pintura onde 1 e pintado de
vermelho e todos os outros pontos sao pintados de verde, entao d(F1) = 2000 e entao
20
d(F1) > d(F2) > · · · > d(F1000) = 2, o que mostra que para todo n < 1000, temos
Fn 6= Fn+2 e entao 1000 nao pode ser substituıdo por 999.
Agora, vamos provar as tres propriedades acima.
Seja (i+ 1, i+ 2, , · · · , i+ k) o maior segmento monocromatico para Fn, considerando os
pontos modulo 2001. Entao (i + 2, i + 3, · · · , i + k − 1) e um segmento monocromatico
para Fn+1 e segue que d(Fn+1) ≥ d(Fn)−2. Alem disso, se (i + 1, i + 2, , · · · , i + k) e o
maior segmento monocromatico para Fn+1, com k ≥ 3, entao (i, i + 1, · · · , i + k + 1) e
um segmento monocromatico para Fn. Disso, e do fato de Fn+1 > 1, seguem (i) e (ii).
Para provar (iii) observe que se d(Fn) ≤ 2 entao Fn+1 e obtido de Fn mudando as cores
de todos os pontos, o que conclui a prova.
10 Explore a simetria.
Muitos problemas sao resolvidos quando se explora a simetria que o problema apresenta,
de forma explıcita ou mesmo mascarada.
Problema 10.1 - Inscreve-se um quadrado num cırculo, que por sua vez esta inscrito
noutro quadrado, veja figura a seguir.
Qual e a razao das areas dos dois quadrados?
Solucao
Podemos resolver o problema usando a nocao de simetria. Se voce gira o quadrado
menor por um angulo de 450, seus vertices irao coincidir com os pontos de tangencia
do cırculo e do quadrado maior. Portanto, e facil ver, que o quadrado menor possui a
metade da area do quadrado maior, veja Figura a seguir.
21
Problema 10.2 - (CMO 1978) Eve e Odette disputam um jogo num tabuleiro 3 × 3,
com pecas brancas e pecas pretas. As regras sao as seguntes:
I - Elas jogam alternadamente;
II - Uma jogada consiste em colocar uma peca numa casa do tabuleiro ainda nao ocu-
pada;
III - Na sua vez de jogar, uma jogadora pode escolher ou uma peca branca ou uma peca
preta e nao precisa usar sempre a mesma cor;
IV - Quando o tabuleiro esta totalmente preenchido pelas pecas, Eves obtem um ponto
para toda linha, coluna ou diagonal que possuir um numero par de pecas pretas, e Odette
obtem um ponto para toda linha, coluna ou diagonal que possuir um numero ımpar de
pecas pretas;
V - A jogadora que obtiver no mınimo cinco dos oito pontos VENCE.
Descreva uma estrategia vencedora para a garota que comeca o jogo.
Solucao
Vamos supor que Eve comeca o jogo.
Eve coloca uma peca preta na casa central do tabuleiro, ela existe pois no tabuleiro temos
9 casas. A partir daı, sempre que Odette jogar, Eve joga com uma peca da cor oposta a
de Odette na casa simetrica, em relacao a casa central, daquela que Odette jogou. Por
este procedimento, Eve obtem um ponto para toda linha, coluna e diagonal que passem
pelo centro. Alem disso, pelo menos uma das linhas ou colunas que passam pelo centro
tem 2 pecas pretas, daı Eves vence o jogo.
Chamando de B uma peca branca e P uma peca preta, no fianl do jogo o tabuleiro tera
a seguinte aparencia:
P 1 B
P
P 2 B
22
Exatamente uma das casas 1 e 2 possui uma peca preta, e a linha dela possui um numero
par de pecas pretas.
11 Reducao ao Absurdo.
Um raciocınio muito empregado na resolucao de problemas e aquele que comumente se
chama de metodo por reducao ao absurdo ou metodo indireto.
Como e que funciona?
Se voce pretende mostrar que uma afirmacao A implica numa afirmacao B, comece su-
pondo que isto nao acontece. Ou seja, que A nao implica em B. Fazendo deducoes e
raciocınios corretos, voce chegara a conclusao de que uma afirmacao, que voce sabe que
e correta, nao se realiza. Ou seja, voce chegara a uma contradicao. Portanto, A implica
em B.
Problema 11.1 - Demonstrar que o numero√
2 e irracional.
Solucao
Suponha o contrario. Isto e,√
2 nao e um numero irracional. Isto significa dizer
que√
2 = mn , onde m,n ∈ Z, com n 6= 0. Sem perda de generalidade, vamos supor que
os numeros m e n sejam relativamente primo. Ou seja, MDC(m,n) = 1. Elevando ao
quadrado ambos os membros de√
2 = mn , obtemos 2 = m2
n2 , que e o mesmo que dizer que
m2 = 2n2 (∗).
Assim, m2 e par e, logo, m e par. Desse modo, m = 2k, onde k ∈ Z. Substituindo esse
valor de m em (*), obtemos que n2 e par, o que implica que n e par. Assim, concluımos
que m e par e n e par. Uma contradicao, pois tınhamos suposto MDC(m,n). = 1.
Portanto, o numero√
2 e irracional.
Problema 11.2 - (BW - 2001) Escrevem-se os numeros 1, 2, 3, · · · , 49 nas casas de um
tabuleiro 7 × 7, sendo um numero em cada casa e calcula-se a soma dos numeros em
cada linha e cada coluna. Algumas dessas 14 somas sao ımpares enquanto as outras sao
pares. Seja A a soma de todas as somas ımpares e B a soma de todas as somas pares.
E possıvel colocar os numeros nas casas do tabuleiro de modo que A = B?
Solucao
23
A resposta e nao.
Se isto fosse possıvel, terıamos 2× (1+2+3+4+ · · ·+49) = A+B = 2B. Mas, B e um
numero par, pois e a soma de numeros pares. Por outro lado, 1 + 2 + 3 + 4 + · · ·+ 49 =
25×49, que e um numero ımpar. Contradicao. Portanto e impossıvel colocar os numeros
nas casas do tabuleiro de modo que A = B.
Problema 11.3 - (TT - 1984) temos 2000 macas em varias bolsas. Podemos remover
bolsas e/ou remover macas das bolsas.
Prove que e possıvel ter um numero igual de macas em cada uma das bolsas restantes,
sendo o total de macas nao menor do que 100.
Solucao
Suponha o contrario. Assim, o numero total de bolsas restantes nao e mais do que
99, caso contrario, poderıamos deixar 1 maca em cada uma das 100 bolsas e remover as
restantes. Alem disso, o total de bolsas com no mınimo duas macas nao e mais do que
49, o total de bolsas com no mınimo tres macas nao e mais do que 33, etc. Portanto,
o total de macas nao e maior do que 99 + 49 + 33 + · · ·. Existem 94 termos depois dos
cinco primeiros termos , cada um deles sendo menor do que ou igual a 16. Agora
99 + 49 + 33 + 24 + 19 + 94× 16 = 1728 < 2000.
Contradicao. Portanto, e possıvel ter um numero igual de macas em cada uma das bol-
sas restantes, sendo o total de macas nao menor do que 100.
Problema 11.4 - (KMO- 1981) Seja p um numero primo, p > 3. Sabe-se que para um
certo inteiro positivo n o numero pn possui 20 dıgitos, quando escrito na base 10.
Prove que dentre esses dıgitos existem no mınimo tres iguais.
Solucao
Suponha o contrario. Isto e, dentre os 20 dıgitos do numero pn nao existem tres
iguais. Isto significa que um dos dıgitos 0, 1, 2, 3 · · · , 9 e usado na representacao decimal
de pn exatamente duas vezes. Assim, a soma dos dıgitos de pn e igual a
2× (0 + 1 + 2 + · · ·+ 9) = 90.
Logo, pn e divisıvel por 3. Mas, isso e uma contradicao, pois p e um primo maior do
que 3, o que implica que pn nao pode ser divisıvel por 3. Portanto, dentre es dıgitos de
24
pn existem no mınimo tres iguais.
12 Suponha o problema resolvido (ou olhe de tras para
diante).
Uma tatica que pode ser utilizada em jogos ou problemas em que se tem de construir
alguma figura, e supor o problema resolvido. Entao voce podera reverter seus passos e,
portanto, construir uma solucao para o problema original.
Problema 12.1 - Dois amigos, A e B se divertem com o seguinte jogo, em que jogam
alternadamente. O primeiro a jogar, A, escolhe um inteiro qualquer de 1 a 11, inclusive,
e comunica ao segundo jogador, B, a sua escolha e este soma-o a qualquer numero de 1
a 11, inclusive, por ele escolhido, falando o resultado ao primeiro jogador, que o soma a
qualquer numero escolhido de 1 a 11, e assim eles vao jogando, alternadamente, ate que
um deles obtenha o numero 56, vencendo o jogo.
Quem vence: A ou B? Qual e a estrategia para vencer?
Solucao
O jogador A, que comeca, vence.
Na sua penultima jogada, o jogador A tem de deixar para B uma soma menor do que
56 − 11 = 45, para garantir que B nao possa atingir o numero 56. Assim, ele deixa a
soma igual a 44. Na sua jogada imediatamente anterior ele deixa para o jogador B uma
soma menor do que 44 − 11 = 33, para garantir que o jogador B nao possa atingir 44.
Desse modo, as jogadas vencedoras de A sao de tal maneira que os totais atingidos por
eles sejam: 8, 20, 32, 44 e 56.
Problema 12.2 - Dois amigos, A e B, disputam seguinte jogo, em que jogam alterna-
damente, usando um monte com 27 de carocos de feijao. O jogador A comeca. Uma
jogada consiste em retirar 1, 2, 3 ou 4 carocos do monte. O jogo termina quando todos
carocos forem removidos. O vencedor e aquele que possuir um numero par de carocos
quando todos os carocos tiverem sido retirados.
Quem vence: A ou B? Qual a estrategia vencedora?
Solucao
25
(Solucao por David Angell, University of New South Wales, Australia. Fonte: [1]
Descreva a posicao do jogo num momento qualquer por um par:
• (n, I), se existem no monte n carocos de feijao e se o jogador que vai fazer seu
movimento possui um numero ımpar de carocos ou
• (n, P ) se existem no monte n carocos de feijao e se o jogador que vai fazer seu
movimento possui um numero par de carocos.
Dizemos que uma posicao e uma posicao vencedora se o jogador que tem a vez de
jogar pode garantir que vai vencer, nao importando como o outro jogue. Assim, temos:
• (1, I) e uma posicao vencedora, porque o jogador que vai fazer seu movimento retira
o ultimo caroco e fica com um numero par deles.
• (1, P ) e uma posicao perdedora, pois o jogador que vai fazer seu movimento retira
o ultimo caroco e fica com um numero ımpar deles.
• (2, I) e uma posicao vencedora, porque retirando um caroco fica com um numero
par deles e deixa o oponente na posicao (1,P), que e uma posicao perdedora..
• (2, P ) e uma posicao vencedora, pois o jogador que vai fazer seu movimento retira
os dois ultimos carocos e termina com um numero par deles.
• Por razoes analogas, (3, I), (3, P ), (4, I) e (4, P ) sao posicoes vencedoras. Por
exemplo, na posicao (3,P) o oponente possui um numero par de carocos, retirando
dois carocos coloca o oponente na posicao (1, P ), que, como vimos acima, e uma
posicao perdedora.
• (5, I) e uma posicao perdedora, pois o oponente possui um numero ımpar de carocos,
pois qualquer movimento deixa-o em uma das posicoes (4, I) ou (3, I) ou (2, I) ou
(1, I).
• (5, P ) e uma posicao vencedora, porque retirando 4 carocos coloca o oponente na
posicao perdedora (1, P ).
• (6, I) e uma posicao perdedora porque o oponente possui um numero par de carocos,
e qualquer movimento leva-o para uma das posicoes vencedoras (5, P ) ou (4, P ) ou
(3, P ) ou (2, P ).
26
• (6, P ) e uma posicao vencedora, pois retirando 1 caroco coloca o oponente na
posicao perdedora (5, I). Se voce continuar com esse raciocınio, vai descobrir que
agora a situacao se repete: as posicoes vencedoras e perdedoras para n carocos sao
as mesmas que para n − 6 carocos. Por exemplo, se n = 7, entao (n, I) vence e
(n, P ) perde, mesmo para n = 1; se n = 8, entao ambas as posicoes (n, I) e (n, P )
vencem; o mesmo para n = 2, e assim por diante.
Portanto, para n = 27, comecando com um numero par de carocos (0 e um numero par)
e essencialmente o mesmo que a posicao (3, P ) e o primeiro jogador vence retirando dois
carocos.
A estrategia vencedora e simplesmente seguir a tabela de instrucoes dada abaixo. Como
existem realmente somente doze posicoes de (1, I) a (6, P ), e tres delas sao posicoes
perdedoras, segue que nao importa como voce jogue, existem nove posicoes vencedoras
para memorizar. Essas posicoes vencedoras estao na tabela abaixo, onde n (mod 6)
significa o resto quando n e dividido por 6.
n (mod 6) 0 1 2 3 4 5
n Impar nenhum 1(2) 1 3(4) 3 nenhum
n Par 1 nenhum 2(3) 2 4 4
27
13 Problemas Diversos
Problema 13.1 - (AMO) Comecando com um hexagono regular, uma forma geometrica
e gerada em estagios. Na Fase 1, ha um hexagono. Cercando-o completamente, adicio-
nando um hexagono regular congruente ao incial, para cada lado dele exposto, temos que
na Fase 2, existem 7 hexagonos no total. Cercando completamente a nova forma pela
adicao de um hexagono regular, congruentes aos outros, para cada lado exposto, temos
que na Fase 3 existem um total de 19 hexagonos, veja Figura a seguir.
Encontre uma formula para o numero total de hexagono em Fase n.
Solucao
No hexagono inicial, tracamos as tres maiores diagonais e as prolongamos. Elas
cortam a figura em 6 partes congruentes, veja Figura a seguir.
28
Agora, omitindo o hexagono central, observa-se que a quantidae de hexagono em cada
parte congruente e em cada estagio e:
1,
(1
2+ 1 +
1
2
), 3,
(1
2+ 3 +
1
2
), 5,
(1
2+ 5 +
1
2
), 7, · · ·
Isto e, a quantidae de hexagono em cada parte congruente e em cada estagio e:
1, 2, 3, 4, 5, 6, 7, · · · , n− 1 (depois de n estagios)
Portanto, se Tn e o numero de hexagonos no estagio n, temos que
Tn = 6[1+2+3+4+5+ · · ·+(n−1)]+1 =6n(n− 1)
2+1 = 3n(n−1)+1 = 3n2−3n+1.
Problema 13.2 - (CM, 37: No 5 September 2011) Juliette e Philippe disputam um jogo
em que fazem seus movimentos alternadamente. No inıcio do jogo, cada vertice de um
quadrado e coberto por um numero de fichas. Um movimento consiste em cada jogador
escolher um lado do quadrado e retirar de suas extremidades tantas fichas quanto ele
desejar, desde que ele retire pelo menos uma. Nao e necessario retirar o mesmo numero
de fichas de cada extremidade. O jogador que retirar a ultima ficha vence o jogo. No
inıcio do jogo, existem 10 fichas no vertice A, 11 fichas no vertice B, 12 fichas no vertice
C e 13 fichas no vertice D.
Se Juliette comeca, qual e a sua estrategia para vencer?
Solucao
Sejam a, b, c e d o numero de fichas nos vertices A,B,C e D, respectivamente. A
estrategia de Juliette e fazer seus movimentos para ter a = c e b = d.
Se na sua vez de jogar, Philippe recebe um quadrado com a = c e b = d, entao ele
retira no mınimo uma ficha, e nao pode retirar fichas de ambos os extremos de uma
diagonal. Portanto, ele sempre passa para Juliette um quadrado com a 6= c e b 6= d. Se
Juliette recebe um quadrado a 6= c e b 6= d, entao para cada diagonal ela deve escolher a
29
extremidade com maior numero de fichas. Nesse caso, ela deve escolher o lado que liga
essas duas extremidades e retirar fichas ate que a = c e b = d. Assim, ela sempre pode
aplicar essa estrategia e obter a = c = 0 e b = d, vencendo o jogo.
Problema 13.3 - (OMM - 2003) Tem-se cartoes sobre uma mesa de modo que em cada
um deles esta escrito um par de numeros inteiros positivos. Existe exatamente um cartao
para cada par de numeros inteiros, (a, b), com 1 ≤ a < b ≤ 2003. Dois jogadores dis-
putam um jogo, em que jogam alternadamente. Cada movimento corresponde a retirar
um cartao e escrever no quadro-negro o produto ab dos numeros la escritos. O primeiro
jogador que faz com que o Maximo Divisor Comum dos numeros no quadro-negro
seja igual a 1 perde.
Qual dos jogadores tem uma estrategia vencedora: o primeiro ou o segundo a jogar?
Solucao
O primeiro jogador tem uma estrategia vencedora.
Considere os numeros no quadro-negro imediatamente antes do movimento perdedor. O
Maximo Divisor Comum de todos esses numeros deve ser um inteiro d > 1.
Se d nao e um numero primo, entao ele possui algum divisor, k, menor do que ele, de
modo que o cartao com o par (1, k) ainda pode ser retirado. Contradicao, pois o proximo
movimento e perdedor.
Logo, d e um numero primo e todo cartao com um par (a, b), com d dividindo ab deve ter
ja sido retirado. Existem 2002 pares da forma (a, d), pois, pela hipotese do problema, a
pode ser qualquer um dos numeros 1, 2, 3, ..., 2003 exceto d. De maneira analoga, existem
2002 pares da forma (a, 2d), com 2d ≤ 2003. Agora, observe que, deste modo, contamos
duas vez o par (d, 2d). Logo, d tem de ser escolhido de modo que 2d < 2003 < 3d, o que
implica que existem 4003 pares possıveis.
O primeiro jogador pode vencer se ele retira o par (1, 997). Assim, as possıveis jo-
gadas sao (k, 997), para k = 2, 3, 4, ..., 996, 998, ..., 2003 (que sao 2001 possibilidades),
e (k, 1994), para k = 1, 2, 3, ..., 996, 998, 999, ..., 1993, 1995, 1996, ..., 2003 (que sao 2001
possibilidades).
Portanto, existe um numero par de movimentos disponıveis e o primeiro jogador vencera.
Observe que o segundo jogador so pode reduzir o numero de movimentos disponıveis se
ele perder.
Problema 13.4 - (HMITMT - 2003) Num hotel os quartos estao dispostos como um
tabuleiro 2 × 8, estando cada um deles ocupado por umm hospede. Todos os hospedes
estao se sentindo desconfortaveis em seus aposentos, de modo que cada um deles gostaria
30
de passar para um quarto adjacente, horizontal ou verticalmente. Naturalmente, eles po-
dem fazer a mudanca simultaneamente, de tal maneira que cada quarto fique novamente
ocupado com um hospede.
De quantas maneiras distintas podem ser feitos esses movimentos coletivos?
Solucao
Imagine que os quartos sao pintados alternadamente de preto e branco, no estilo de
um tabuleiro de xadrez, veja figura a seguir.
Pela figura, e facil ver que, cada hospede se movimenta de um quarto preto para um
quarto adjacente branco, e vice-versa. Se para um hospede, que inicialmente esta num
quadrado preto, colocamos um domino sobre o quarto antigo e o novo, obtemos uma
pintura do tabuleiro do tipo 2 × n, formada por n dominos, pois cada quadrado preto
e usado uma vez e cada quadrado branco e usado uma vez. Aplicando procedimento
analogo para cada hospede que inicialmente esta num quarto branco e se movimenta
para um quadrado preto, obtemos uma segunda pintura para o tabuleiro. Inversamente,
e facil verificar que, para qualquer par de quadrados dessas pinturas, determina um
padrao de movimento. Tambem e facil provar por inducao que o numero de pinturas do
tipo dominos de um tabuleiro de dimensoes 2× n e (n+ 1)-esimo numero de Fibonacci.
Isto e facil de ver para os casos de n = 1, 2 e para um retangulo 2 × n, onde os dois
quadrados mais a direita pertencem a um domino vertical ou deixam um retangulo de
dimensao 2× (n−1) ser pintado arbitrariamente, ou dois dominos ocupam quadradados
adjacentes, deixando um retangulo de dimensao 2 × (n − 2) ser pintado livremente.
Portanto, o numero de pinturas possıveis e o numero de Fibonacci.
Deste modo, o numero de pinturas de um tabuleiro de dimensao 2× 8 e 34, e o numero
possıvel de pares de tais pinturas e igual a 342 = 1156, que e a resposta ao problema.
Problema 13.5 - (HMITMT - 2002) Sem levar em consideracao a ordem das parcelas,
de quantas maneiras podemos expressar 2002 como soma de 3 inteiros positivos?
31
(Consideramos 2 + 1000 + 1000 e 1000 + 2 + 1000 como sendo a mesma forma de
expressar 2002 como soma de 3 inteiros positivos)
Solucao
Sejam a, b e c tres numeros positivos para os quais a+ b+ c = 2002. Para facilitar o
entendimento e evitar redundancia, vamos supor que a ≤ b ≤ c. Observe que, para cada
escolha de a e b, existe uma unica escolha para c, pois c = 2002− (a+ b). Agora, vamos
contar todas as possibilidades para a e b considerando dois casos:
Caso 1 O numero a e par.
Caso 2 O numero a e ımpar.
Suponha que o numero a do terno procurado seja um numero par. Neste caso, para
cada valor de a, terıamos b = c = 2002−a2 , que e um numero inteiro. Com isso, terıamos
a+ 2002−a2 + 2002−a
2 = 2002, satisfazendo ao problema. Observe que, para b = 2002−a2 ≥ a,
segue que 2002− a ≥ 2a, que e o mesmo que a ≤ 667. Como a e um numero par, temos
2 ≤ a ≤ 666.
Para cada valor de a, existem (2002−a2 − a+ 1) valores para b. Ou seja, para cada valor
de a, existem 2002−a−2a+22 = 1002− 3a
2 valores para b.
Agora, se a = 2, temos 1002−3×22 = 999 valores para b. Se a = 4, temos 2002−3×4
2 = 996
valores para b. Se a = 6, temos 2002 − 3×62 = 993 valores para b, e assim por diante
ate a = 666, que nos da 2002 − 3×6662 = 3 valores para b. Para calcular a quantidade
de todos os numeros a, b, c possıveis, quando a e um numero par, somamos os numeros
obtidos anteriormente, que formam uma progressao aritmetica. Isto e, a quantidade de
valores possıveis para os ternos de numero a, b, c, com a par, satisfazendo ao problema
e igual a: 999 + 996 + 993 + ...+ 3 = 999+32 × 333 = 501× 333 = 166833.
Seja a um numero ımpar. Neste caso, para cada valor de a, existem [ (2002−(a+1)2 −a+1] =
[ (2002−a−1−2a+22 ] = [2000−3(a−1)
2 ] = 1000− [3(a−1)2 ] possıveis valores para o numero b.
Como dado o numero a, tem-se: b = 2002−(a+1)2 ≥ a, segue que 2002− (a+ 1) ≥ a, que
e o mesmo que a ≤ 667. Como a e um numero ımpar positivo, temos 1 ≤ a ≤ 667.
Agora, se a = 1, temos que existem 1000 − 3×(1−1)2 = 1000 valores possıveis para b.
Se a = 3, existem 1000 − 3×(3−1)2 = 997 valores possıveis para b. Se a = 5, existem
1000 − 3×(5−1)2 = 994 valores possıveis para b, e assim por diante ate a = 667, que nos
da 1000 − 3×(667−1)2 = 1 valor possıvel para b. Para calcular a quantidade de todos os
numeros a, b, c possıveis, quando a e um numero ımpar, somamos os numeros obtidos
anteriormente, que formam uma progressao aritmetica. Isto e, a quantidade de valores
possıveis para os ternos de numero a, b, c, com a ımpar, satisfazendo ao problema e igual
a: 1000 + 997 + 994 + ...+ 1 = (1000+12 × 334 = 1001× 167 = 167167.
32
Portanto, existem 166833 + 167167 = 334000 possıveis arranjos dos numeros inteiros
positivos a, b, c satisfazendo ao problema.
Problema 13.6 - (TT - 2012) Um tesouro esta enterrado num tabuleiro de xadrez
8× 8. Em cada uma das casas do tabuleiro existe enterrado uma mensagem que indica
o numero mınimo de passos que se necessita para chegar a casa do tesouro. Necessita-se
de um passo para se mover de uma casa para a casa vizinha, que e uma que tem um lado
comum com a casa de partida.
Determine o numero mınimo de casas que se deve escavar para chegar com certeza ao
tesouro.
Solucao
Se escolhemos uma casa qualquer para escavar, nao ha nenhuma garantia de que o
tesouro esteja la. Se a mensagem retirada diz que o tesouro esta num outro quadrado,
nao e possıvel determinar a exata localizacao dele fazendo uma so escavacao. Vamos
provar que, para encontrar o tesouro, temos que escavar duas casas.
Numeramos as linhas do tabuleiro 8 × 8, de baixo para cima, de 1 a 8 e as colunas,
da esquerda para a direita, de 1 a 8. Assim, cada casa do tabuleiro e perfeitamente
identificada por um par de numeros (b, c), veja figura a seguir.
Escavamos as casas (1, 1) e (8, 1). Sejam a e b, respectivamente, os numeros que encon-
tramos apos escavarmos as duas casas. Cada um desses numeros representa o compri-
mento do caminho mınimo que devemos fazer da casa escavada ate o tesouro. Podemos
imaginar, sem perda de generalidade, que o caminho mınimo realiza primeiro todos os
movimentos verticais necessarios em seguida e, apos isso, os movimentos horizontais ate
atingir o tesouro.
Vamos supor que o tesouro esteja na casa (i, j) do tabuleiro. Os caminhos mınimos para
33
se atingir o tesouro, a partir das casas escavadas, sao de dois tipos:
Tipo (I) - aquele que comeca na casa (1, 1), vai ate a casa (1, j) e daı ate a casa (i, j).
Tipo (II) - aquele que comeca na casa (8, 1), vai ate a casa (8, j) e daı ate a casa (i, j).
Deste modo, sejam V1 e H1 a quantidade de movimentos verticais e horizontais, res-
pectivamente, a partir da casa (1, 1) ate chegar ao tesouro e V2 e H2 a quantidade de
movimentosos verticais e horizntias a partir da casa (8, 1) ate chegar ao tesouro. Desse
modo, temos que:{V1 +H1 = a
V2 +H2 = bPelo que indicamos acima, os movimentos horizontais dos dois caminhos sao os mes-
mos, i. e. H1 = H2, e a diferenca | a − b | e igual a diferenca entre os comprimentos
dos movimentos verticais dos dois caminhos. Alem disso, a soma dos comprimentos dos
dois movimentos verticais e igual a V1 + V2 = 7.
Portanto, supondo a ≥ b, teremos um sistema de equacoes lineares 2× 2:{V1 − V2 = a− bV1 + V2 = b
.
Este sistema tem solucao unica, o que determina exatamente a posicao do tesouro.
Para ilustrar, considere o tabuleiro a seguir com o numero obtido com a escavacao em
cada casa e o local do tesouro.
Quando escavamos a casa (1, 1) obtemos o numero a = 9. Isto e, o caminho mınimo
de (1, 1) ate o tesouro tem comprimento 9. Quando escavamos a casa (8, 1) obtemos o
numero b = 8. Ou seja, o caminho mınimo de (8, 1) ate o tesouro tem comprimento 8.
Para se mover da casa (1, 1) ate o tesouro, casa (5, 6), temos que fazer um movimento
vertical ate a casa (5, 1) e de la fazemos um movimento horizontal ate a casa (5, 6). Alem
disso, a diferenca 9− 8 = 1. Logo, temos que encontrar dois numeros cuja soma seja 7
e cuja diferenca seja 1. Os unicos numeros que satisfazem sao 3 e 4. Portanto, de (1, 1)
temos que descer 3 casas e, de (8, 1), mover para cima 4 casas. Como o comprimento do
34
caminho mınimo de (1, 1) ate o tesouro e 9, temos que andar 5 casas horizontalmente.
Portanto, o tesouro esta na casa (5, 6).
Problema 13.7 - (LMO - 1987) Num tabuleiro 8 × 8 comum, com as casas pintadas
alternadamente de preto e branco, um movimento permitido e trocar de posicao quais-
quer duas linhas ou colunas.
Aplicando uma sequencia de tais movimentos, e possıvel obter um tabuleiro onde a me-
tade a esquerda seja totalmente formada por casas pretas e a metade a direita seja
formada inteiramente por casas brancas?
Solucao
Observe que, em qualquer movimento permitido, nao se altera o numero de quadrados
pretos numa coluna do tabuleiro, que inicialmente e quatro. Logo, nunca obteremos uma
coluna consistindo de oito quadrados pretos. Portanto, e impossıvel obter um tabuleiro
onde a metade a esquerda seja totalmente formada por casas pretas e a metade a direita
seja formada inteiramente por casas brancas.
Problema 13.8 - (OIM - 2000) Um magico tem cem cartoes numerados de 1 a 100.
Ele coloca os cartoes em tres caixas, uma vermelha, uma branca, uma azul, de tal modo
que cada caixa contem no mınimo um cartao. Uma pessoa da plateia escolhe duas dessas
caixas e retira cartoes de cada uma delas. Em seguida, revela a soma dos numeros da-
queles cartoes. Dada esta informacao, o magico localiza a caixa da qual nenhum cartao
foi retirado.
De quantas maneiras o magico pode repartir os cartoes nas caixas de modo que ele possa
sempre executar seu truqie com exito?
(Duas maneiras de repartir os cartoes sao consideradas distintas se ao menos um cartao
e colocado em duas caixas diferentes)
Solucao
A resposta e 12.
Vamos chamar, respectivamente, de r, w, b as cores das caixas vermelha, branca, azul.
Vamos dizer que a cor do numero i seja a da cor da caixa em que ele se encontra e todo
numero considerado esteja no conjunto {1, 2, 3, · · · , 100}.Para que o truque funcione, sempre que x + y = z + t e os cartoes de numeros x e y
estejam em casas distintas, entao ou z e t estao nestas mesmas caixas ou ambos estao
na caixa restante. Isso significa dizaer que, nenhum par de numero de cores distintas
35
tem a mesma soma que outros dois em caixas distintas.
Consideramos dois casos:
Caso 1: Suponhamos que existe uma caixa tal que os cartoes numerados com i, i+1, i+2
sao de cores distintas, digamos vermelho (r), branco (w), azul (b), respectivamente.
Questao: Em que caixa esta o cartao de numero i+ 3?
Esta na caixa vermelha. De fato, como i︸︷︷︸r
+ (i+ 3)︸ ︷︷ ︸?
= (i+ 1)︸ ︷︷ ︸w
+ (i+ 2)︸ ︷︷ ︸b
, para que o
truque funcione, (i+ 3) tem de ser vermelho (r).
De modo analogo, como (i+ 4)︸ ︷︷ ︸?
+ (i+ 1)︸ ︷︷ ︸w
= (i+ 3)︸ ︷︷ ︸r
+ (i+ 2)︸ ︷︷ ︸b
, para que o truque funcione,
segue que (i+ 4) e branco (w). Do mesmo modo, como (i− 1)︸ ︷︷ ︸?
+ (i+ 2)︸ ︷︷ ︸b
= (i)︸︷︷︸r
+ (i+ 1)︸ ︷︷ ︸w
,
segue que (i− 1) e branco (w)
Com isso, concluımos que tres cores vizinha distintas determinam a cor do proximo
numero. Alem disso, este processo se repete: rwb e seguido por r, w, b e assim por di-
ante. Este processo tambem funciona inversamente: rwb e precedido por b, e assim por
diante.
Logo, e suficiente definir as cores dos cartoes numerados com 1, 2, 3, que pode ser feito
de 6 modos distintos. Todos esses arranjos sao tais que as somas dos numeros vermelhos
e azuis, dos numeros brancos e azuis, e dos numeros vermelhos e azuis, sao restos dis-
tintos modulo 3. Isto e, a primeira caixa comtem os cartoe de numeros 1, 4, 7, · · · , 100,
a segunda caixa contem os de numeros 2, 5, 8, · · · , 98 e a terceira contem 3, 6, 9, · · · , 99
Caso 2: Suponhamos que nao existem tres cartoes com numeros consecutivos em caixas
distintas. Sem perda de generalidade, suponhamos que o numero 1 seja vermelho (r).
Agora, seja i o maior numero que nao e vermelho. Vamos supor que i seja branco. Seja
k o menor numero azul. Como, por hipotese, nao existe tres numeros consecutivos de
cores distintas, rwb, temos necessariamente que (i+ 1) < k.
Suponhamos que k < 100. Como i︸︷︷︸w
+ k︸︷︷︸b
= (i− 1)︸ ︷︷ ︸r
+ (k + 1)︸ ︷︷ ︸?
, segue que (k + 1) e
vermelho (r). No entanto, como i︸︷︷︸w
+ (k + 1)︸ ︷︷ ︸r
= (i+ 1)︸ ︷︷ ︸?
+ k︸︷︷︸b
, segue que (i + 1) deve
ser azul b, o que contradiz o fato de que k e o menor numero azul. Logo, k = 100.
Do mesmo modo, como (i− 1)︸ ︷︷ ︸r
+ 100︸︷︷︸b
= i︸︷︷︸w
+ 99︸︷︷︸?
, segue que 99 e branco.
Se t e um numero inteiro, com t > 1 e o cartao numerado com t esteja na caixa ver-
melha (r), como t︸︷︷︸r
+ 99︸︷︷︸w
= (t− 1)︸ ︷︷ ︸?
+ 100︸︷︷︸b
, temos que (t − 1) e azul (b), segue que o
menor numero azul e 100. Portanto, a pintura dos numeros e feita do seguinte modo:
36
rww · · ·wwb.Deste modo, se a soma e maior do que ou igual a 100, entao a caixa restante e azul;
se a soma e 101, a caixa restante e branca; e se a soma e maior do que 101, a caixa
restante e vermelha. Ou seja, uma caixa contem o cartao com numero 1, uma outra
caixa contem os cartoes com os numeros 2, 3, 4, · · · , 99 e a outra caixa contem somente
o cartao com numero 100. O numero de tais arranjos e 6.
Portanto, a resposta ao problema e 6 + 6 = 12.
Problema 13.9 - (OIM - 1986) Provar ou de um contra-exemplo: Dado um conjunto
finito de pontos no plano com coordenadas inteiras, e possıvel pintar de vermelho alguns
destes pontos e os restantes de branco de tal forma que para qualquer reta L paralela a
um dos eixos coordenados, o numero de pontos vermelhos e o numero de pontos brancos
sobre L diferem por no maximo 1.
Solucao
A resposta e sim.
Sejam P1, P2, P3, · · · , Pn pontos sobre uma reta l paralela a um eixo, contados da esquerda
para a direita e de cima para baixo. Desenhamos segmentos juntando P1 a P2, P3 a
P4, · · ·. De um modo geral, tracamos um segmento juntando os pontos P2i−1 a P2i.
Feito isso para toda dessas retas l, obtemos uma algumas linhas poligonais. Se uma
dessas poligonais e fechada, significa que ela forma um poligono com um numero par
de vertices. Agora, pintamos os vertices dessa poligonal alternadamente de vermelho e
branco. Um ponto que nao esteja sobre a poligonal pode ser pintado de forma arbitraria.
A pintura obtida satisfaz ao problema.
Problema 13.10 - (LMO - 1989) Dadas 32 pedras de pesos distintos, prove que 35
pesagens num balanca de dois pratos sao suficiente para determinar quais sao as duas
pedras mais pesadas.
Solucao
Inicialmente, dividimos as 32 pedras em 16 pares e, fazendo 16 pesagens, separamos
o conjunto das 16 pedras mais pesadas. Agora, dividimos as 16 pedras mais pesadas em
pares e, com 8 pesagens, determinamos as 8 mais pesadas dentre as 16 mais pesadas.
Repetindo o processo, dividimos as 8 pedras mais pesadas em pares e, com quatro pesa-
gens, encontramos a 4 mais pesadas. Repetindo o processo, podemos determinar a mais
pesada das pedras depois de 16 + 8 + 4 + 2 + 1 = 31 pesagens.
37
Durante as pesagens, a segunda pedra com mais peso so poderia ser eliminada pela pedra
mais pesada. Nesse momento, voce conhece a pedra mais pesada e as 6 mais pesadas.
Agora, fique so com as 5 mais pesadas. Extraia as 5 pedras que foram pesadas contra
a pedra mais pesada durante as pesagens. Nesse momento, e facil de encontrar a mais
pesado dessas 5 pedras em apenas 4 pesagens sucessivas, fazendo a pesagem duas a duas
e eliminando a mais leve.
Problema 13.11 - (SAMO - 1996) Um polıgono convexo possui 2n lados. Prove que
o polıgono contem no mınimo n diagonais que nao sao paralelas a qualquer um de seus
lados.
Solucao
Como o polıgono possui 2n lados, ele possui 2n.(2n−3)2 = n(2n− 3) diagonais. Agora,
observe que, para cada lado, existem no maximo (n− 2) diagonais paralelas a ele. Deste
modo, existem no maximo 2n(n − 2) diagonais paralelas a algum lado. Portanto, exis-
tem no mınimo n(2n−3)−2n(n−2) = n diagonais que nao sao paralelas a qualquer lado.
Problema 13.12 - Na decada de 1960, tinha um programa semanal de televisao muito
popular nos Estados Unidos chamado ”Let’s Make a Deal”(”Vamos fazer um acordo”).
A cada semana, em um determinado momento no programa, o apresentador, Monty
Hall, apresentava ao competidor tres portas fechadas.
Atras de uma das portas, havia um premio substancial (um carro) e atras das outras,
nao havia nada substancial (vamos imaginar que tivesse um bode). O apresentador,
Monty Hall, pedia que o participante escolhesse uma das porta. Claramente, a chance
de o competidor escolher a porta com o premio era de 1 em 3. Para causar impacto aos
telespectadores, em vez de simplesmente abrir a porta escolhida para revelar o que esta
por tras, o apresentador, Monty Hall, abria uma das duas portas que o competidor nao
tinha escolhido, revelando que ela nao escondia o premio (e sim um bode).
38
E claro que o apresentador sabia onde o premio estava, por isso ele podia fazer isso. Ele
entao oferecia ao competidor a oportunidade de mudar sua escolha para a outra porta
que, naquela momento, permanecia fechada.
Qual e a estrategia mais logica, ficar com a porta escolhida inicialmente ou mudar de
porta? Com qual das duas portas ainda fechadas o concorrente tem mais probabilidades
de ganhar? Por que?
Solucao 1
Existem tres portas: A, B e C. Quando o competidor escolheu uma delas, digamos a
A, a chance de que ela seja a premiada e de 1/3. Como consequencia, a probabilidade
de que tenha errado, ou em outras palavras, de que o premio esteja nas outras duas
portas B ou C e de 2/3. Pode-se comprovar isso somando a probabilidade de cada uma
das outras portas ou simplesmente sabendo que a probabilidade de que haja um premio
e sempre 1. O importante e ter em mente que a chance de o premio estar nas outras
portas que ele nao escolheu e de 2/3. Entendendo isso, basta ver que o apresentador
abrira sem erro uma dessas outras duas portas que contem um bode, digamos que seja
a B. Ao fazer isso, ele esta dando uma informacao valiosa: se o premio estava nas
outras portas que nao escolheu (B ou C), entao agora ele so pode estar na porta que o
compettidor nao escolheu e nao foi aberta, ou seja, a porta C. Ou seja, se o competidor
errou ao escolher uma porta - e as chances disto sao de 2/3 - entao ao abrir uma das
outras portas nao-premiadas o apresentador esta lhe dizendo onde esta o premio. Toda
vez que o competidor tiver escolhido inicialmente uma porta errada, ao trocar de porta
ira com certeza ganhar. Como as chances de que tenha errado em sua escolha inicial
sao de 2/3, se trocar suas chances de ganhar serao de 2/3 - e por conseguinte a chance
de que ganhe se nao trocar de porta e de apenas 1/3. E assim mais vantajoso trocar de
porta.
Solucao 2
Suponha que, em vez de 3 houvessem 1000 portas, numeradas de 1 a 1000, e o
competidor escolheu a porta de numero 1000.
Todos as portas contem um bode, exceto uma, aquela que tem o carro.
39
Quando o competidor escolhe uma porta, em seguida, Monty Hall abre todas as outras
portas, exceto uma... e da a oportunidade para o competidor mudar a escolha para a
outra porta. Se fosse voce, mudaria? E possıvel um pensamento do tipo ”Escolhi a porta
correta no meu primeiro palpite.”Mas, qual e a probabilidade de que isso fosse verdade?
Resposta: 11000 ... Ha uma chance de 999 de que o carro nao esta atras da porta que o
competidor escolheu. E se o carro nao esta atras da porta que o competidor escolheu, ele
deve estar por tras da ultima porta que Monty deixou sem abrir. Em outras palavras,
Monty ajudou, deixando uma porta para que o competidor mude, que tem uma chance
de 999 de ter o carro por tras dela. Entao nesse caso, se voce mudar, voce teria uma
chance de 9991000 de ganhar o carro. Portanto, e melhor mudar.
Problema 13.13 - Dois jogadores, A e B, disputam um jogo em que jogam alterna-
damente. Uma jogada de A e escolher um ponto do plano, que nao esteja pintado, e
pinta-lo de vermelho. Uma jogada de B e escolher 10 pontos do plano, que nao estejam
pintados, e pinta-los de verde. O jogador A vence se existem tres pontos vermelhos que
sejam vertices de um triangulo equilatero.
O jogador B pode impedir do jogador A de vencer a partida?
Solucao
A resposta e nao.
O primeiro jogador, A, pode sempre vencer, nao importa como o jogador B jogue. Para
isso, em suas n primeiras jogadas ele escolhe pintar de vermelho pontos sobre uma
mesma reta. Agora, observe que para cada par destes n pontos existem dois pontos, um
de cada lada da reta, que o segundo jogador, B, tem de pintar de verde, para evitar que o
jogador A venca. O numeros de tais pontos e igual a 2×(n2
). Por outro lado, o jogador
B pode pintar no maximo 10n pontos de verde. Agora, 2×(n2
)> 10n, que e o mesmo que
n(n − 1) > 10n. Ou seja, n − 1 > 10. Portanto, o primeiro jogador vence no seu 12o
movimento.
Problema 13.14 - Ana e Celia disputam o jogo seguinte, em que jogam alternada-
mente. Ana deve pintar, ou de azul ou de vermelho, cada ponto que esteja sobre um
dado cırculo. Celia deve escolher tres dos pontos pintados de modo que eles determinem
um triangulo cujas medidas de seus angulos internos sejam 30, 50 e 100 graus, respec-
tivamente. Celia vence se esse triangulo possui os vertices de mesma cor. Ana vence se
Celia nao consegue fazer a escolha.
40
Quem vence: Ana ou Celia?
Solucao
Ana vence.
Basta ela marcar 6 pontos sobre o cırculo, de modo que este fique dividido em seis arcos
de mesmo comprimento. Agora ela pinta alternadamente de azul e vermelho cada um
dos arcos, de forma consecutiva, tendo o cuidado de pintar em cada arco o ponto inicial
da cor do arco, mas deixar o ponto final com a cor do proximo arco. Quando Celia qui-
ser escolher os vertices de seu triangulo, os extremos do lado oposto ao angulo de 600,
ela deve determinar um arco de 600 sobre o cırculo. Pela pintura feita, estes extremos
devem necessariamente possuir cores distintas.
Problema 13.15 - Numa caixa, temos 25 fichas iguais, numeradas de 1 ate 25. Voce
pode retirar da caixa uma ficha por vez, sem reposicao, e pode continuar a retirar fichas
ate que o produto de dois numeros de duas fichas retiradas seja um quadrado perfeito.
Qual e o numero mınimo de fichas que voce deve retirar para ter certeza de obter um
par de fichas cujo produto e um quadrado perfeito?
Solucao
Seja S = {1, 2, 3, ..., 24, 25}. Partimos o conjunto S em subconjuntos disjuntos com
as seguintes duas propriedades:
(i) o produto de quaisquer dois elementos de um subconjunto e um quadrado perfeito;
(ii) o produto de quaisquer dois elementos escolhidos em subconjuntos distintos nao e
um quadrado perfeito. Assim, escrevemos:
S = {1, 4, 9, 16, 25} ∪ {2, 8, 18} ∪ {3, 12} ∪ {5, 20} ∪ {6, 24} ∪ {7} ∪ {10}∪
∪{11} ∪ {13} ∪ {14} ∪ {15} ∪ {17} ∪ {19} ∪ {21} ∪ {22} ∪ {23}
.
Ou seja, partimos o conjunto S em 16 subconjuntos disjuntos. Se escolhermos uma
ficha de cada um dos subconjuntos nao teremos obtido um par de fichas satisfazendo ao
problema. Mas, com mais uma ficha vamos obter um par de fichas cujo produto e um
quadrado perfeito. Portanto, a resposta e 16 + 1 = 17.
Problema 13.16 - Dois jogadores, A e B, disputam um jogo, em que jogam alter-
nadamente. Inicialmente, escreve-se no quadro-negro o numero natural 2. Uma jogada
41
consiste em somar ao ultimo numero, n, no quadro-negro um divisor proprio de n. Quem
atingir um numero maior do que ou igual 2010 vence. O jogador A comeca o jogo.
Quem vence, A ou B? Qual e a estrategia para vencer?
Solucao
O jogador A possui uma estrategia vencedora.
A estrategia do jogador A consiste em jogar deixando para seu adversario sempre um
numero ımpar. Observe que um divisor proprio de um numero ımpar e no maximo um
terco daquele numero, pois o menor divisor deste numero e 3. Deste modo, o jogador B
so pode somar no maximo 13 do ultimo numero escrito no quadro-negro.
Toda vez que o jogador B vai jogar, encontra um numero ımpar e soma a ele um divi-
sor dele, que e ımpar tambem, resultando sempre num numero par. O jogador A por
sua vez soma sempre um divisor de um numero par. Assim, ele pode jogar a metade
deste numero e prossegue assim ate obter pela primeira vez um numero maior do que
ou igual a 1340. Uma vez obtido esse numero x, o jogador A soma a ele sua metade,
atingindo entao um numero maior do que 2010. (Observe que: x+x2 ≥ 2010⇒ x ≥ 1340).
Problema 13.17 - Dois jogadores, A e B, disputam o seguinte jogo, em que jogam
alternadamente. Escrevem-se no quadro-negro uma sequencia de 49 numeros inteiros
consecutivos quaisquer. Uma jogada consiste em apagar um desses numeros. No final,
restam somente dois numeros: a e b. O jogador A ganha se MDC(a, b) = 1 e B ganha
se MDC(a, b) > 1. O jogador A comeca o jogo.
(a) Quem ganha: A ou B? Qual a estrategia para vencer?
(b) Se, em vez de 49 numeros inteiros consecutivos fossem 50, quem ganha: A ou B?
Qual a estrategia para vencer?
Solucao
(a) O jogador A ganha.
Como a quantidade de inteiros e ımpar, o jogador divide os 49 primeiros numeros em
pares de inteiros sucessivos, deixando o numero final sozinho. Ele inicia apagando o
numero que ficou sozinho. Se o jogador B apaga qualquer numero de um par, entao A
apaga o outro. O que sobra no final e um par (n, n+ 1), com MDC(n, n+ 1) = 1.
(b) O jogador B ganha.
A estrategia do jogador B e apagar todos os numeros ımpares, deixando dois numeros
ımpares multiplos de 3. Por sua vez, o jogador A sempre apaga um numero par. Antes
da penultima jogada restam quatro numeros no quadro-negro: dois numeros pares, p e q,
42
e dois numeros ımpares, i e j. Se A apagar um numero ımpar, entao B apaga o outro
numero ımpar, restando os dois numeros pares. Se A apaga um dos numeros pares,
entao B apaga o outro numero par, restando i e j, com MDC(i, j) ≥ 3.
Problema 13.18 - Todo membro de uma sequencia de numeros, a partir do segundo,
e igual a soma do termo precedente com a soma de seus dıgitos. O primeiro numero da
sequencia e 1.
Diga, justificando, se o numero 2010 pertence a sequencia.
Solucao
A resposta e nao.
Seja (a1, a2, a3, a4, · · · a sequencia de numeros. Observe que:
a1 = 1,
a2 = 2 = 3.0 + 2,
a3 = 4 = 3.1 + 1,
a4 = 8 = 3.2 + 2,
a5 = 16 = 3.5 + 1,
a6 = 23 = 3.7 + 2,
a7 = 28 = 3.9 + 1,
· · · · · · · · · · · · · · ·
Para cada inteiro m, seja S(m) a soma dos dıgitos de m. Sabe-se que, na divisao por
3,os numeros m e S(m) deixam o mesmo resto. Observando os numeros da sequencia
encontrados acima, temos que os restos da divisao por 3 dos termos da sequencia sao
alternadamente 1 e 2. De fato, se an = 3k+1, com k inteiro, entao an+1 = an+S(an) =
(3k + 1) + (3q + 1) = 3j + 2, onde q e j sao numeros inteiros inteiros.
Se an = 3k+ 2, com k inteiro, entao an+1 = an + S(an) = (3k+ 2) + (3q+ 2) = 3j + 1,
onde q e j sao numeros inteiros.
Deste modo, de fato o resto da divisao dos termos da sequencia por 3 e ou 1 ou 2. Mas,
2010 deixa resto zero na divisao por 3. Portanto, 2010 nao aparece na sequencia.
43
Problema 13.19 - (CRUX) No aniversario de Maria, Jose quer dar-lhe um presente
e, para isso, propoe o jogo seguinte, no qual eles jogam alternadamente. Ele escreve
no quadro-negro os numeros inteiros 0, 1, 2, 3, 4, ...., 255, 256. Maria comeca o jogo. Ela
escolhe 27 dos numeros escritos e apaga-os. Jose escolhe 26 numeros dentre o que sobra-
ram e apaga-os. Em seguida, Maria escolhe 25 dentre os numeros restantes a apaga-os.
E eles prosseguem assim ate que Jose escolhe 20 = 1 numero e apaga-o. Como sao
apagados 27 + 26 + 25 + 24 + ....+ 21 + 20 = 281 = 255 numeros, restam dois numeros,
a e b, no quadro-negro, Jose paga para Maria uma quantia, em reais, correspondente ao
valor |a− b|.Se os jogadores fazem sempre suas melhores jogadas, qual e o maior valor que Maria
tem certeza que ganha?
Solucao
Maria ganha no maximo 24 ou 216 reais.
A estrategia de Maria e apagar sempre os numeros que estao nas posicoes pares. Com
isso, ela aumenta a distancia entre eles, aumentando o valor de |a − b|. Depois das
jogadas de numeros 1, 2, 3 e 4, a distancia entre os numeros vizinhos, que estao ainda
escritos no quadro-negro, e 2, 4, 6, 8 e 16, respectivamente, o que garante a Maria receber
o maximo possıvel, independente de como Jose joga.
Problema 13.20 - (RP) Daniel tem uma balanca de dois pratos e dez pedras cujos pe-
sos sao todos numeros inteiros entre 1 ate 10, inclusive. Ele quer colocar algumas pedras
na balanca de tal forma que os pratos fiquem equilibrados.
(a) Determine qual e o maior e o menor numero de pedras que pode colocar. Justifique
por que e o maior e mostre um exemplo.
(b) Determine a maior quantidade de pedras que se pode colocar se em cada prato se
deve haver a mesma quantidade de pedras.
Solucao
(a) E impossıvel colocar 10 pedras, pois 1+2+3+4+5+6+7+8+9+10 = 55, que e
um numero ımpar e nao pode ser dividido como soma de dois inteiros iguais. Nove pedras
podem ser usadas, basta retirar uma pedra cujo peso e um numero ımpar. Por exemplo,
se retirarmos a pedra 1, podemos colocar num dos pratos as pedras 8 + 9 + 10 = 27 e no
outro prato as pedras 2 + 3 + 4 + 5 + 6 + 7 = 27.
(b) O maximo possıvel de pedras que podemos usar e 8. Por exemplo, descartamos as pe-
dras 9 e 10 e usamos 1+4+5+8 = 18 num dos pratos e 2+3+6+7 = 18 no outro prato.
44
Problema 13.21 - (OMP) Um motorista planeja uma viagem que vai passar por um
trecho de 800 km no deserto, que nao possui postos para abastecer. Ele sabe que seu
carro so pode armazenar 50 litros de gasolina e tem um rendimento de 10 km por li-
tro. O motorista pode deixar gasolina armazenada em barris, no costado da rodovia, em
pontos distintos dessa regiao desertica. Por exemplo, com o tanque cheio com 50 litros
de gasolina ele pode percorrer 100 km, deixar armazenado 30 litros no ponto que chegou
e voltar ao ponto de partida para reabastecer o tanque de gasolina. O motorista decide
realizar a viagem e chega ao primeiro posto antes do deserto com tanque vazio.
Pode o motorista atravessar o deserto se neste primeiro posto de abastecimento antes do
deserto a oferta total de gasolina e de 140 litros? E se fosse 180 litros?
Solucao
Com a oferta de 140 litros nao e possıvel o motorista atravessar o deserto.
Para atravessar o deserto se necessita armazenar gasolina no quilometro 300 ou mais
adiante, caso contrario, se percorreria mais de 500 km sem abastecer, o que e impossıvel,
pois a autonomia do carro e de no maximo 500 km. Chamemos este ponto de deposito
de combustıvel de P . Para armazenar gasolina em P o motorista tem de percorrer
pelo menos duas vezes a distancia do primeiro posto ao ponto P , que e pelo menos
2 × 300 km = 600 km. Como a distancia a ser percorrida e de 800 km, vemos que e
impossıvel atravessar o deserto com uma oferta menor do que 140 litros. Por outro lado,
nao se pode atravessar o deserto com uma oferta exatamente igual a 140 litros, simples-
mente porque e impossıvel armazenar gasolina em P e voltar com esta quantidade.
Com 180 litros e possıvel atravessar o deserto seguindo o seguinte roteiro:
(a) O motorista faz tres viagens para armazenar gasolina no ponto P , situado a 50 km
da partida, armazenando 40 litros em cada uma das viagens;
(b) Apos estas tres viagens, abastece o tanque no primeiro posto com 30 litros, volta ao
ponto P , chegando com 25 litros;
(c) Do ponto P , avanca duas vezes a um ponto Q a 100 km dele, armazenando ali 30
litros em cada viagem;
(d) De volta ao ponto P abastece com 45 litros que estao armazenados ali e segue ate o
ponto Q com 35 litros de gasolina;
(e) A partir de Q, chegando num ponto R, armazenando ali 20 litros de gasolina e volta
ao ponto Q;
(f) Abastece os 45 litros de gasolina restantes em Q, avanca ate R, chegando com 30
45
litros, abastece ali com os 20 litros existentes no local e completa a viagem.
46
14 Legenda
• AMO - Australian Mathematical Olympiad
• AUMO - All Union Mathematical (URRS)
• BW - Baltic Way Mathematical Contest
• CMO - Canadian Mathematical Olympiad
• CRUX - Crux Mathematicorum (Revista de resolucao de problemas - Canada)
• HMITMT - Havard-MIT Mathematics Tournaments
• IMO - International Mathematical Olympiad
• KMO - Kiev Math Olympiad
• LMO - Lenigrad Mathematical Olympiad
• OMM - Olimpiada Mexicana de Matematica
• OMP - Olimpiada de Matematica do Peru
• RP - Olimpiada Rioplatense de Matematica
• SAMO - South African Mathematics Olympiad
• TT - Tournament of the Tows
47
15 Bibliografia
1. ANGEL, D - http://math.stackexchange.com/questions/731193/how-to-win-this-
game
2. EWING, J. - Paul Halmos: In his own words. Notice of AMS. Vol. 54 . Number
9. October 2007.
3. GUZMAN, O. M. - Aventuras Matematicas. Gradiva. Lisboa. 1990.
4. MARTIN, J. E. - Resolucion de Problemas Matematicos (Vol 3). Centro de Pro-
fessores y Recursos. Salamanca. 1999. (Em PDF)
5. POSAMENTIER, A.S.; WOLFGANG, S - The Art of Problem Solving. Corwin
Press. Thousand Oaks. 1996.
6. POSAMENTIER, A.S. - The Art of Solving Problems. Vienna 2-06 (Em PPT)
7. POSAMENTIER, A.S. - Problem Solving in Mathematics - Grade 3-6 Powerful
Strategies to Deeper. Corwin Press. Thousand Oaks. 2009.
8. ZEITZ, P. - The Art and Craft of Problem Solving. Second Edition. Wiley. Dan-
vers. 2007
48
