Polos Olmpicos de Treinamento

Curso de Combinatria - Nvel 2 Aula 6

Prof. Bruno Holanda

Jogos

Quando falamos em jogos, pensamos em varios conhecidos como: xadrez, as damas e os

jogos com baralho. Porem, nao s ao desses jogos que iremos falar neste material. Imagine
que exista algum tipo de jogo em que voce pudesse ganhar sempre, independente de como
seu adversario jogasse? Seria uma boa, n ao?! Pois esses jogos existem e s ao um dos
assuntos mais abordados em provas de olimpada. Nesta aula vamos mostrar varios destes
jogos e as principais estrategias vencedoras: a simetria e o uso das posico
es vencedoras.

1. Simetria

Uma das estrategias mais simples e o uso de alguma simetria que pode ocorrer durante
o jogo em vantagem de um dos jogadores, forcando sempre uma nova rodada para o jogador
destinado `a derrota. Para entender melhor veja o seguinte exemplo:

Problema 1. Pedro e M onica jogam em um tabuleiro 1 11. Cada um, em sua vez, pode
pintar um dos quadrados (que nao foram pintados anteriormente), ou dois quadrados con-
secutivos (se ambos estiverem brancos). Quem nao puder mais jogar perde. Sabe-se que
Pedro sera o primeiro a jogar. Quem pode sempre garantir a vitoria?

ao. Pedro sempre poder

Soluc a ganhar se seguir a seguinte estrategia:

(i) Inicialmente, Pedro deve pintar o quadrado do meio.

(ii) Agora, depois que M onica fizer sua jogada, Pedro deve jogar sempre simetricamente
em relacao ao centro do tabuleiro (i.e. sempre deixando o tabuleiro simetrico). Por
exemplo, se M onica jogar nas casas 9 e 10, Pedro deve jogar nas casas 2 e 3.

z z
POT 2012 - Combinat
oria - Nvel 2 - Aula 6 - Prof. Bruno Holanda

(iii) Assim, M onica nunca poder a ganhar, pois na sua jogada ela quebra a simetria e a
configuracao final do jogo todas as casas estarao pintadas, ou seja, a configuracao e
simetrica.

O proximo exemplo e um dos problemas que apareceu na prova da OBM de 2004. Vamos
apresentar uma solucao diferente da solucao proposta na Eureka! 22, usando simetria:

Problema 2. Arnaldo e Bernardo disputam um jogo em um tabuleiro 2 n :

As pecas do jogo s
ao dominos 2 1. Inicialmente Arnaldo coloca um domino cobrindo
exatamente duas casas do tabuleiro, na horizontal ou na vertical. Os jogadores se revezam
colocando uma peca no tabuleiro, na horizontal ou na vertical, sempre cobrindo exata-
mente duas casas do tabuleiro. N ao e permitido colocar uma peca sobre outra ja colocada
anteriormente. Quem nao conseguir colocar uma peca no tabuleiro perde.

Qual dos dois jogadores tem uma estrategia vencedora, ou seja, uma estrategia que o
leva `a vitoria quaisquer que sejam as jogadas de seu adversario, para:
a) n = 2004?
b) n = 2005?

ao. Quando n = 2005 o primeiro jogador garante a vitoria. Ele pode fazer isto colo-
Soluc
cando um domino na vertical no meio do tabuleiro e, em seguida, jogar simetricamente ao
segundo jogador. Quando n = 2004 o tabuleiro possui um n umero par de colunas. Desse
modo, o segundo ganha jogando simetricamente ao primeiro jogador.

Como voce deve ter visto, usar a simetria e realmente uma tecnica muito eficiente.
Porem, `as vezes, usar apenas a simetria nao e suficiente para resolver o problema. Observe
o proximo exemplo retirado da olmpiada da Bielor ussia de 2000.

Problema 3. Tom e Jerry jogam o seguinte jogo. Eles colocam alternadamente pinos
identicos em casas vazias de um tabuleiro 20 20 (um pino de cada vez). Tom e o primeiro
a jogar. Vence quem, em sua jogada, formar um bloco de quatro pinos vizinhos. Dois pinos
s
ao vizinhos se estiverem em casas com um lado em comum. Determine quem possui a
estrategia vencedora.

ao. Jerry deve jogar simetricamente em relacao ao centro do tabuleiro. Assim

Soluc
que Tom formar tres um bloco de tres pinos vizinhos, Jerry deve abandonar a estrategia
simetrica e completar o bloco de quatro pinos vizinhos.

2
POT 2012 - Combinat
oria - Nvel 2 - Aula 6 - Prof. Bruno Holanda

2. Posi
c
oes Vencedoras

Alguns tipos de jogos possuem certas configuracoes que sempre levam um jogador `a
vitoria. Essas configuracoes s
ao chamadas de posicoes vencedoras. O proximo exemplo e
um jogo bastante simples em que essa estrategia aparece facilmente.

Problema 4. Na primeira casa de um tabuleiro 1 13 esta uma moeda. Tiago e Maria

movem a moeda alternadamente. Em cada turno e permitido avancar 1, 2, 3, 4 ou 5 casas.
Quem colocar a moeda na ultima casa e o vencedor. Se Maria comecar jogando, ela pode
ter certeza da vitoria?

Soluc ao. Como em muitos problemas de olimpada, vamos analisar alguns casos pequenos.
Vamos supor que em vez de 13 casas o tabuleiro tivesse apenas quatro. Neste caso, fica
facil ver que quem comeca ganha basta avancar tres casas.
O mesmo iria ocorrer se o tabuleiro tivesse 2, 3, 4, 5 ou 6 casas. Porem, em um tabuleiro
7 1 o primeiro jogador perde. Veja que ap os a primeira jogada a moeda estara em uma
das casas 2, 3, 4, 5 ou 6. E ja sabemos que essas casas levam o jogador `a vitoria.

Desse modo, vamos dizer que 7 e uma posicao perdedora e 6, 5, 4, 3 e 2 s ao posicoes

vencedoras. Assim, se um o jogador estiver em uma das casas 8, 9, 10, 11 ou 12, ele pode
garantir a vitoria movendo a moeda para a casa 7, deixando o seu adversario em uma
posicao perdedora. Com isso, podemos afirmar que as posicoes 8, 9, 10, 11 e 12 tambem s ao
posicoes vencedoras.
Resta analisar a 13a casa. Observe que a partir desta casa podemos mover a moeda
apenas para uma das casas 8, 9, 10, 11 ou 12 que s
ao vencedoras. Da, quem comecar perde
pelo simples fato de iniciar em uma posicao perdedora.

A grande dificuldade para a maioria dos alunos e descobrir quais s

ao as posicoes vence-
doras de um jogo. Para evitar esse tipo de problema, tenha sempre em mente as seguintes
definicoes:

(a) Posicao vencedora: A partir dela, podemos escolher um movimento

e repassar uma posicao perdedora para o adversario.

(b) Posicao perdedora: A partir dela, e impossvel escolher um mo-

vimento e repassar uma posicao perdedora para o adversario. Ou
seja, nao importa o movimento escolhido, o adversario ir
a receber uma
posicao vencedora.

3
POT 2012 - Combinat
oria - Nvel 2 - Aula 6 - Prof. Bruno Holanda

E como fazer para descobrir quais s ao as posicoes vencedoras e perdedoras? A melhor

maneira de se fazer isto e analisando o final do jogo e aplicar as definicoes acima. Vamos
praticar um pouco resolvendo o proximo problema.

Problema 5. Em um tabuleiro 8 8, uma torre esta na casa a1. Dois jogadores movem a
torre com objetivo de colocar a torre na casa h8. Sabendo que a torre pode mover-se apenas
para cima ou para direita (quantas casas o jogador desejar) e que nao pode-se passar a vez,
determine qual jogador tem a estrategia vencedora.

Solucao. Primeiramente note que todas as casas da u ltima linha e da u

ltima coluna (exceto
a h8) s ao vencedoras pois, a partir delas podemos escolher um movimento que nos leve `a
vitoria. Com, isso a casa g7 se torna perdedora pois, a partir dela qualquer movimento leva
o outro jogador a uma posicao vencedora (veja a figura 1).

Figura 1 Figura 2 Figura 3

Agora, como g7 e perdedora, as demais casas da setima linha e da setima coluna s

ao
vencedoras. Mais ainda, a casa f 6 tambem deve ser perdedora (figura 2). Continuando
de maneira an
aloga, obtemos que a casa a1 e perdedora (figura 3). Logo, quem comecar,
perde.

Problemas Propostos

Problema 6. Sobre uma mesa existem duas pilhas (uma com 15 e outra com 16 pedras). Em
um jogo cada jogador pode, em sua vez, retirar qualquer quantidade de pedras de apenas
uma pilha. Quem nao puder mais jogar perde. Quem possui a estrategia vencedora?

Problema 7. Dois jogadores colocam alternadamente bispos (da mesma cor) em um ta-
buleiro 8 8, de forma que nenhum bispo ataque outro. Quem nao puder mais jogar
perde.

Problema 8. Dois jogadores colocam alternadamente reis (da mesma cor) em um tabuleiro
9 9, de forma que nenhum rei ataque outro. Quem nao puder mais jogar perde.

Problema 9. Sao dados um tabuleiro de xadrez (8 8) e palitinhos do tamanho dos lados

das casas do tabuleiro. Dois jogadores jogam alternadamente e, em cada rodada, um dos

4
POT 2012 - Combinat
oria - Nvel 2 - Aula 6 - Prof. Bruno Holanda

jogadores coloca um palitinho sobre um lado de uma das casas do tabuleiro, sendo proibido
sobrepor os palitinhos.
Vence o jogador que conseguir completar primeiro um quadrado 1 1 de palitinhos. Su-
pondo que nenhum dos jogadores cometa erros, qual dos dois tem a estrategia vencedora?

Problema 10. Sao dados vinte pontos ao redor de um crculo. Cada jogador em sua vez
pode ligar dois desses pontos se essa novo segmento nao cortar os feitos anteriormente.
Quem nao puder mais tracar nenhum segmento perde.

Problema 11. Dois jogadores colocam alternadamente xs e os em um tabuleiro 9 9. O

primeiro escreve xs e o segundo os. Quando o tabuleiro for completamente preenchido o
jogo termina e os pontos sao contados. Um ponto e dado ao jogador para cada linha ou
coluna em que ele possuir mais casas dos que o adversario. O jogador que possuir mais
pontos vence. Quem pode sempre ganhar?

Problema 12. Um pino esta no centro de um tabuleiro 11 11. Dois jogadores movem
alternadamente o pino para qualquer outra casa do tabuleiro, mas a cada movimento (a
partir do segundo) deve ser maior que o anterior. O jogador que nao puder mais jogar
perde. Ache a estrategia vencedora.

Problema 13. Um jogo consiste em quebrar um tabuleiro 5 10 ao longo de suas linhas.

Ganha o primeiro jogador que obter um quadrado 1 1. Quem tem a estrategia vencedora?

Problema 14. (R ussia 1997) Os n umeros 1, 2, 3, ..., 1000 s

ao escritos no quadro. Dois joga-
dores apagam alternadamente um dos n umeros da lista ate que s o restem dois n
umeros. Se
a soma desses n
umeros for divisvel por 3, o primeiro jogador vence, caso contrario vence o
segundo. Quem tem a estrategia vencedora?

Problema 15. Sobre uma mesa existem duas pilhas de moedas com 11 moedas cada. Em
cada turno, um jogador pode retirar duas moedas de uma das pilhas ou retirar uma moeda
de cada pilha. O jogador que nao puder mais fazer movimentos perde.

Problema 16. Tom e Jerry jogam um jogo e Tom faz a primeiro passo. Em cada turno o
jogador pode diminuir de um dado natural N um dos seus dgitos nao-nulos. Inicialmente
o n
umero N e 1234. O jogador que obter zero ganha. Quem pode garantir a vitoria?

Problema 17. Uma pilha de 500 pedras e dada. Dois jogadores jogam o seguinte jogo: Em
cada turno, o jogador pode retirar 1, 2, 4, 8, ... (qualquer potencia de 2) pedras da pilha. O
jogador que nao puder mais jogar perde.

Problema 18. Em uma caixa existem 300 bolinhas. Cada jogador pode retirar nao mais do
que a metade das bolinhas que estao na caixa. O jogador que n
ao puder mais jogar perde.

Problema 19. Sobre uma mesa existem duas pilhas (uma com 7 e outra com 15 pedras).
Em um jogo cada jogador pode, em sua vez, retirar qualquer quantidade de pedras de
apenas uma pilha ou a mesma quantidade de ambas as pinhas. Quem nao puder mais
jogar perde. Quem possui a estrategia vencedora?

5
POT 2012 - Combinat
oria - Nvel 2 - Aula 6 - Prof. Bruno Holanda

Dicas e Solu
c
oes

6. O jogador 1 deve retirar uma pedra da pilha com 16. Em seguida, deve jogar sime-
tricamente em relacao ao jogador 2.

7. Divida o tabuleiro em duas partes, cada uma formada por 4 linhas. O jogador 1 deve
jogar entao simetricamente.

8. O primeiro jogador deve colocar um rei no centro, e depois jogar simetricamente em

relacao ao centro do tabuleiro.

14. Observe que a soma de dois elementos opostos sempre e 1002, que e um m
ultiplo de
3.

15. Construa um tabuleiro 11 11, onde a casa (i, j) represente quantidade de pedras em
cada pilha. Observe que o movimento do jogo original e equivalente ao movimento
do cavalo no tabuleiro. Termine o problema descobrindo as posicoes vencedoras e
perdedoras atraves de inducao retroativa.

17. Pense nos m

ultiplos de 3. Nenhuma potencia de 2 e m
ultiplo de 3.

18. Pense nas potencias de 2.

19. Novamente, use a ideia do tabuleiro que foi usada para resolver o problema 15.