Nimliczby

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Definicja intuicyjna:
Nimliczbyliczby, które różnią się od zwykłych liczb naturalnych i porządkowych sposobem wykonywania działań.

Nimliczbyklasa właściwa wprowadzona do określenia wielkości stosów w grze nim, ale zastosowana do szerszej klasy gier dzięki twierdzeniu Sprague–Grundy'ego.

Dodawanie nimliczb definiuje się następująco

\alpha + \beta = \mbox{mex}(\{\,\alpha' + \beta : \alpha' < \alpha\,\} \cup \{\, \alpha + \beta' : \beta' < \beta \,\})

zaś mnożenie:

\alpha \beta = \mbox{mex}(\{\,\alpha' \beta + \alpha \beta' - \alpha' \beta' : \alpha' < \alpha, \beta' < \beta \,\}) = \mbox{mex}(\{\,\alpha' \beta + \alpha \beta' + \alpha' \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, 16, 32...) to dodaje się je według takich zasad, jak zwykłe liczby.

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]