15.4 C
Brasília
quinta-feira, maio 15, 2025

estratégia – Seth e Cain se revezam escolhendo números de 1 a 50. Quem ganha?


Poderíamos chegar à solução observando que este jogo é efetivamente Kayles de Dawsonum jogo imparcial e aplicando o Teorema de Sprague-Grundy para encontrar o valor Nim da posição inicial.

Mas, em vez disso, vamos dar uma estratégia vencedora explícita.

Primeiro, é útil classificar os números em cadeias de duplicações, as linhas abaixo, onde cada turno take away dois números consecutivos dentro de uma linha:

 1  2  4  8 16 32
 3  6 12 24 48
 5 10 20 40
 7 14 28
 9 18 36
11 22 44
13 26
15 30
17 34
19 38
21 42
23 46
25 50

Os números ímpares de 27 a 50 são omitidos porque não podem ser usados. Mais geralmente, qualquer número deixado sem vizinhos após remoções é inútil, e podemos imaginar que ele desapareça.

Vamos mostrar como Seth (o jogador inicial) vence garantindo que um número ímpar de turnos aconteça, o que o coloca como o último jogador a ir e, portanto, o vencedor. As 10 fileiras de comprimento 2 ou 3 ocupam um turno cada. A fileira de comprimento 5 sempre ocupa 2 turnos — a primeira deixa uma fileira de 3, ou uma fileira de 2 e um singleton inútil. Então, essas sempre ocupam 12 turnos, o que não afeta a paridade.

Então, isso deixa as fileiras de comprimento 4 e 6, que podem levar diferentes números de voltas dependendo de quais pares são removidos. Seth começa removendo os números 1 e 2, agora deixando duas fileiras de comprimento 4 (4-8-16-32 e 5-10-20-40). Agora, sempre que Cain se transfer em uma delas, Seth apenas espelha na outra, o que resulta em um número par de voltas adicionais ali, contando ímpar o movimento inicial de Seth. Então, Seth vence.

Related Articles

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Stay Connected

0FansLike
0FollowersFollow
0SubscribersSubscribe
- Advertisement -spot_img

Latest Articles