Nimliczby

Nimliczby – liczby porządkowe ze specjalnie zdefiniowanymi działaniami wprowadzone dla określenia wielkości stosów w grze nim, ale zastosowane do szerszej klasy gier dzięki twierdzeniu Sprague’a-Grundy’ego.

Rekurencyjna definicja dodawania nimliczb wygląda następująco:

${\displaystyle 0\oplus 0=0}$

${\displaystyle \alpha \oplus \beta ={\mbox{mex}}(\{\,\alpha '\oplus \beta$ :\alpha '<\alpha \,\}\cup \{\,\alpha \oplus \beta ':\beta '<\beta \,\})}

(dla liczb naturalnych n ⊕ m oznacza n xor m)

zaś mnożenia:

${\displaystyle 0\odot \alpha =\alpha \odot 0=0}$

${\displaystyle \alpha \odot \beta ={\mbox{mex}}(\{\,(\alpha '\odot \beta )\oplus (\alpha \odot \beta ')\oplus (\alpha '\odot \beta '):\alpha '<\alpha ,\beta '<\beta \,\})}$

gdzie mex oznacza najmniejszą liczbę porządkową nieobecną w danym zbiorze.

Nimliczby spełniają warunki z definicji ciała algebraicznie domkniętego, poza tym, że nie są zbiorem. Zbiory nimliczb skończonych mniejszych od ${\displaystyle 2^{2^{n}}}$ są ciałami skończonymi.

Ujęcie intuicyjne

Nimliczby można oznaczać kolorem czerwonym. Dodawanie i mnożenie nimliczb, tak jak zwykłych liczb, są łączne i przemienne, mnożenie jest rozdzielne względem dodawania.

Reguły dodawania:

• Suma dwu równych nimliczb wynosi 0.
• Jeżeli większa z dwóch nimliczb odpowiada potędze dwójki (1, 2, 4, 8, 16, 32...) to dodaje się je według takich zasad, jak zwykłe liczby.
• dodawanie jest przemienne i łączne.

Dodawanie nimliczb odpowiada operacji XOR na cyfrach ich rozwinięcia dwójkowego.

Reguły mnożenia:

• Jeżeli większa z dwóch nimliczb jest typu 1, 2, 4, 16, 256, 65536, 4294967296..., to mnoży się je według takich zasad, jak zwykłe liczby.
• Jeżeli liczbę tego typu (z wyjątkiem 1) mnoży się przez siebie, to wynik jest równy sumie dwóch nimliczb: jej samej oraz części całkowitej jej połowy. Przykład: 7^2= 7 + część całkowita(7/2) = 7 + 3 = 4

Na przykład:

5 × 6 = (4 + 1) × (4 + 2) = (4 × 4) + (4 × 2) + (1 × 4) + (1 × 2) = 6 + 8 + 4 + 2 = 6 + 8 + 6 = 6 + 6 + 8 = 0 + 8 = 8

Potęgowanie odbywa się według zwykłych zasad, a wykładnik jest zwykłą liczbą.

a³ = a × a × a

Okazuje się, że

2² = 3

4⁴ = 5

16¹⁶ = 17

256²⁵⁶ = 257

itp.

Można też mówić o nieskończonych nimliczbach, np.

ω³ = 2

(ω + 6) + (ω + 3) + 5 = 0

W innym ujęciu:

• a ⊕ b = b ⊕ a
• a ⊙ b = b ⊙ a
• (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
• (a ⊙ b) ⊙ c = a ⊙ (b ⊙ c)
• a ⊙ (b ⊕ c) = a ⊙ b ⊕ a ⊙ c
• a ⊕ 0 = a
• a ⊕ a = 0
• a ⊕ 2ⁿ = a + 2ⁿ jeżeli a < 2ⁿ
• a ⊙ 0 = 0
• a ⊙ 1 = a
• a ⊙ 2²ⁿ = a · 2²ⁿ jeżeli a < 2²ⁿ
• 2²ⁿ ⊙ 2²ⁿ = 3 · 2^2n-1

Można je też przedstawić jako neutralną grę Hackenbusha, co pozwala na rozgałęzianie.

Tabliczka dodawania i mnożenia

Poniższe tabele przedstawiają dodawanie i mnożenie pierwszych 16 nimliczb. (Ten podzbiór jest podciałem, gdyż 16 jest postaci ${\displaystyle 2^{2^{n}}}$).

Bibliografia

• John Horton Conway, Richard Kenneth Guy, Księga liczb, ISBN 83-204-2969-2, s. 285–290.