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
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
Balas na mesa. Como o segundo pode comer no máximo 
na sua vez, ele deixa um mínimo de duas balas na mesa, e eum máximo de 
. 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!
- Questão 74 ? Prova Do Estado ? (ofa) 2.014 ? Professor De Educação Básica Ii
Pedro e Ivo estão disputando um jogo em que não há empates. Eles devem disputar, no mínimo, duas partidas. Ganha o jogo aquele que vencer duas partidas seguidas, ou, então, três partidas alternadas. O número de sequências distintas de resultados...
- Prova Da Olimpíada De Matemática Da Lusofonia.
Pessoal, hoje vou postar a prova da OMCPLP (Olimpíada de Matemática da Comunidade dos Países de Língua Portuguesa). A competição, que este ano teve realizada sua segunda edição, ocorreu na cidade de Salvador, BA, entre os dias 20 e 28 de Julho....
- Jogo Matemático: Dedo No Gatilho
Crianças têm muita dificuldade em “decorar” a tabuada. Uma das maneiras de tornar essa atividade mais prazerosa e menos monótona é utilizar jogos matemáticos como apoio. Um deles é o dedo no gatilho que é adequado para crianças de 8 a 11 anos....
- Feche A Caixa (multiplicação)
MATERIAL: Tabuleiro, 40 marcadores e dois dados (1 de 6 faces e 1 de 10 faces)- Tabuleiro para impressão - versão pdf -REGRAS: 1. Distribuir o material para as duas equipes. 2. Decidir qual das equipes iniciará o jogo. 3. O jogador joga os...
- Teoria De Conjuntos
Resolveremos dois problemas envolvendo teoria de conjuntos, utilizando as operações de união, intersecção, diferença e complementar de um conjunto. Exemplo 1. A segunda fase de um concurso público foi constituída de dois problemas: 340 candidatos...