OBM - Em um jogo de duas pessoas, os jogadores tiram, alternadamente,
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
a) 1
b) 2
c) 3
d) 4
e) 5
Passo 1
O enunciado descreve um jogo em que há inicialmente
palitos e, a cada jogada, um jogador retira
ou
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
palitos é perdedora (P-posição), pois quem tiver de jogar não pode mover e, portanto, perde. Se uma posição
for tal que toda jogada (remover
a
) leve a uma N-posição, então
é P-posição.
Verifica-se por indução que todas as posições com número de palitos múltiplo de são P-posições. De fato, se
, qualquer remoção de
a
palitos deixa
, que não é múltiplo de
, ou seja, uma N-posição.
Verifica-se por indução que todas as posições com número de palitos múltiplo de
Passo 3
A estratégia vencedora é: estando em uma N-posição (não múltiplo de
), o jogador deve remover
palitos de modo que a posição resultante seja múltiplo de
, ou seja, escolher
Passo 4
No início,
. Calculamos
Logo, o primeiro jogador deve tirar
palitos para deixar
, que é múltiplo de
(P-posição), assegurando a vitória.
Resposta
4 palitos.