Jogos - Subtração

Jogos - Subtração

Em geral podemos definir as regras de um jogo de subtração assim: é permitido retirar n1, n2, ..., nk palitos de qualquer pilha. Examinemos o caso de uma pilha de 0, 1, 2, 3, ..., k palitos e vemos as possíveis jogadas. O valor da pilha de k palitos é o menor resultado que não pode ser obtido de ter palitos dela. Isso é a regra chamada de mex, mínimo excluído.

Por exemplo, jogamos S(1,3,4): de qualquer pilha podem ser retirados um, três ou quatro palitos. De uma pilha vazia não pode retirar nada. mex { Æ } = 0. De uma pilha de um palito pode ser retirado um palito, reduzindo-a a zero: mex { 0 } = *1. De uma pilha de dois pode ser retirado somente um palito, deixando um: mex { *1 } = 0. De uma pilha de três pode ser retirado um ou três palitos, deixando zero ou dois: mex { 0, 0 } = *1. E de uma pilha de quatro, pode ser retirado um, três ou quatro palitos, deixando zero, um ou três: mex { 0, *1, *1} = *2. Continuando, calculamos a seqüência toda de mex, denotado G(k), com para este jogo

G = 0,1012320101232010123201012320 ...

que é seqüência periódica de período 7. G = 0,1012320

A estratégia de jogar é análoga à de Nim. Procura-se tornar a soma dos valores das pilhas igual a zero após a sua jogada, e mantê-la igual a zero após a sua jogada sempre. Por exemplo, se neste jogo houver as quatro pilhas do jogo de Nim de 2, 3, 8 e 9 palitos, avalia-se as pilhas pelo G do jogo: G(2) = 0, G(3) = *1, G(8) = *1 e G(9) = 0. A soma é zero e portanto o segundo a jogar pode garantir vitória, pois o primeiro a jogar não tem como manter a soma igual a zero na sua jogada.

A seqüência mex de qualquer jogo de subtração simples é sempre periódica.