quinta-feira, 23 de agosto de 2012

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!

Nenhum comentário:

Postar um comentário

Você pode comentar! A equipe do blog encoraja todos a comentar.

Porém, lembre-se que comentários que desrespeitem as regras abaixo serão excluídos:

-É proibido ofender qualquer pessoa ou grupo em seu comentário.
-Os comentários deverão ser minimamente relacionados com o tópico. Lembrem-se, estamos falando de um blog de matemática!
-Proibido flood.
-Proibido palavras de baixo calão.
-Proibido colocar qualquer tipo de conteúdo improprio para menores de 18 anos (há menores de idade que acessam o blog).

A equipe do blog agradece seu comentário, e tenha certeza que será muito enriquecedor. Tentaremos respondê-los o quanto antes possível.

Related Posts Plugin for WordPress, Blogger...