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.

Definicja intuicyjna

Nimliczby – liczby, które różnią się od zwykłych liczb naturalnych i porządkowych sposobem wykonywania działań.

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

$0\oplus 0=0$

$\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:

$0\odot \alpha =\alpha \odot 0=0$

$\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 $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 $2^{2^{n}}$).

Dodawanie nimliczb

+	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1	0	3	2	5	4	7	6	9	8	11	10	13	12	15	14
2	2	3	0	1	6	7	4	5	10	11	8	9	14	15	12	13
3	3	2	1	0	7	6	5	4	11	10	9	8	15	14	13	12
4	4	5	6	7	0	1	2	3	12	13	14	15	8	9	10	11
5	5	4	7	6	1	0	3	2	13	12	15	14	9	8	11	10
6	6	7	4	5	2	3	0	1	14	15	12	13	10	11	8	9
7	7	6	5	4	3	2	1	0	15	14	13	12	11	10	9	8
8	8	9	10	11	12	13	14	15	0	1	2	3	4	5	6	7
9	9	8	11	10	13	12	15	14	1	0	3	2	5	4	7	6
10	10	11	8	9	14	15	12	13	2	3	0	1	6	7	4	5
11	11	10	9	8	15	14	13	12	3	2	1	0	7	6	5	4
12	12	13	14	15	8	9	10	11	4	5	6	7	0	1	2	3
13	13	12	15	14	9	8	11	10	5	4	7	6	1	0	3	2
14	14	15	12	13	10	11	8	9	6	7	4	5	2	3	0	1
15	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0

Mnożenie nimliczb

×	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
2	0	2	3	1	8	10	11	9	12	14	15	13	4	6	7	5
3	0	3	1	2	12	15	13	14	4	7	5	6	8	11	9	10
4	0	4	8	12	6	2	14	10	11	15	3	7	13	9	5	1
5	0	5	10	15	2	7	8	13	3	6	9	12	1	4	11	14
6	0	6	11	13	14	8	5	3	7	1	12	10	9	15	2	4
7	0	7	9	14	10	13	3	4	15	8	6	1	5	2	12	11
8	0	8	12	4	11	3	7	15	13	5	1	9	6	14	10	2
9	0	9	14	7	15	6	1	8	5	12	11	2	10	3	4	13
10	0	10	15	5	3	9	12	6	1	11	14	4	2	8	13	7
11	0	11	13	6	7	12	10	1	9	2	4	15	14	5	3	8
12	0	12	4	8	13	1	9	5	6	10	2	14	11	7	15	3
13	0	13	6	11	9	4	15	2	14	3	8	5	7	10	1	12
14	0	14	7	9	5	11	2	12	10	4	13	3	15	1	8	6
15	0	15	5	10	1	14	4	11	2	13	7	8	3	12	6	9

Bibliografia

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