estratégia – Quem ganha este jogo de remoção de correspondência?

Existe uma estratégia vencedora para o jogador que vai

primeiro, e começa com 45 partidas.

Aqui está o porquê:

O único caso de perda é quando resta apenas 1 partida – com qualquer número maior de partidas, um jogador poderá escolher 1 partida como jogada válida. Portanto, qualquer jogador que conseguir vencer todas as partidas, exceto uma, vencerá. A única vez que um jogador pode vencer todas as partidas, exceto 1, é quando há 2 partidas, então esse é um caso de vitória, e se houver 3 partidas, é um caso de derrota, já que o único movimento válido é pegar exatamente 1 partida, deixando 2. partidas. Então, para resumir:

– o jogador começa seu turno com 1 partida: derrota
– o jogador começa seu turno com 2 partidas: vitória
– o jogador começa seu turno com 3 partidas: derrota

Portanto, se um jogador conseguir vencer todas as partidas, exceto 3, ele pode garantir uma vitória. Isso é possível se faltarem 4, 5 ou 6 partidas, mas se faltarem 7 partidas, eles terão que disputar 4, o que é mais da metade. As únicas opções que um jogador tem se começar seu turno com 7 partidas é pegar 1, 2 ou 3, deixando o outro jogador com 4, 5 ou 6 – todas condições de vitória, conforme estabelecido anteriormente.

Portanto, se um jogador conseguir vencer todas as partidas, exceto 7, ele pode garantir uma vitória. Para sair de 7 partidas, o máximo que um jogador pode ter no início do turno é 14, e se iniciar o turno com 15 partidas, será obrigado a deixar o outro jogador com entre 8 e 14 partidas, garantindo que o outro jogador vencerá.

Você está vendo o padrão?

Até agora, nossos casos de perda são 1, 3, 7 e 15 – todos na forma $2^n-1$. Isso faz sentido – se você tiver $2^n-1$ partidas, você pode levar até $2^{n-1}-1$ fósforos – mas você não pode pegar $2^{n-1}$ partidas, e não importa quantas partidas você faça, o outro jogador sempre pode responder de forma que você fique com $2^{n-1}-1$ partidas, o que acabará levando você a apenas 1 partida.

Então a estratégia very best é

para o jogador que for primeiro vencer 45 partidas, restando 255 para o adversário. Nos turnos subsequentes, eles devem pegar quantos forem necessários para deixar 127, depois 63, depois 31, depois 15, depois 7, depois 3 e, eventualmente, 1.