Nimliczby
Definicja intuicyjna |
Nimliczby – liczby, które różnią się od zwykłych liczb naturalnych i porządkowych sposobem wykonywania działań. |
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:
(dla liczb naturalnych n ⊕ m oznacza n xor m)
zaś mnożenia:
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 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
- 44 = 5
- 1616 = 17
- 256256 = 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 ⊕ 2n = a + 2n jeżeli a < 2n
- a ⊙ 0 = 0
- a ⊙ 1 = a
- a ⊙ 22n = a · 22n jeżeli a < 22n
- 22n ⊙ 22n = 3 · 22n-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 ).
+ | 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 |
× | 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.