OBM - Em um jogo de duas pessoas, os jogadores tiram, alternadamente, 1,2,3,4 ou 5 palitos de uma pilha que inicialmente tem 1.000 palitos. Ganha o jogador que tirar o último palito da pilha. Quantos palitos o jogador que começa deve tirar na sua jogada inicial de modo a assegurar sua vitória?
a) 1
b) 2
c) 3
d) 4
e) 5

Passo 1

O enunciado descreve um jogo em que há inicialmente 1000 palitos e, a cada jogada, um jogador retira 1,2,3,4 ou 5 palitos. Ganha quem tirar o último palito. Vamos usar a teoria de jogos para posições de vitória (N-posições) e derrota (P-posições) em jogos de subtração.

Passo 2

Observe que a posição com 0 palitos é perdedora (P-posição), pois quem tiver de jogar não pode mover e, portanto, perde. Se uma posição n for tal que toda jogada (remover 1 a 5) leve a uma N-posição, então n é P-posição.
Verifica-se por indução que todas as posições com número de palitos múltiplo de 6 são P-posições. De fato, se n=6k, qualquer remoção de 1 a 5 palitos deixa n-r=6k-r, que não é múltiplo de 6, ou seja, uma N-posição.

Passo 3

A estratégia vencedora é: estando em uma N-posição (não múltiplo de 6), o jogador deve remover r palitos de modo que a posição resultante seja múltiplo de 6, ou seja, escolher
r equiv n pmod6

Passo 4

No início, n=1000. Calculamos
1000 bmod 6 = 4
Logo, o primeiro jogador deve tirar 4 palitos para deixar 1000-4=996, que é múltiplo de 6 (P-posição), assegurando a vitória.

Resposta

4 palitos.

Exercícios de Livros Relacionados