sábado, 25 de agosto de 2012

Seção de Problemas – Nº 6

Hoje trago uma nova seção de problemas a vocês. A partir desta seção de problemas, vou apenas resolver os problemas requisitados pelos leitores. Como, desde a ultima não houve problemas requisitados, não resolverei problemas, apenas darei dicas sobre os problemas atuais.

Teoria dos Números

1 – Mostre que, se mdc(a,2n+1) = 2n e mdc(b, 2n+1) = 2n então mdc(a+b, 2n+1) = 2n+1

2 – (IMO – 1989) Mostre que, para todo n natural, há um bloco de n inteiros consecutivos no qual não há potências de números primos.

3 – Definamos

clip_image002

Mostre que a imagem da função

clip_image004

É justamente o conjunto dos números primos.

Álgebra

4 – (Harvard-MIT 2012) Seja a0 = -2, b0=1 e, para todo n >1, temos

clip_image006

clip_image008

Ache a2012.

5 – (Harvard-MIT 2012) Seja x1 = x2 = y1 = y2 = 1, e, para todo n > 2, sejam

clip_image010

clip_image012

Quais são os dois últimos dígitos da representação decimal de |x2012|?

6 – (Harvard-MIT 2012) Nos finais de semana, Eli entrega leite no plano complexo. No sábado, ele começa no complexo z e vai para clip_image014, nessa ordem. No domingo, ele começa do 1 e vai para clip_image016, também nesta ordem. Eli anda diretamente (em linha reta) entre duas casas. Se a distância que ele anda do primeiro ponto até o último ponto é clip_image018 em ambos os dias, ache a parte real de z².

Geometria

7 – Seja H o ortocentro de um triângulo ABC. Prove que as retas de Euler dos triângulos ABC, BCH, CAH, ABH São todas concorrentes. Em que ponto notável elas são concorrentes?

8 – (Estônia) As medianas relativas aos vértices A e B do triângulo ABC são perpendiculares. Mostre que AB é o menor lado do triângulo.

Combinatória

9 – (Resta Um) O clássico jogo do resta um é jogado em um tabuleiro formado por 5 quadrados 3x3, colocados um acima do outro em forma de cruz, como na figura, com a casa central sem peças, e as restantes com peças. Determine em quais casas podemos terminar o jogo do resta um.

clip_image019

10 – Temos camaleões de 3 cores, digamos, vermelho, amarelo a azul. Se dois camaleões se encontram, então eles ficam com a mesma cor, diferente das de cada um camaleão. Suponhamos que só haja encontros entre dois cameleões por vez. Encontre todos os pares de (a,b,c), onde a é a quantidade de camaleões vermelhos, b a de amarelos e c a de verdes tal que possa haver uma maneira de, ao final, todos os camaleões estarem de uma mesma cor.

Dicas e Fatos que Ajudam

1 – Use o Teorema Fundamental da Aritmética, aliado à propriedade de que a soma de dois ímpares é um par.

2 – Considere os números da forma ((n+1)!)² + k, onde 1<k < n + 2.

3 – Analise os dois casos para o módulo de |a² - 1|, e em um deles complemente com o teorema de Wilson.

4 – Ache uma relação entre o produto e a soma de cada an e bn.

5 – Utilize multiplicação de números complexos para achar uma recorrência que dê xn explicitamente. Feito isso, considere x2012 módulo 100, e, com a ajuda do teorema de Euler, utilize o resultado desejado.

6 – Utilize a distância de dois complexos w e z no plano ser |z – w|, e compare os dois somatórios para achar o módulo de z. Feito isso, achar a parte imaginária de fica fácil, com auxílio da forma trigonométrica.

7 – Prove a relação desejada para apenas uma reta de Euler, e faça o análogo para as outras (elas se intersectam no centro círculo dos nove pontos)

8 – É uma aplicação direta do teorema do baricentro e do teorema de Pitágoras.

9 – Colora o tabuleiro com três cores, uma em cada diagonal, e prove que só pode acabar em determinadas casas. Simetrizar esse processo, só até obter casas que são suas próprias simétricas, que serão as casas que nos darão os resultados.

10 – Repare que a quantidade de cada cor é sempre “aumentada” de 2 módulo 3. Com isso, prove que basta que dois números a,b sejam côngruos módulo 3 para que o desejado ocorra.

Bom, por enquanto é só. Fiquem ligados para mais material teórico e problemas no blog.

Alguma dúvida, crítica, sugestão, opinião, elogio, comentário? Comente! Incentivamos os comentários no blog, principalmente se forem bem-educados!

Ah, e não se esqueça de avaliar o post aqui embaixo! É rápido, só um click.

quinta-feira, 23 de agosto de 2012

Um pouco sobre jogos

Aproveitando esse post do João, eu decidi escrever essa postagem em que apresentarei alguns jogos e algumas formas de descobrir uma estratéga vencedora para o primeiro ou o segundo jogador.

Inicialmente, temos os pseudo-jogos, que são jogos em que um jogador sempre ganha não importando o que aconteça durante o jogo.

P-1: Estão escritos num papel, em ordem, todos os inteiros de 1 a 20 (inclusive). Dois jogadores se revezam colocando sinais de [;+;] ou de - entre dois números. Ao final, quando todos os espaços forem preenchidos calcula-se a expressão obtida. Se o resultado for par, o primeiro jogador a jogar vence. Caso contrário, vence o segundo. Há alguma estratégia que garanta a vitória a um dos jogadores?

Resposta: Vamos inicialmente supor que os números estão escritos assim:
[;1+;][;2+ 3+ 4 +5+;][; 6+ 7+ 8+ 9+ 10+ 11;][;+;][; 12+ 13+ 14+ 15+ 16+ 17+ 18+ 19+ 20;]

E supor que cada jogada passa a ser alterar um dos sinais que estão pré-escritos para - ou simplesmente manter como +. (Sendo que se for mantido, o sinal não poderá ser alterado futuramente)

Observe que essa soma é par. Observe também que se a soma é par, se antes de um número par o sinal de + for alterado para um sinal de -, o resultado da expressão continua par. E o mesmo ocorre para números ímpares, assim, não importando o que seja feito, o resultado final será par e o primeiro jogador sempre ganha.


P-2:
Dois jogadores se revezam colocando torres num tabuleiro de xadrez de forma que elas não possam se atacar.O jogador que não conseguir colocar uma torre perde o jogo. Quem vence o jogo?

Resposta: Observe que colocar uma torre reduz em 1 o número de linhas e colunas que pode se colocar uma torre. Assim, só haverá 8 jogadas e o segundo jogador fará a ultima jogada possível.

O.B.S.: De modo geral, num tabuleiro [;n;] x [;n;], se n é par o segundo jogador sempre ganha, caso contrário, o primeiro sempre ganhará.

P-3: Há 2 montes de pedras, 1 com 5 e outro com 10. Dois jogadores se alternam em jogadas que consistem em escolher um dos montes e dividi-los em 2 montes menores. Perde o jogador que não conseguir realizar uma jogada. Qual dos jogadores ganha?

Resposta: O jogo acaba quando tiver 15 montes, cada 1 com 1 pedra. Cada jogada aumenta o número de montes em 1, logo, são realizadas 13 jogadas e o jogador 1 fará a ultima jogada possível.


Observe os problemas abaixo:

P-4: Dois jogadores se revezam colocando moedas de mesmo tamanho numa mesa redonda sem empilha-las, perde o jogador que não puder mais colocar uma moeda na mesa. Existe uma estratégia vencedora que garanta a vitória ao primeiro ou segundo jogador? Em caso afirmativo, explicite-a e explique sua eficacia.

P-5: Dois jogadores se revezam colocando bispos em um tabuleiro de xadrez de forma que eles não ataquem. Perde o jogador que não puder mais colocar bistos no tabuleiro. Existe uma estratégia vencedora que garanta a vitória ao primeiro ou segundo jogador? Em caso afirmativo, explicite-a e explique sua eficacia.

P-6: Há 2 montes de pedra, cada um com 10 pedras. Dois jogadores se revezam efetuando jogadas que consistem em retirar quantas pedras quiser de um dos montes. Perde o jogador que não puder mais realizar uma jogada. Existe uma estratégia vencedora que garanta a vitória ao primeiro ou segundo jogador? Em caso afirmativo, explicite-a e explique sua eficacia.

P-7: Há 2 montes de pedra, um com 10 e outro com 20. Dois jogadores se revezam efetuando jogadas que consistem em retirar quantas pedras quiser de um dos montes (para sua jogada cada jogador tem que tirar pelo menos 1 pedra de 1 dos montes) . Perde o jogador que não puder mais realizar uma jogada. Existe uma estratégia vencedora que garanta a vitória ao primeiro ou segundo jogador? Em caso afirmativo, explicite-a e explique sua eficacia.

Todas são resolvidas usando uma estratégia conhecida como simetria. Após resolver cada uma ficará claro no que consiste a estratégia simétrica.

Resposta da 4: Sim. O primeiro jogador pode ganhar sempre não importando o tamanho da mesa. Para isso, ele deve botar a primeira moeda de forma que o centro da moeda coincida com o centro da circunferência. Feito isso, onde o segundo jogador colocar uma moeda o primeiro coloca no seu simétrico em relação ao centro da circunferência. Fica fácil ver que como ele age sempre simétricamente toda vez que o segundo jogador puder realizar uma jogada o primeiro pode realizar sua jogada. Logo, alguma hora o segundo jogador não poderá jogar.

Resposta da 5: Sim. O segundo jogador pode ganhar sempre. A ideia é bastante parecida com a ideia acima, para isso, ele deve usar como eixo de simetria a reta entre a quarta e a quinta linha do tabuleiro. Observe que como ela divide o tabuleiro ao meio, todas as casas terão uma casa simétrica a reta escolhida. Para garantir sua vitória o segundo jogador deve colocar seu bispo sempre na casa simétria a casa que o primeiro jogador escolheu. Note que essa casa será de cor diferente a casa escolhida pelo primeiro jogador e por isso os bispos não irão se atacar. Assim, o segundo jogador garante que se o primeiro puder jogar, então ele também pode, o que garante a vitória.

Reposta da 6: Sim. O segundo jogador pode sempre vencer. Para isso, se o primeiro jogador tirar X pedras do monte A, então o segundo deve tirar X pedras do monte B. Assim, ele garante que ao final de sua jogada os dois montes tenham a mesma quantidade de pedras. Logo, quando o primeiro jogador acabar as pedras de um dos montes, o segundo acaba com as pedras do outro e o primeiro perde.

Resposta da 7: Sim. O primeiro jogador pode vencer sempre. A estratégia é bastante parecida com a do problema acima. Na primeira jogada do primeiro jogador deve retirar 10 pedras do monte que tem 20 pedras. observe então que ele passa a ser o segundo jogador do problema anterior e por isso deve após a sua primeira jogada seguir a estratégia seguida pelo segundo jogador do problema acima.

Para explicar o próximo método, vamos observar os problemas abaixo.

P-8: Numa caixa há 153 fósforos. Dois jogadores se revezam realizando jogadas que consistem em retirar 1, 2, 3, 4 ou 5 fósforos. Perde o jogador que não puder realizar sua jogada. Existe uma estratégia vencedora que garanta a vitória ao primeiro ou segundo jogador? Em caso afirmativo, explicite-a e explique sua eficacia.

Resposta: Sim, o primeiro jogador pode sempre vencer. Para isso, observe que um jogador ganha se ao final de sua última jogada não tiver nenhum fósforo na caixa. A estratéga então consiste em retirar na primeira jogada 3 palitos da caixa. Então, sobraram 150 palitos e 150 é um múltiplo de 6. Feito isso, se o segundo jogador retirar k palitos, então o primeiro retira [;6-k;] palitos. Assim, ele garante que ao final de todas as suas jogadas e somente ao final de todas as suas jogadas, o número de fósforos na caixa é múltiplo de 6. Como 0 é um múltplo de 6, ele garante a sua vitória sempre.

P-9:
Num tabuleiro de xadrez uma torre está na casa [;a1;]. Dois jogadores se revezam realizando jogadas que coincistem em mover a torre quantas casas quiser na horizontal pra direita ou quantas casas quiser na vertical para cima. Vence o primero jogador que ao final da sua última jogada colocar a torre em [;h8;]. Existe uma estratégia vencedora que garanta a vitória ao primeiro ou segundo jogador? Em caso afirmativo, explicite-a e explique sua eficacia.

Resposta: Sim, o segundo jogador sempre vence. Para isso, se o primeiro jogador mover a torre em X vezes na horizontal pra direita, o segundo deve mover X vezes na vertical pra cima. Se o primeiro mover a torre em X vezes na vertical pra cima, o segundo deve mover em X vezes na horizontal pra direita. Essa estratégia funciona por que o segundo jogador garante que a torre fica na diagonal formada pelas casas [;a1;] e [;h8;] . Como [;h8;] está nessa diagonal, o segundo jogador pode de fato sempre ganhar.


As estratégias usadas nos dois problemas acima consistem em encontrar as chamadas posições vencedoras. Que seriam as posições em que quem se encontrar nelas pode ganhar sempre. Observe algumas coisas importantes sobre posições vencedoras.

1) A posição final é uma posição vencedora. De fato 0 e h8 são as posições finais.


2) Nunca é possível mover de uma posi
ção vencedora para outra posição vencedora. De fato, no problema 8, se subtrairmos 1, 2, 3, 4 ou 5 de um múltiplo de 6 o resultado não será um múltiplo de 6. E no segundo jogo, como não é possível andar na diagonal, sempre que a torre é colocada na diagonal, na rodada seguinte ela é obrigada a sair.

3) Sempre pode-se mover de uma posição não-vencedora para uma posição vencedora. Verifique que isso ocorre nos dois jogos.

Ao obter-se posições vencedoras, e uma estratégia para manter-se sempre nelas, é suficiente afirmar: "como ao final de suas jogadas o jogador A sempre está numa posição vencedora, ele garante sua vitória." e o problema então passaria a ser mostrar que essas posições são de fato posições vencedoras.


Por hoje é só! Não se esqueçam de avaliar a postagem logo abaixo. Se você gostou do blog, recomende aos seus amigos nas redes sociais e se inscreva (por e-mail ou no blog) para receber nossas atualizações.

Até mais!

Dois Problemas Interessantes sobre Jogos

Hoje vou apresentar a vocês dois problemas de jogos interessantes que um amigo meu me propôs. Na verdade, um deles é apenas um erro de interpretação (e aquecimento) para o outro, porém eu gostei bastante das duas versões, logo, apresentarei as duas e suas respectivas soluções.

Problema 1: Temos n balas em uma mesa, e dois amigos jogando um jogo. Uma jogada consiste em comer até um máximo de n/2 balas. Ganha quem deixar uma bala na mesa primeiro. Alguém possui uma estratégia vencedora? Se sim, explicite-a.

Resolução: Vamos fazer casos pequenos:

n = 2, então o primeiro obviamente ganha

n = 3, então o segundo obviamente ganha

n = 4, então o segundo obviamente ganha.

Agora vamos provar que para todo n > 4 que o primeiro tem uma estratégia vencedora. Seja

clip_image002

Onde o símbolo acima indica o menor inteiro menor ou igual que n/2. Se o primeiro jogador comer x balas em sua primeira jogada, então sobrarão

clip_image004

Balas na mesa. Como o segundo pode comer no máximo clip_image006 na sua vez, ele deixa um mínimo de duas balas na mesa, e eum máximo de clip_image008. Logo, o primeiro sempre garante sua vitória pra n > 4. ■

Vimos neste problema que não utiliza-se nada muito específico, porém apenas uma ideia boa. No próximo, as ideias valem a pena, mas os conhecimentos sobre indução também são válidos.

Problema 2: Temos n balas em uma mesa, e dois amigos jogando um jogo. Uma  jogada consiste em retirar no máximo a metade das balas que há na mesa no momento. Vence quem deixar apenas uma na mesa. Para que valores de n cada jogador tem uma estratégia vencedora?

Resolução: Vamos fazer alguns casos pequenos, desta vez para entender o que está acontecendo:

n = 2, o primeiro vence.

n = 3, o segundo vence.

n = 4, o primeiro vence.

n = 5, o primeiro vence.

n = 6, o primeiro vence.

n = 7, o segundo vence.

E assim notamos algo peculiar. Será que para todo n = 2k -1 o segundo vence, e para o resto, o primeiro vence? A resposta é sim.

Mas por quê? Pensemos assim: o primeiro, quando faz uma jogada de tamanho a, vira o segundo num jogo de tamanho n-a. Assim, Se existir a<n/2 tal que num jogo com n-a balas o segundo vence, então podemos garantir a vitória do primeiro. Vamos mostrar por indução que isso só não acontece se n é potência de 2 subtraída de um.

A base n = 3 é óbvia. Agora, suponhamos que isso seja válido para um inteiro n = 2t – 1, ou seja, que o segundo ganhei. Como sabemos, se tivermos um inteiro b = 22t – 2, então, se subtrairmos exatamente a sua metade, teremos n, logo, o primeiro pode vencer. Vemos facilmente que para todo inteiro r tal que n < r < b, o primeiro ganha, pois o número de balas que este irá subtrair para chegar a n é menor que a sua metade: r-n < r/2 se, e somente se, r < 2n. Porém, no caso para b + 1 = 22t – 1, se subtrairmos o inteiro mais próximo de sua metade, teremos b + 1 – n = 2t, que é maior que n. Porém, em todos estes casos, o primeiro ganha. Logo, para b+1, o segundo jogador deve ganhar, o que completa a indução.

Logo, temos que o segundo ganha se, e somente se, n = 2k – 1, e o primeiro ganha em todos os outros casos. ■

Caso você não entenda muito sobre indução, não fique preocupado! Temos três posts sobre indução, e você pode acessá-los clicando aqui, aqui e aqui.

Caso queira deixar sua dúvida, reclamação, crítica, sugestão, elogio ou qualquer tipo de expressão verbal para nós, então comente! Seu comentário é bem-vindo, desde que este seja bem educado e seguindo as regras da moderação.

Pedimos também que você avalie o post aqui embaixo. Não demora nada, é só um click!

quarta-feira, 22 de agosto de 2012

Problema 2 da IMO 2012

Hoje vamos resolver o segundo problema da IMO. Porém, antes iremos demonstrar um importante teorema para resolvê-lo. Este teorema geralmente é conhecido como o teorema da desigualdade entre as médias.

Desigualdade Entre as Médias Geométrica e Aritmética: Sejam a1, a2, ..., an reais positivos dados. Então, se

clip_image002

É sua média aritmética e

clip_image004

É sua média geométrica, então

clip_image006

Demonstração: Façamos por indução em n potência de 2. Depois demonstraremos o caso geral.

Para n=2, então

clip_image008

Que é verdadeiro.

Agora, suponhamos que seja válido para n. Provemos que é válido para 2n. Pela hipótese de validade para n, então, se dividirmos os números de 1 a 2n em 1 a n e n+1 e 2n, então

clip_image010

Ou seja, é válido para toda potência de 2. Agora, seja k uma potência de 2 e n um natural menor que k. Então, sendo a a média geométrica de a1, ..., an. Então,

clip_image012

Onde a é inserido k-n vezes, como um complemento de espaço. Mas

clip_image014

Logo,

clip_image016

Portanto,

clip_image018

Que completa o caso geral de n. ■

O Problema 2 da IMO 2012: Sejam a2,a3,... , an reais positivos com produto 1. Prove que

clip_image020

Resolução: Tudo que vamos utilizar neste problema é a desigualdade já estudada, além de um pouco de raciocínio. Aplicaremos MA-MG (Abreviação usual pra desigualdade entre as médias) nas parcelas separadamente:

clip_image022

clip_image024

E assim podemos proceder indutivamente:

clip_image026

Reparemos que, ao final, ao multiplicarmos as parcelas, todos os denominadores “cortarão” com numeradores, e, como o produto dos números é 1, então

clip_image028

Mas e a igualdade? Sabemos que só ocorre igualdade se

clip_image030

Mas, quando isto ocorre, o produto dos ai não vira 1. Logo, não há igualdade, o que prova a desigualdade do enunciado. ■

Fiquem ligados no blog para mais problemas e material teórico. Não se esqueçam de avaliar o conteúdo aqui embaixo, é rápido! Só um click!

Caso queiram deixar sua opinião, crítica, sugestão, elogio ou qualquer outra manifestação verbal, podem deixar comentários! Nós incentivamos todos a comentar, desde que os comentários sejam bem educados e respeitosos (seguindo as regras que estão na seção de comentários).

sexta-feira, 17 de agosto de 2012

Um problema famoso de Geometria

Olá gente! Hoje aprensentarei um problema bastante conhecido em geometria e algumas de suas soluções também muito conhecidas.









O triângulo [;ABC;] ao lado é isósceles de vértice [;A=20^{\circ};] .

Sendo [;D\hat{B}C=50^{\circ};] e [;E\hat{C}B=60^{\circ};] calcule [;C\hat{E}D;].













Resolução 1 :

Vamos usar lei dos senos nessa solução. Clique aqui para ler o post do João sobre geometria com contas.

Se fizermos [;C\hat{E}D=x;] então [;C\hat{D}E=160^{\circ} -x;]

Aplicando a Lei dos Senos no triângulo [;CDE;]...

[;\frac{CE}{CD}=;][;\frac{sen(160^{\circ}-x)}{sen (x)};](I)

e no triângulo [;BCE;] obtemos:

[;\frac{CE}{BC}= \frac{sen(80^{\circ})}{sen(40^{\circ})} = 2 \cdot cos (40^{\circ});] (II) (só usar a fórmula do seno do arco duplo!)

Como [;C\hat{B}D=;][;C\hat{D}B;][;=;]
[;50^{\circ};] então [;\triangle{BCD};] é isosceles. Assim, [;CD=BC;]

Isso nos permite escrever (I)=(II)
L
ogo, [;\frac{sen(160^{\circ} -x)}{sen(x)}=2 \cdot cos(40^{\circ});]

Sendo [;sen(180^{\circ} - x) = sen(x);]


Temos
[;sen(160^{\circ} - x)=;][; sen(180^{\circ} - (160^{\circ} - x)) =;]

[;sen(20^{\circ}+ x) = 2\cdot cos(40^{\circ}) \cdot sen(x)=2\cdot cos(60^{\circ} - 20^{\circ}) \cdot sen(x);]

Usando a fórmula da soma de arcos para o seno e da subtração de arcos para o cosseno obtemos:

[;sen(20^{\circ}) \cdot cos (x) +;][;cos(20^{\circ});][;\cdot;][; sen(x)=;][;cos(20^{\circ});][; \cdot sen(x);][; + \sqrt{3};][;sen(20^{\circ});][; \cdot sen(x);]

[;sen(20^{\circ}) \cdot cos(x) = \sqrt{3}sen(20^{\circ}) \cdot sen(x);]

[;ctg(x)=\sqrt{3};]

daonde [; x=30^{\circ};].

Uma outra solução é obtida de forma mais bonita.

Resolução 2:


Observe a construção abaixo


Na figura abaixo [;ED'\parallel BC;]. Seja [;P;] o ponto de encontro de[;BD';] com[;CE;]. Assim, [; \triangle{BCP};] e [;\triangle{ED'P};] são triângulos equiláteros. Ou seja, [;CP=BC;] como [;\triangle{BCD};] é isosceles, então [;\triangle{PCD};] é isosceles com ângulo do vértice [;\hat{C}=20^{\circ};], assim[;C\hat{P}D=80^{\circ};]como [;E\hat{P}D'=60^{\circ};] e [;E,P;] e [;C;] são colineares, [;D'\hat{P}C=40^{\circ};].

Como
[;D'\hat{P}C=40^{\circ};] e [;B\hat{D'}C=40^{\circ};] [;\triangle{PDD'};] é isosceles com angulo do vétice [; \hat{D}=100^{\circ};] .

Lembrando que [;\triangle{EPD'};] é equilatero. Temos [;ED'=EP;] e [;DP=DD';] assim, pelo caso LLL, [;\triangle{EPD}=\triangle{EDD'};]. Por isso, [;ED;] é bissetriz de [;P\hat{E}D';], logo, [;C\hat{E}D=30^{\circ};].








Há muitas outras soluções para esse problema. Por que você não tenta a sua?

Lembre-se: Para melhorar a qualidade de nossas postagens avalie-as logo abaixo. Se você gostou do blog recomende aos seus amigos e se inscreva por e-mail para receber nossas atualizações.

Até mais!
Related Posts Plugin for WordPress, Blogger...