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 = 2^k -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 = 2^t – 1, ou seja, que o segundo ganhei. Como sabemos, se tivermos um inteiro b = 2^2t – 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 = 2^2t – 1, se subtrairmos o inteiro mais próximo de sua metade, teremos b + 1 – n = 2^t, 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 = 2^k – 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!