PiR2
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Jogos e estratégias vencedoras

2 participantes

Ir para baixo

Jogos e estratégias vencedoras Empty Jogos e estratégias vencedoras

Mensagem por Perceval Qua 03 Fev 2021, 08:09

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 não puder mais jogar perde. Quem possui a estratégia vencedora?
Perceval
Perceval
Recebeu o sabre de luz
Recebeu o sabre de luz

Mensagens : 121
Data de inscrição : 03/01/2021

Ir para o topo Ir para baixo

Jogos e estratégias vencedoras Empty Re: Jogos e estratégias vencedoras

Mensagem por NikolsLife Sex 15 Out 2021, 12:22

O primeiro a jogar possui a estratégia vencedora. Para observar isso, tente fazer o jogo de trás para frente. Veja que quem jogar no turno com (0,0) (ou seja, 0 em cada uma perde). Logo, quem jogar no turno com (1, 0); (1, 1); (2, 0) ganha. Daí, note que quem jogar no turno com (2,1) sempre perde, já que (2, 1) só leva para essas três possibilidades. Também note que quem jogar no turno com (2, x>=2) sempre pode ganhar, pois dá pra levar isso para (2, 1). Agora observemos:

(3, 0) ganha levando p (0,0)
(3, 1) ganha porque levo para (2, 1)
(3, 2) ganha levando para (1, 2)
(3, 3) ganha levando para (0,0)
(3, 4) ganha já que pode levar para (1, 2)
(3, 5) perde, pois se pudesse ganhar, ela poderia direcionar para uma tupla que perde diretamente. Mas a única tupla que perde é (1, 2) e é impossível ir daquela para esta.
(4, 0) ganha levando p (0,0)
(4, 1) ganha levando p (2, 1)
(4, 2) ganha levando p (1, 2)
(4, 3) ganha levando p (2, 1)
(4, 4) ganha levando p (0,0)
(4, 5) ganha porque pode levar para (1, 2)
(4, 6) ganha levando p (3, 5)
(4, 7) perde, pois e impossível levar pra (3, 5), (2, 1) ou (0,0)

Se continuar vai notar que, assim como (3, 5) perde, (4, 7) perde, (5, 9) perde e todos os outros possuem um caminho para a vitória. (Prove por indução ou então vai na fé porque é só até o 7 que precisa)
Continuando o padrão, o (6, 11) e o (7, 13) também perdem sempre.
Sendo assim, basta o primeiro jogador ir da situação inicial (7, 15) para (7, 13) que o segundo vai perder (é claro que o primeiro tb não pode vacilar dps disso porque quando eu digo que (x, y) ganha é porque to dizendo que existe uma estratégia para quem começa com (x, y) ganhar, não que independentemente dos movimentos começando de (x, y) o cara ganha
NikolsLife
NikolsLife
Padawan
Padawan

Mensagens : 84
Data de inscrição : 10/12/2019

Ir para o topo Ir para baixo

Ir para o topo

- Tópicos semelhantes

 
Permissões neste sub-fórum
Não podes responder a tópicos