Kayles

Kayles

O jogo de Kayles envolve formalmente uma ou mais filas de pinos de boliche. Cada jogador pode derrubar um pino sozinho ou dois adjacentes, até não haver mais pino algum (e evidentemente é obrigado a derrubar pelo menos um). Denotamos uma fila de n pinos por Kn, e uma configuração de duas filas de n e m pinos de Kn+Km.

Como exemplo, uma fila de cinco pinos, K5, permite passagem para as cinco configurações seguintes: K4, K3, K2+K2, K3+K1, K2+K1, conforme o jogador derrubar um ou dois pinos, e quais deles ele derruba. Kayles foi vendido como jogo no início do século na Inglaterra e é jogo imparcial. Equivale um jogo "tipo Nim" mas com possível divisão de pilhas em duas subpilhas, com remoção de um ou dois palitos. Novamente, cada jogador pode mexer com somente uma pilha a cada jogada. Os valores serão sempre Nim-pilhas *n. Em jogos imparciais o valor é sempre ou zero (ganha o segundo a jogar) ou *n (ganha o primeiro a ganhar). Em Kayles, com um, dois, três ou quatro pinos em fila, ganha o primeiro a jogar. Com cinco pinos iniciais, a sua jogada seria uma das cinco enumeradas acima. Se jogar para K4 ou K3, ele perde. E os outros?

Kayles é exemplo de um jogo de subtração de tipo diferente dos jogos S(n1, n2, ... nk) : dadas m pilhas de palitos, com n1, n2, ..., nm palitos em cada pilha, e tendo como regra

i)pode-se retirar 1 ou 2 palitos de uma pilha qualquer, e/ou; ii)após retirar 1 ou 2 palitos da pilha, pode-se dividir uma pilha em 2 sub-pilhas; temos um jogo de subtração em geral. A análise é feita da mesma maneira de que em Nim e outros jogos de subtração. Kayles é um portanto outro exemplo de um jogo de subtração, com a seguinte mex-seqüência.

n = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... G (n) = 0. 1 2 3 1 4 3 2 1 4 2 6 4 1 2 7 1 ...

Vamos entender a determinação desta seqüência. Uma fila de zero pinos vale zero. Uma fila de um resulta invariavelmente em zero, e a regra mex implica que este vale *1. Uma fila de dois pode se tornar fila de um ou nenhum, com valores *1 e 0. Assim, a regra mex afirma que vale *2. A fila de três pode se tornar fila de dois, de um ou duas filas de um (tirando o pino do meio), rendendo valores *2, *1 e *1+*1 = 0. Logo, vale *3. Uma fila de quatro pode se tornar uma fila de três, de dois ou duas filas de um ou uma fila de 1 e outrd de 2, de valores *3, *2, *1+*1 = 0 e *1 + *2 = *3. O menor valor omitido é *1 e portnato este é o valor da fila de quatro. Deixamos como exercício a confirmação da seqüência-mex de Kayles para 5 ou mais pinos. Vemos imediatamente que Kayles poderia ser chamado, por exemplo, de (1,2)-Kayles: i.e. estas regras podem ser alteradas livremente, permitindo a criação de toda uma gama de jogos distintos.

Outra opção para Kayles é de arranjar os pinos não em filas simples mas em figuras mais complexas. Na figura embaixo à esquerda, há três jogadas distintas, ou dividindo-a em três ou quatro pinos separados ou deixando como resto a figura à direita.

Qual seria o valor das duas figuras acima? Vejamos a figura à direita: esta pode se tornar após uma jogada uma das opções ilustradas embaixo. Os valores de cada uma é colocado embaixo.

Simplificando, estes valores são 0, 0, *3, *3 e *1 respectivamente. Logo, pela regra mex, o valor da figura lá encima à direita é *2. Repare que é diferente do valor de quatro pinos em fila: *2.