Olá meus amigos nerds. Hoje vamos brincar (literalmente) de comer bolinhas de chocolate. Já que é isso que o problema 11629. Competiçăo de chocolate nos pede para fazer. Mais especificamente, dado o jogo em que dois jogadores comem bolinhas de chocolate de modo alternado, com a restrição de que há n bolinhas e que um jogador pode comer no máximo m delas de cada vez. Determinar quem ganha o jogo, se o jogador que começou ou o que jogou em segundo lugar.
Solução
Para quem já conhece, esse jogo é uma variação d Nim. A ideia para resolver esse problema é simples:
a) Se m >= n o jogador que começa pode comer todas as bolinhas de chocolate e ganhar o jogo.
b) Se m < n, teríamos.
1 Se há 1, 2, ..., m bolinhas restantes, então quem joga ganha (ele pode comer todas as bolinhas)
2 Se há m+1 bolinhas então quem joga perde, pois ele não pode comer todas as bolinhas e qualquer número de bolinhas que ele comer resulta em uma configuração em que o outro jogador pode comer todas as bolinhas.
3 Se há m+1,..., 2m+1 bolinhas quem joga ganha, basta comer de modo a restar m+1 bolinhas (cenário em que quem joga, ou seja, seu adversário perde, dado o item 2).
Do esposto acima é possível concluir que se n == 0 mod m+1 quem joga perde. Então vamos a indução (vale para 1, suponha que vale para n, prove que vale para n+1): Suponha que essa relação valha para n. Para n+1 teríamos:
n+1 == 1 mod m+1 já que n == 0 mod m+1, ou seja, quem joga ganha pois ele pode comer uma bolinha e deixar que o outro jogador perca, uma vez que o segundo jogador estará na situação em que n == 0 mod m+1. Logo a relação vale para n+1, cqd.
a) Se m >= n o jogador que começa pode comer todas as bolinhas de chocolate e ganhar o jogo.
b) Se m < n, teríamos.
1 Se há 1, 2, ..., m bolinhas restantes, então quem joga ganha (ele pode comer todas as bolinhas)
2 Se há m+1 bolinhas então quem joga perde, pois ele não pode comer todas as bolinhas e qualquer número de bolinhas que ele comer resulta em uma configuração em que o outro jogador pode comer todas as bolinhas.
3 Se há m+1,..., 2m+1 bolinhas quem joga ganha, basta comer de modo a restar m+1 bolinhas (cenário em que quem joga, ou seja, seu adversário perde, dado o item 2).
Do esposto acima é possível concluir que se n == 0 mod m+1 quem joga perde. Então vamos a indução (vale para 1, suponha que vale para n, prove que vale para n+1): Suponha que essa relação valha para n. Para n+1 teríamos:
n+1 == 1 mod m+1 já que n == 0 mod m+1, ou seja, quem joga ganha pois ele pode comer uma bolinha e deixar que o outro jogador perca, uma vez que o segundo jogador estará na situação em que n == 0 mod m+1. Logo a relação vale para n+1, cqd.
Nenhum comentário:
Postar um comentário