Nimber - Nimber

Em matemática , os nimbers , também chamados de números de Grundy , são introduzidos na teoria dos jogos combinatórios , onde são definidos como os valores dos montes no jogo Nim . Os números são os números ordinais dotados de adição e multiplicação de números , que são distintos da adição ordinal e da multiplicação ordinal .

Por causa do teorema Sprague-Grundy, que afirma que todo jogo imparcial é equivalente a uma pilha Nim de um certo tamanho, os números surgem em uma classe muito maior de jogos imparciais. Eles também podem ocorrer em jogos partidários como Domineering .

Nimbers têm a característica de que suas opções Left e Right são idênticas, seguindo um certo esquema, e que eles são seus próprios negativos, de modo que um ordinal positivo pode ser adicionado a outro ordinal positivo usando a adição de nimber para encontrar um ordinal de valor inferior. A operação de exclusão mínima é aplicada a conjuntos de nimbers.

Usos

Nim

Nim é um jogo em que dois jogadores se revezam removendo objetos de pilhas distintas. Como os movimentos dependem apenas da posição e não de qual dos dois jogadores está se movendo no momento, e onde os pagamentos são simétricos, Nim é um jogo imparcial. Em cada jogada, um jogador deve remover pelo menos um objeto, e pode remover qualquer número de objetos, desde que todos venham da mesma pilha. O objetivo do jogo é ser o jogador que remove o último objeto. Usando a adição de nimber, cada heap pode ser somado para fornecer um valor nim para o heap. Além disso, como todos os montes juntos podem ser somados usando a adição de nim, pode-se calcular o número do jogo como um todo. A estratégia de vitória deste jogo é forçar o número cumulativo do jogo a 0 para o turno do oponente.

Cram

Cram é um jogo frequentemente jogado em um tabuleiro retangular no qual os jogadores se revezam colocando os dominós tanto horizontalmente quanto verticalmente até que nenhum outro dominó possa ser colocado. O primeiro jogador que não consegue fazer um movimento perde. Como os movimentos possíveis para ambos os jogadores são os mesmos, é um jogo imparcial e pode ter um valor nimber. Se cada linha e coluna for considerada um heap, o valor do jogo será a soma de todas as linhas e colunas usando a adição de nimber. Por exemplo, qualquer placa 2xn terá um número 0 para todos os n pares e um número 1 para todos os n ímpares.

Jogo de Northcott

Um jogo onde os pinos para cada jogador são colocados ao longo de uma coluna com um número finito de espaços. A cada vez, cada jogador deve mover a peça para cima ou para baixo na coluna, mas não pode passar pela peça do outro jogador. Várias colunas são empilhadas para adicionar complexidade. O jogador que não pode mais fazer nenhum movimento perde. Ao contrário de muitos outros jogos relacionados ao Nimber, o número de espaços entre os dois tokens em cada linha são os tamanhos dos montes de Nim. Se seu oponente aumentar o número de espaços entre duas fichas, apenas diminua em seu próximo movimento. Caso contrário, jogue o jogo de Nim e faça com que a soma de Nim do número de espaços entre as fichas em cada linha seja 0.

Hackenbush

Hackenbush é um jogo inventado pelo matemático John Horton Conway . Pode ser reproduzido em qualquer configuração de segmentos de linha coloridos conectados uns aos outros por seus pontos de extremidade e a uma linha "terra". os jogadores se revezam removendo segmentos de linha. Uma versão de jogo imparcial, portanto um jogo passível de ser analisado usando nimbers, pode ser encontrada removendo a distinção das linhas, permitindo que qualquer jogador corte qualquer galho. Quaisquer segmentos dependentes do segmento recém-removido para se conectar à linha de aterramento também são removidos. Dessa forma, cada conexão com o solo pode ser considerada um heap nim com um valor nimber. Além disso, todas as conexões separadas para a linha de terra também podem ser somadas para um nimber do estado do jogo.

Adição

A adição de Nimber (também conhecida como adição de nim ) pode ser usada para calcular o tamanho de um único heap de nim equivalente a uma coleção de heaps de nim. É definido recursivamente por

α ⊕ β = mex ({ α ′ ⊕ β  : α ' < α } ∪ { α ⊕ β ′: β ′ < β }) ,

onde o excludant mínimo mex ( S ) de um conjunto S de ordinais é definido como sendo a menor ordinal que é não um elemento de S .

Para ordinais finitos, a soma nim é facilmente avaliada em um computador tomando o bit a bit exclusivo ou (XOR, denotado por ⊕ ) dos números correspondentes. Por exemplo, a soma nim de 7 e 14 pode ser encontrada escrevendo 7 como 111 e 14 como 1110; as casas somadas a 1; a casa dos dois soma 2, que substituímos por 0; a quarta casa soma 2, que substituímos por 0; a casa dos oito é adicionada a 1. Portanto, a soma nim é escrita em binário como 1001 ou em decimal como 9.

Essa propriedade de adição decorre do fato de que mex e XOR geram uma estratégia vencedora para Nim e só pode haver uma dessas estratégias; ou pode ser mostrado diretamente por indução: sejam α e β dois ordinais finitos e suponha que a soma nim de todos os pares com um deles reduzido já esteja definida. O único número cujo XOR com α é α ⊕ β é β e vice-versa; assim, α ⊕ β é excluído. Por outro lado, para qualquer ordinal γ < α ⊕ β , XORing ξ ≔ α ⊕ β ⊕ γ com todos os α , β e γ deve levar a uma redução para um deles (uma vez que o líder 1 em ξ deve estar presente em pelo menos um dos três); como ξ ⊕ γ = α ⊕ β > γ , devemos ter α > ξ ⊕ α = β ⊕ γ ou β > ξ ⊕ β = α ⊕ γ ; assim, γ é incluído como ( β ⊕ γ ) ⊕ β ou como α ⊕ (α ⊕ γ) e, portanto, α ⊕ β é o ordinal mínimo excluído.

Multiplicação

A multiplicação Nimber (multiplicação nim ) é definida recursivamente por

α β = mex ({ α ′ β ⊕ α β ′ ⊕ α ' β ′: α ′ < α , β ′ < β }) .

Exceto pelo fato de que nimbers formam uma classe própria e não um conjunto, a classe de nimbers determina um campo algebricamente fechado de característica 2. A identidade aditiva nimber é o ordinal 0, e a identidade multiplicativa nimber é o ordinal 1. De acordo com sendo a característica 2, o nímero aditivo inverso do ordinal α é o próprio α . O inverso multiplicativo nimber do ordinal diferente de zero α é dado por 1 / α = mex ( S ) , onde S é o menor conjunto de ordinais (números) tal que

1. 0 é um elemento de S ;
2. se 0 < α '< α e β ' é um elemento de S , em seguida, [1 + (α '- α) β'] / α ' é também um elemento de S .

Para todos os números naturais n , o conjunto de números menores que 2 ^{2 n} forma o campo de Galois GF (2 ^{2 n} ) de ordem  2 ^{2 n} .

Em particular, isso implica que o conjunto de números finitos é isomórfico ao limite direto como n → ∞ dos campos GF (2 ^{2 n} ) . Este subcampo não é fechado algebricamente, visto que nenhum outro campo GF (2 ^k ) (então com k não é uma potência de 2) está contido em qualquer um desses campos e, portanto, não em seu limite direto; por exemplo, o polinômio x ³ + x + 1 , que tem uma raiz em GF (2 ³ ) , não tem uma raiz no conjunto de números finitos.

Assim como no caso da adição de nimber, há um meio de calcular o produto nimber de ordinais finitos. Isso é determinado pelas regras que

1. O produto nimber de uma potência de Fermat 2 (números na forma 2 ^{2 n} ) com um número menor é igual ao seu produto normal;
2. O nimber quadrado de um Fermat 2-potência x é igual a 3 x / 2 conforme avaliado sob a multiplicação ordinária de números naturais.

O menor campo algebricamente fechado de números é o conjunto de números menores que o ordinal ω ^{ω ω} , onde ω é o menor ordinal infinito. Segue-se que, como um número, ω ^{ω ω} é transcendental sobre o campo.

Tabuada de adição e multiplicação

As tabelas a seguir exibem adição e multiplicação entre os primeiros 16 números.
Este subconjunto é fechado em ambas as operações, uma vez que 16 tem a forma  2 ^{2 n} . (Se você preferir tabelas de texto simples, elas estão aqui .)

Adição de Nimber (sequência A003987 no OEIS )
Esta também é a tabela Cayley de Z ₂ ⁴ - ou a tabela de operações XOR bit a bit . As pequenas matrizes mostram os dígitos únicos dos números binários.

Multiplicação de Nimber (sequência A051775 no OEIS )
Os elementos diferentes de zero formam a tabela Cayley de Z ₁₅ .
As pequenas matrizes são matrizes de Walsh binárias permutadas .

Multiplicação de Nimber de potências de dois (sequência A223541 no OEIS ) O
cálculo dos produtos nim de potências de dois é um ponto decisivo no algoritmo recursivo de multiplicação de Nimber.

Veja também

• Número surreal

Notas

Referências