7/25/2019 par_impar

1/11

PAR OU MPAR? EIS A QUESTOSamuel Barbosa Feitosa e Einstein do Nascimento Jnior

Paridade

Quando duas pessoas esto indecisas sobre uma escolha, muitas vezes elas utilizam umabrincadeira chamada Par ou mpar para se decidirem. Por trs desse simples critrio, podem seresolver problemas que parecem ser bastante complicados. Dizemos que um nmreo tem paridadepar se ele for par, e paridade mpar, se ele for mpar. Observar a paridade de um nmero algo bemsimples mas com aplicaes fantsticas em problemas de olimpadas. Vejamos um exemplo:

Paridade como invariante

Vamos comear com um problema bastante famoso que j foi utilizado at em entrevistas paragrandes empresas de computao.

Problema 1.100 pessoas so postas em uma fila e cada uma delas recebe um chapu, que pode serpreto ou branco. Cada pessoa s consegue ver os chapus das pessoas que esto a sua frente. pedido que cada uma delas tente adivinhar a cor do seu chapu. Qual o mximo nmero de acertosque se pode garantir, dado que as pessoas podem combinar uma estratgia antes de receb-los.

Soluo:Facilmente consegue-se 50 acertos. Podemos dividir as pessoas em pares: (100,99), (98,97),...(2, 1) e assim o maior nmero de cada par falar a cor da pessoa da frente. Que apenas precisarepeti-lo, para garantir 1 acerto por par. De uma forma um pouco mais elaborada, se garante 66acertos. Separando em trios: (100, 99, 98),...(4, 3, 2). O maior nmero de cada trio pode falar

BRANCO caso os dois da sua frente tenham a mesma cor e PRETO, caso as cores sejam distintas.Assim, aps o maior nmero falar, o nmero do meio pode acertar sua cor e em seguida, o primeirodo trio pode acertar a dele. Curiosamente esse nmero pode chegar a 99 acertos utilizando essepoderoso argumento que a paridade. Notemos que ningum sabe a cor do ltimo da fila. Entono importa a estratgia de ordem das pessoas, nenhuma informao pode ser obtida para essechapu. O que no ocorre com os 99 chapus restantes. Note ainda que a diferena deconhecimentos entre a pessoa e a pessoa que encontra atrs dela apenas o seu chapu. Ento, bastaseguir a estratgia: As cores sero faladas das pessoas de trs para as da frente. E a ltima pessoavai falar BRANCO caso a quantidade de chapus brancos a sua frente seja par e PRETO, casocontrrio. Como a 99. pessoa sabe a paridade da quantidade de chapus brancos estritamente suafrente, e a paridade da quantidade de chapus brancos sua frente, incluindo ela mesma, que foiinformada pela 100. pessoa, ela acertar o seu chapu. A 98., computando ambas as informaes

pode acertar o dela, e assim sucessivamente.

Problema 2.Em cada casa de um tabuleiro de 5 x 5 est escrito 1 ou 1. Em cada passo troca-se onmero de cada uma das 25 casas pelo resultado da multiplicao dos nmeros de todas as suascasas vizinhas. Inicialmente se tem o tabuleiro da figura. Mostre como fica o tabuleiro ao final de2004 passos.

Observao:Duas casas so vizinhas se tiverem um lado em comum.

7/25/2019 par_impar

2/11

1 1 1 1 11 1 1 1 1

1 1 1 1 11 1 1 1 11 1 1 1 1

Dica:Muitas vezes, quando no se tem ideia de como ser a soluo de uma questo, pode-se obtervrias pistas fazendo alguns casos iniciais do enunciado, esperando observar algum padro. Meusnmeros da sorte so 5 e 9. Ao achar um padro repetitivo, basta analisar em que caso cair onmero 2004.

Problema 3.Em cada um dos 10 degraus de uma escada existe uma r. Cada r pode, de um pulo,colocar-se em outro degrau, mas quando uma r faz isso, ao mesmo tempo, uma outra r pular amesma quantidade de degraus em sentido contrrio: uma sobe e outra desce. Conseguiro as rs

colocar-se todas juntas num mesmo degrau?

Soluo:Uma maneira muito utilizada para atacar problemas onde dada uma condio inicial eum conjunto de operaes para manipul-la tentar procurar o que no muda, independentementedos movimentos que utilizamos. Note que se uma r vai de um degrau par para um mpar (muda deparidade), a outra r que se movimenta com ela tambm pular um nmero mpar de degraus,mudando tambm a paridade. Caso a primeira no mude, a sua parceira de movimento tambmpermanecer num degrau de mesma paridade. UM INVARIANTE: Paridade da quantidade de rsem degraus de nmero par (comprove testando os movimentos possveis). Como na posio inicialh 5 rs nos degraus de posio par e na posio final h ou dez ou zero rs nos degraus de posiopar, a posio final NO pode ser obtida da posio inicial apenas fazendo essas operaespermitidas.

Essa estratgia de invariantes utilizada principalmente para provar a impossibilidade de ocorreralgum evento.

Definiremos uma pea prncipe(que no existe no jogo de xadrez) como uma que s pode andar nahorizontal e vertical, uma casa por vez. Um jeito comum de fazer notaes em um tabuleiro dexadrez nomear as colunas da esquerda para a direita de aa he as linhas de baixo para cima de 1 a8 tomando o referencial da pessoa que joga com as casas brancas.

Problema 4.Sobre um tabuleiro de xadrez, um prncipe comea do quadrado a1 e retorna aps fazeralguns movimentos. Mostre que o prncipe fez um nmero par de movimentos.

Soluo:veja que em cada movimento, o prncipe muda para uma casa de cor oposta. Como a casa

a1 preta, aps um nmero mpar de movimentos o prncipe estar numa casa da cor branca. Paraele ter retornado at a casa preta do incio, ele dever ter feito um nmero par de movimentos.

Problema 5.Pode um prncipe comear do quadrado a1 de um tabuleiro de xadrez, ir at o quadradoh8, visitando cada um dos quadrados restantes exatamente uma vez?

Soluo:A resposta no. Em cada movimento, o prncipe pula para um quadrado da cor oposta.Como o prncipe tem que fazer 63 movimentos, o ltimo movimento ir deix-lo em uma casa dacor oposta a cor de a1.Entretanto, a1 e h8 tm a mesma cor. Isto um absurdo.

7/25/2019 par_impar

3/11

O ltimo problema nos conduz a um tipo muito importante de demonstrao: prova por absurdo.Suponha que lhe perguntaram se possvel somar cinco nmeros mpares e obter o nmero 100.Aps algumas tentativas voc comea a desconfiar que isto no possvel. Mas como provar que

no possvel? Se realmente fosse possvel somar 5 nmeros mpares e obter 100 o queaconteceria? Como a soma de cinco nmeros mpares sempre mpar obteramos que 100 umnmero mpar. Mas 100 no mpar! Logo no possvelexistirem tais 5 nmeros. Para provarque algo no possvel, basta supormos que possvel e chegarmos a um absurdo.

Problema 6. Uma linha poligonal fechada composta por 11 segmentos. Pode uma reta (nocontendo um vrtice da linha poligonal) intersectar cada um desses segmentos?Problema 7.Trs bolas de gude, A, B, e Cesto no cho. Um movimento permitido passar umabola entre as outras duas. possvel, aps 25 movimentos, que todas as bolas estejam nas suasposies originais?Dica: Que horas so? (Sentidos horrio e anti-horrio...)

Problema 8.Ktia e seus amigos esto em um crculo. Sabemos qua ambos os vizinhos de cadacriana so do mesmo sexo. Determine o nmero de garotas sabendo que existem 5 garotos nocrculo.Dica: Comece a analisar por um vizinho da Ktia.

Problema 9.(Rssia 1970) O rei Luis estava desconfiado de alguns de seus cortesos. Ele fez umalista completa de cada um dos seus cortesos e disse a cada um deles para espionar um outrocorteso. O primeiro da lista foi espionar o corteso que estava espionando o segundo da lista, osegundo da lista foi espionar o corteso que estava espionando o terceiro da lista, e assimsucessivamente; o penltimo foi espionar o corteso que estava espionando o ltimo e o ltimo foiespionar o corteso que estava espionando o primeiro. Prove que o rei Luis tinha um nmero mparde cortesos.

Soluo.Seja no nmero de corteso da lista e suponha que n par. Coloque-os sentados ao redorde uma mesa circular de modo que cada um esteja espionando o seu vizinho da direita.

Y1

X

2

2

n

O corteso 1 espia o cortesoXque espia o corteso 2, o corteso 2 espia o corteso Zque espia o

corteso 3, e assim sucessivamente at que o corteso2

nespia o corteso Yque espia o corteso

12

n.+ Como os nmeros 1, 2, 3,...,ndevem se alternar sobre o crculo, conclumos que o corteso

12

n+ igual ao corteso 1, ou seja, n= 0. Esse absurdo mostra que n mpar.

Problema 10.Um cubo 1 1 1 est posicionado em um plano quadriculado de modo que uma de

7/25/2019 par_impar

4/11

suas faces coincide com um dos quadradinhos do plano. Em cada movimento podemos tombar ocubo por uma de suas arestas, fazendo coincidir uma face, que tinha essa aresta, com um dosquadradinhos do plano. possvel fazer o cubo voltar a sua posio inicial aps 2005 movimentos?

Dica: Algum a joga xadrez?

Paridade e Contagens

Nesta seo, abordaremos duas ideias muito simples:

1. Se contamos os elementos de um conjunto de duas maneiras diferentes, os valores obtidos devemter a mesma paridade (Porque so iguais!)

2. Se os elementos de um conjunto podem ser pareados ento o conjunto tem uma quantidade par deelementos.

Problema 11.Em Brasilndia existem apenas 9 casas muito distantes entre si. possvel que cadacasa esteja ligada a exatamente 7 outras casas atravs de estradas?Soluo:No possvel. Some a quantidade de estradas que saem de cada casa. Bem, facilmenteobtemos 9 7 estradas. Como cada estrada liga duas cidades, a contagem que fizemos contou cadaestrada duas vezes. Logo o nmero obtido teria que ser par.Voc deve ter ficado com uma pulga atrs da orelha. Ser que cada casa ligada a exatamente 7outras foi realmente crucial? possvel revolvermos o problema anterior com um eneunciado maisgeral:

Problema 12.Prove que numa festa com npessoas, o nmero de pessoas que conhecem um nmerompar de outras pessoas na festa par.

Soluo:Numere as pessoas de 1 at ne denote por id o nmero de amigos da pessoa i. Imagineque existe um fio entre duas pessoas que se conhecem. SeEdenota a quantidade de fios, temos

1 2 2nd d ... d E,+ + + = pois cada fio contado duas vezes, um para cada ponta. Como o lado direito par, no lado esquerdodevemos ter uma quantidade par de nmeros mpares.

Problema 13. (Olimpada de Maio 2000) O conjunto {1, 2, 3, 4} pode ser dividido em doissubconjuntos { }1 4A ,= e { }3 2B ,= sem elementos comuns e tais que a soma dos elementos de A

seja igual soma dos elementos de B. Essa diviso impossvel para o conjunto { }1 2 3 4 5, , , , e

tambm para o conjunto { }1 2 3 4 5 6, , , , , . Determine todos os valores de npara os quais o conjunto

dos primeiros nnmeros naturais pode ser dividido em dois subconjuntos sem elementos comunstais que a soma dos elementos de cada subconjunto seja a mesma.

Soluo.Como a soma dos elementos de Adeve ser igual soma dos elementos de B, a soma dosnmeros do conjunto { }1 2 3, , ,...,n deve ser o dobro da soma dos elementos deA, ou seja, deve serum nmero par. Voc j deve saber que

( )11 2 3

2

n n... n .

++ + + + =

Voc no sabia disso? No fique a parado! Tente descobrir porque isso verdade! Veja que

7/25/2019 par_impar

5/11

( )1

2

n n + par se ( )1n n + mltiplo de 4. Como estamos interessados no resto na diviso por 4 de

algum nmero, talvez seja interessante procurar quais os possveis restos de n na diviso por 4.Podemos escrever nna forma 4n q r= + onde 0 1 2r , ,= ou 3. Mos obra!

1. Se 4n q= ento( )

( )1

2 4 12

n nq q

+= + par.

2. Se 4 1n q= + ento( )

( )( )1

2 1 4 12

n nq q

+= + + mpar.

3. Se 4 2n q= + ento( )

( )( )1

2 1 4 12

n nq q

+= + + mpar.

4. Se 4 3n q= + ento( )

( )( )1

2 2 4 32

n nq q

+= + + par.

Podemos concluir que n deve ser da forma 4q ou 4q + 3. Acabou? No! Precisamos construirEXEMPLOS para cada uma dessas possibilidades mostrando que realmente esses valoressatisfazem as condies do problema.Para n= 4q, considere os conjuntos

( ) ( ) ( ) ( ){ }1 4 5 8 9 12 4 3 4A , , , , , ,..., q , q .=

( ) ( ) ( ) ( ){ }2 3 6 7 10 11 4 2 4 1B , , , , , ,..., q , q .= Para n = 4q+ 3, considere os conjuntos

( ) ( ) ( ) ( ){ } ( ){ }4 7 8 11 12 15 4 4 3 1 2A , , , , , ,..., q, q , .= +

( ) ( ) ( ) ( ){ } ( ){ }5 6 9 10 13 14 4 1 4 2 3B , , , , , ,..., q , q .= + + Note que os conjuntos foram divididos em parntesis. Cada parntese deApossui correspondente

emBcom a mesma soma, facilitando a construo de um exemplo generalizado.Problema 14.Podemos desenhar uma linha poligonal fechada feita por 9 segmentos de reta, cada umdeles intersectando exatamente outro segmento?

Soluo.Se tal construo possvel, ento todos os segmentos podem ser agrupados em pares desegmentos intersectantes.Mas o nmero de segmentos mpar! Absurdo!

Os prximos dois problemas tratam de domins. Um domin consiste de um tabuleiro 1 x 2 compontos em cada casinha.A quantidade de pontos varia de 0 at 6. Ento, o nmero total de domins distintos 28.

Problema 15. Todos os domins so arranjados em uma cadeia de duas pontas (a quantidade depontos na extremidade de dois domins consecutivos a mesma). Se em uma ponta existe o nmero5, qual o nmero de outra ponta?

Problema 16.Em um conjunto de domins, descartamos todos aqueles que possuem pelo menosuma casinha vazia. possvel arranjarmos todos os restantes em uma cadeia?

Problema 17.(Eslovnia 1992) Prove que para quaisquer inteiros positivos 1 2 na ,a ,...,a o nmero:

1 2 2 3 1na a a a ... a a + + +

par.

7/25/2019 par_impar

6/11

Observao: x y chamado de valor absoluto da diferena entrexeye denota o mximo entrex

yeyx.Na reta real, ele representa a distncia entre os nmerosxey.Soluo:Perceba que x y x y = para alguma escolha de sinais. Ento a soma total

1 2 2 3 1na a a a ... a a .

Como cada nmero ia aparece duas vezes, basta mostrarmos que cada uma das expresses 1 ia a par para qualquer escolha de sinais. Vejamos os casos:

1. 2i i i i ia a a a a = + + = par.

2. 0i i i ia a a a = + = par.

3. 0i i i ia a a a = + = par.

4. 2i i i i ia a a a a = = par.

1.3 Miscelnia

Problema 18. Podemos trocar uma nota de 25 reais usando dez notas que podem assumir os valores1, 3, 5?

Soluo. No. Como a soma de um nmero par de nmeros mpares par, a soma dos valoresdessas 10 notas s pode ser um nmero par. Mas 25 mpar.

Problema 19.Peter comprou um caderno com 96 folhas, e numerou com os nmeros de 1 at 192.Victor rasgou 25 folhas consecutivas do caderno, e adicionou os 50 nmeros. Victor pode ter obtidoo nmero 1990 como resultado da soma?

Problema 20.Prove que a igualdade1 1 1 1 1 1

1a b c d e f + + + + + = no admite solues com todos os

nmeros sendo mpares.Dica: Faa o produto dos denominadores.

Problema 21.O produto de 21 inteiros igual a 1. Mostre que sua soma no pode ser zero.Dica: compare as quantidades de nmeros positivos e negativos.

Problema 22.Trs gafanhotos esto brincando ao longo da uma linha. Na sua vez, cada gafanhotopode pular sobre um outro gafanhoto, mas no sobre os outros dois. Eles podem retornar para suasposies iniciais aps 1991 movimentos?

Soluo. Sejam A, B, C os trs gafanhotos. Estaremos interessados apenas na ordem em que osgafanhotos se dispem ao longo da reta, digamos que inicialmente eles esto na ordem (A, B, C).Podemos fazer os seguintes movimentos:

( ) ( ) ( ) ( )1 2 3 4

A,B,C B, A,C B,C ,A C,B ,A ...

Em cada passo, disponha as letrasA, Be Cem um crculo (como mostra a figura) e leia a palavraABC. Percebeu alguma coisa? Antes de efetuarmos nosso primeiro movimetno, a leitura estava nosentido horrio e logo em seguida passou para o sentido anti-horrio. Como cada movimentoalternar os sentidos, aps 1991 movimentos estaremos em um sentido diferente do original. Logo,no possvel retornarmos para a posio original.

7/25/2019 par_impar

7/11

A B

CC B A

Observao:Compare com o problema 7.

Problema 23.Os nmeros de 1 at 10 so escritos em uma linha. Podemos colocar os sinais + e entre eles de modo que o resultado da expresso resultante seja 0?

Soluo:No possvel. Perceba que quando escolhemos um nmero para trocarmos de sinal, porexemplo, de + para , a soma total varia o dobro do nmero escolhido, ou seja, a paridade da somano muda. Basta ver agora que 1 2 10 55...+ + + = no tem a mesma paridade que 0. UmINVARIANTE a paridade da soma.

Problema 24.Um gafanhoto pula ao longo de uma linha. No seu primeiro pulo, ele anda 1cm, nosegundo 2cm, e assim sucessivamente. Ele pode pular para a esquerda ou para a direita. Mostre queaps 1985 pulos, o gafanhoto no pode retornar ao ponto em que comeou.Dica: Perceba que voc pode associar aos pulos do gafanhoto um nmero com sinal (+ se o pulo para a esquerda e se para a direita). Agora use o problema anterior.

Problema 25.Os nmeros 1, 2,...,1984, 1985 so escritos em um tabuleiro. A operao permitida apagar dois nmeros e colocar sua diferena positiva. Aps algumas operaes, resta apenas umnico nmero no tabuleiro. Pode este nmero ser 0?

Problema 26.Pode um tabuleiro 8 8 ser coberto com domins 1 2 de modo que somente osquadrados a1 e h8 no sejam cobertos?

Soluo.No possvel. Pinte o tabuleiro de preto e branco da maneira usual. Cada domin cobreexatamente um quadrado preto e outro branco (Invariante), portanto, a quantidade de quadradospretos cobertos igual quantidade de quadrados brancos cobertos. Como a1 e h8 tm a mesmacor, sobrariam 30 quadrados de uma cor e 32 de outra para serem cobertos. Absurdo!

Problema 27.45 pontos so escolhidos sobre a reta AB, todos fora do segmento de reta AB. Proveque a soma das distncias desses pontos ao ponto Ano pode ser igual soma das distncias aopontoB.

Soluo.Sejam AeBdispostos, sem perda de generalidade como na figura abaixo. Tomemos umpontoX.

A B X

X pode estar direita de B ou esquerda de A. Ou ocorre: AX AB BX+ = ou BX AB AX .+ = Assim, se estivssemos somando emxas distncias dos 45 pontos paraAe emyparaB, estaramos

7/25/2019 par_impar

8/11

na verdade, s somando uma diferena de AB em x ou em y. Como 45 mpar, no podemos

distribuir uma igual quantidade de AB spara o grupo de A e o de B. Assim, segue que no possvel.

Problema 28.Um nmero de 17 dgitos somado com o seu reverso (um nmero com os mesmodgitos mas escritos na ordem inversa). Mostre que sua soma contm pelo menos um dgito par.

Problema 29.Existem 100 soldados em um quartel. Toda noite, trs deles ficam de guarda. Aps umcerto perodo de tempo, possvel que cada soldado tenha ficado de guarda exatamente uma vezcom cada outro soldado?Soluo: Suponha, por absurdo, que seja possvel. Tomemos o Soldado Ryan, ele possui 99companheiros. Suponha que ele em particular tenha conseguido ficar exatamente uma vez depernoite com cada um dos outros. A cada dia, Ryan formava 2 duplas diferentes, que no poderiamse repetir nos dias posteriores. Caso Ryan tivesse pernoitadoxvezes, a quantidade de duplas que eleteria formado seria 2x, que por hiptese, deve ser igual a 99. Chegando concluso que 99 par.

Absurdo!

Problema 30.25 garotos e 25 garotas esto sentados ao redor de uma mesa. Prove que semprepossvel encontrar uma pessoa tal que ambos os seus vizinhos so garotas.

Soluo:Suponha, por absurdo, que no necessariamente haja uma pessoa que possua duas garotascomo vizinhas. Denotemos hpara garoto e mpara garota. Cada pessoa ou possui como vizinho 2hou h+m. Somando todas as 50 possibilidades, devemos estar contando cada pessoa duas vezes (jque essa vizinho de duas pessoas). Assim: ( ) ( )2 50 50x h y h m h m+ + = + onde x o nmero depessoas que tm 2 garotos como vizinhos e y o nmero de pessoas que tm um garoto e umagarota. Notemos ainda que x+ y= 50. Obtemos ( )50xh y m= assim xh xm.= Mas xgarotos s

sero iguais a xgarotas, sexfor nulo. Assim, todas as pessoas tm um garoto e uma garota comovizinhos. Pintemos as 50 posies do crculo apenas de branco e preto. E analisemos apenas aspretas. Todas as pretas tero que ter vizinhos sendo um garoto e uma garota. Logo, as casas brancassero alternadas: garoto, garota, garoto... Absurdo. Pois com 25 casas brancas, na ltima e naprimeira brancas haver 2 garotos. Absurdo! Segue o resultado.

Problema 31.(Ucrnia 1997) Um tabuleiro colorido de branco e preto da maneira usual, e cadacasa contm um inteiro. Sabemos que a soma dos nmeros em cada coluna e a soma dos nmerosem cada linha par. Mostre que a soma dos nmeros nas casas pretas par.

Soluo.Suponha sem perda de generalidade que o quadrado do canto esquerdo superior preto. Apartir desse quadrado, numere as colunas da esquerda para a direita e as linhas de cima para baixo.

Some os nmeros das colunas em posies mpares e os nmeros das linhas em posies pares.Perceba que cada quadrado preto do tabuleiro contado apenas uma vez nessa soma enquanto queos quadrados brancos das linhas e colunas mencionadas so contados duas vezes. Logo, esse somatem a mesma paridade que a soma de todos os nmeros escritos nos quadrados pretos. Como a somade quaisquer linhas e colunas par, a soma dos nmeros nos quadrados pretos par.

7/25/2019 par_impar

9/11

Problema 32. Considere um tabuleiro 1998 2002 pintado alternadamente de preto e branco damaneira usual. Em cada casa do tabuleiro, escrevemos 0 ou 1, de modo que a quantidade de 1s emcada linha e em cada coluna do tabuleiro mpar. Prove que a quantidade de 1s escritos nas casabrancas par.Dica: Tente imitar a soluo anterior.

Problema 33.(Austrlia 2007) Em cada casa de um tabuleiro 2007 2007 escrevemos um nmerointeiro mpar. Sejam iZ a soma dos nmeros na i-sima linha e jS a soma dos nmeros na j-sima

coluna, para 1 2007i, j . Alm disso, sejam 2 2007iA Z Z ...Z= e 1 2 2007B S S ...S .= Mostre queA+Bno pode ser igual a zero.

Problema 34.(China 1986) possvel arranjar os nmeros 1, 1, 2, 2, 3, 3,...,1986, 1986 em fila demodo que entre quaisquer dois is hajam (i 1) nmeros?

Soluo:Vamos tentar fazer alguns casos pequenos. fcil ver que no conseguimos fazer o que oenunciado pede com os nmeros 1, 1, 2, 2 mas com os nmeros 1, 1, 2, 2, 3, 3, 4, 4 temos umexemplo:

1. 2. 3. 4. 5. 6. 7. 8.a3 a4 a2 b3 b2 b4 a1 b13 4 2 3 2 4 1 1

Contados da squerda para a direita, denotemos pori

a ei

b as posies do primeiro e segundo

nmero i, respectivamente. No nosso exemplo, 2 3a = e 2 5b .=

Como existem i 1 nmeros entre dois nmeros is, devemos teri ib a i. = Se possvel escrever

os nmeros 1, 1, 2, 2, ..., n, n em linha como no enunciado, obtemos:

( ) ( ) ( )1 2 1 2 1 2 2 2 1n na a ...a b b ...b ... n n n+ + + + + = + + + = +

( ) ( ) ( ) ( )

1 1 2 2

11 2

2

+ + + = + + + =n n

n nb a b a ... b a ... n .

Somando as duas linhas,

( ) ( )

1 2

5 32

2nn n

b b ...b+

+ + =

Como o lado esquerdo sempre par, a frao( )5 3

2

n n +deve ser um inteiro par. Isso j restringe os

possveis valores de n.Para n = 1986,

( )5 39863469

2

n n +=

7/25/2019 par_impar

10/11

mpar e conseqentemente no possvel dispormos esses nmeros em linha. Uma perguntanatural que voc deve tentar responder : para quais ntal distribuio possvel?

Problema 35. possvel arranjar os nmeros de 1 at 9 em uma sequncia, de modo que exista umaquantidade mpar de nmeros entre 1 e 2, entre 2 e 3,..., e entre 8 e 9?

Problema 36.(Rssia 1984) O nmero de todos os inteiros positivos de 64 dgitos sem zeros em suarepresentao e que so divisveis por 101 par ou mpar?

Soluo: Precisamos bolar alguma maneira de agrupar os nmeros em pares. Seja64

11 110vezes

A ...=

repeties do nmero 1.Como 1111 mltiplo de 101 fcil ver que A mltiplo de 101. Para todo nmero de 64 dgitos

1 2 63 64a a a ...a a ,= sem zeros em sua representao decimal, considere o seu conjugado

( )( ) ( )1 2 63 64 1 2 6410 10 10= = b b b ...b b a a ... a . Nenhum dgito de a igual a zero, portanto, cada

nmero 10 ia pertence ao conjunto { }1 2 9, ,.., .Da equao a+ b=Aobtemos que a divisvel por101 se e somente se b divisvel por 101 (lembre-se que A mltiplo de 101). Como o niconmero que igual ao seu conjugado o nmero

64

55 55vezes

...

(que mltiplo de 101) e os demais

nmeros que satisfazem o enunciado podem ser pareados, conclumos que a quantidade procurada mpar.

Problema 37. (Putnam 1997) Seja nB a quantidade de n uplas ordenadas de inteiros positivos

( )1 2 na ,a ,...,a tais que

1 2

1 1 11

n

...a a a

+ + + =

10B par ou mpar?

Soluo:Uma ideia natural tentar agrupar as solues em pares. Qualquer soluo com 1 2a a

pode ser pareada com a outra soluo obtida pela troca de posio entre 1a e 2a . Logo, 10B tem a

mesma paridade que o nmero de solues com 1 2a a .= Das solues com 1 2a a ,= podemos parear

aquelas que tem 3 4a a da mesma maneira. Repetindo esse argumento com ( ) ( )5 6 7 8a ,a , a ,a e

( )9 10a ,a , conclumos que a paridade de 10B a mesma do nmero de solues com 5 6 7 8a a ,a a= =

e 9 10a a ,= ou seja, das solues de:

1 3 5 7 9

2 2 2 2 21.a a a a a+ + + + =

Como anteriormente, podemos nos restrigir quantidade de solues com 1 3a a= e 5 7a a= , que igual ao nmero de solues da equao:

1 5 9

4 4 21.

a a a+ + =

Mais uma vez, podemos nos restringir quantidade de solues com 1 5a a= , que igual ao nmerode solues da equao:

1 9

8 21.

a a+ =

7/25/2019 par_impar

11/11

Agora ficou fcil! Basta contar explicitamente o nmero de solues da equao anterior. Comofazer isso? Bem, ela pode ser fatorada como:

( )( )1 98 2 16a a =

que admite 5 solues correspondendo s fatoraes de 16 como 42 2i i para 0 1 2 3 4i , , , , .= Ento

10B mpar.

Problema 38:Prove que numa festa com 2npessoas existem duas com um nmero par de amigos emcomum.

Soluo:Suponha que quaisquer duas pessoas tenham um nmero mpar de amigos em comum esejaAum dos participantes da festa. Seja { }1 2 kM F ,F ,...,F= o conjunto dos amigos deA.Considere

uma nova festa restrita apenas ao conjunto M. Como cada iFtem um nmero mpar de amigos em

comum com A, na nova festa, cada iFpossui um nmero mpar de amigos. Pelo problema 12, k

deve ser par. O mesmo argumento vale para qualquer pessoa na festa e conseqentemente todos tmum nmero par de amigos. Pea para cada um dos amigos de Afazerem uma lista de seus amigosdiferentes deA. A soma da quantidade de nomes listados par, pois uma soma de uma quantidadepar (igual a k) de nmeros mpares (cada iFpossui um nmero mpar de amigos diferentes de A).

Agora comparemos o nmero de aparies de cada uma das 2 1n pessoas diferentes de Anessaslistas. Se cada uma delas aparecer em um nmero mpar de listas, a soma total de todos os nomesem todas as listas seria mpar. (Lembre-se que a soma de uma quantidade mpar de nmerosmpares mpar!). Mas isso uma contradio. Logo, existe uma pessoa diferente de Aque apareceem um nmero par de listas, e portanto tem um nmero par de amigos em comum comA.

Problema 39.Alex desenhou uma coleo de K retas no plano em posio geral (quaisquer duasretas se intersectam em um ponto e quaisquer trs definem um tringulo no degenerado). Para

quais valores de K sempre possvel (no importa como as retas so desenhadas) colocar umelemento do conjunto { }1 2 1, ,...,K em cada ponto de interseo das retas de modo que em todareta no existam nmeros iguais.

Problema 40. (Rssia) Em cada planeta de um sistema solar existe um astrnomo observando oplaneta mais prximo. As distncias entre os planetas so distintas duas a duas. Demonstre que se aquantidade de planetas mpar, ento existe pelo menos um planeta que no observado.Dica: Procure as cadeias de planetas que um olha para o outro que olha para o outro com mais de 2planetas.

REFERNCIAS[1] D. Fomin, S. Genkin e I. Itenberg, Mathematical Circles, MAS (1996).

[2] C. Augusto, S. Feitosa, B. Holanda e Y. Lima, treinamento Cone Sul 2007, Fortaleza, Realce (2007).[3] P. J. Taylor, Tournament of the Towns 1980 to 1984, Australian Mathematical Trust (1993).[4] D. Fomin e A. Kirichenko, Leningrand Mathematical Olympiadas 1987-1991, MathPro Press (1994).[5] E. Wagner, Paridade, Eureka! No. 2, pp. 32-38, (1998).