Nimber
In mathematics, the nimbers, also called Grundy numbers, are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim.
Because of the Sprague–Grundy theorem which states that every impartial game is equivalent to a Nim heap of a certain size, nimbers arise in a much larger class of impartial games.
The nimber addition and multiplication operations are associative and commutative.
In particular for some pairs of ordinals, their nimber sum is smaller than either addend.
[1] The minimum excludant operation is applied to sets of nimbers.
Nim is a game in which two players take turns removing objects from distinct heaps.
The winning strategy is to force the nimber of the game to 0 for the opponent's turn.
[2] Cram is a game often played on a rectangular board in which players take turns placing dominoes either horizontally or vertically until no more dominoes can be placed.
As the possible moves for both players are the same, it is an impartial game and can have a nimber value.
Unlike many other nimber related games, the number of spaces between the two tokens on each row are the sizes of the Nim heaps.
If your opponent increases the number of spaces between two tokens, just decrease it on your next move.
Else, play the game of Nim and make the Nim-sum of the number of spaces between the tokens on each row be 0.
[3] Hackenbush is a game invented by mathematician John Horton Conway.
Players take turns removing line segments.
In this way, each connection to the ground can be considered a nim heap with a nimber value.
Additionally, all the separate connections to the ground line can also be summed for a nimber of the game state.
This property of addition follows from the fact that both mex and XOR yield a winning strategy for Nim and there can be only one such strategy; or it can be shown directly by induction: Let α and β be two finite ordinals, and assume that the nim-sum of all pairs with one of them reduced is already defined.
On the other hand, for any ordinal γ < α ⊕ β, XORing ξ with all of α, β and γ must lead to a reduction for one of them (since the leading 1 in ξ must be present in at least one of the three); since
In fact, it even determines an algebraically closed field of characteristic 2, with the nimber multiplicative inverse of a nonzero ordinal α given by
Therefore, the set of finite nimbers is isomorphic to the direct limit as n → ∞ of the fields GF(22n).
This subfield is not algebraically closed, since no field GF(2k) with k not a power of 2 is contained in any of those fields, and therefore not in their direct limit; for instance the polynomial x3 + x + 1, which has a root in GF(23), does not have a root in the set of finite nimbers.
This is determined by the rules that The smallest algebraically closed field of nimbers is the set of nimbers less than the ordinal ωωω, where ω is the smallest infinite ordinal.
This is also the Cayley table of Z 2 4 – or the table of bitwise XOR operations.
The small matrices show the single digits of the binary numbers.
The nonzero elements form the Cayley table of Z 15 .
The small matrices are permuted binary Walsh matrices .
Calculating the nim-products of powers of two is a decisive point in the recursive algorithm of nimber-multiplication.