Nimliczby

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Definicja intuicyjna


Nimliczbyliczby, 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:

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}ciałami skończonymi.

Ujęcie intuicyjne[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]