O Jogo de Bachet |
|
|
O Jogo de Bachet funciona da seguinte forma: são colocadas n pedras numa mesa. Cada jogador, alternadamente, retira 1, 3 ou 6 pedras na sua vez. O jogador que não conseguir jogar (porque não há pedras na mesa) perde o jogo. Vamos assumir que os jogadores não cometem erros, jogando na perfeição. Por exemplo, numa mesa com cinco pedras ganha o primeiro jogador. Como? Se tirar três pedras, deixa duas na mesa. Assim, o segundo jogador apenas pode tirar uma pedra (a sua única jogada válida) deixando ainda uma pedra na mesa. Volta a ser a vez do primeiro jogador e este retira a última pedra, ganhando a partida. Outro exemplo: uma mesa vazia (com zero pedras iniciais) é uma vitória para o segundo jogador, dado que o primeiro jogador não consegue jogar. Calcule a lista dos vencedores para os jogos entre zero e mil pedras. A posição n+1 desta lista deve indicar o vencedor do jogo de Bachet para n pedras, sendo igual a 1 se for uma vitória do primeiro jogador, ou 2 se vencer o segundo jogador. Os primeiros valores desta lista são: 2 1 2 1 2 1 1 1 1 2... Note que a primeira posição da lista indica a vitória do jogo com zero pedras. Devolva a soma desta lista. |
|