Odejmij kwadrat

Odejmowanie do kwadratu (nazywane również odejmowaniem do kwadratu ) to gra matematyczna dla dwóch graczy polegająca na odejmowaniu . Grają w nią dwie osoby ze stosem monet (lub innych żetonów) między sobą. Gracze na zmianę usuwają monety ze stosu, zawsze usuwając niezerową kwadratową liczbę monet. Gra jest zwykle rozgrywana jako normalna gra, co oznacza, że wygrywa gracz, który usunie ostatnią monetę. Jest to gra bezstronna , co oznacza, że zestaw ruchów dostępnych z dowolnej pozycji nie zależy od tego, czyja jest tura. Solomon W. Golomb przypisuje wynalezienie tej gry Richardowi A. Epsteinowi .

Przykład

Normalna gra rozpoczynająca się od 13 monet jest wygrana dla pierwszego gracza, pod warunkiem, że zacznie od odjęcia 1:

gracz 1: 13 - 1*1 = 12

Gracz 2 ma teraz trzy możliwości: odjąć 1, 4 lub 9. W każdym z tych przypadków gracz 1 może zapewnić, że w ciągu kilku ruchów liczba 2 zostanie przekazana graczowi 2:

gracz 2: 12 - 1*1 = 11 gracz 2: 12 - 2*2 = 8 gracz 2: 12 - 3*3 = 3 gracz 1: 11 - 3*3 = 2 gracz 1: 8 - 1*1 = 7 gracz 1: 3 - 1*1 = 2 gracz 2: 7 - 1*1 = 6 lub: 7 - 2*2 = 3 gracz 1: 6 - 2*2 = 2 3 - 1*1 = 2

Teraz gracz 2 musi odjąć 1, a następnie gracz 1 robi to samo:

gracz 2: 2 - 1*1 = 1 gracz 1: 1 - 1*1 = 0 gracz 2 przegrywa

Teoria matematyczna

W powyższym przykładzie liczba „13” reprezentuje pozycję wygrywającą lub „gorącą”, podczas gdy liczba „2” reprezentuje pozycję przegraną lub „zimną”. Biorąc pod uwagę listę liczb całkowitych z każdą liczbą całkowitą oznaczoną jako „gorąca” lub „zimna”, strategia gry jest prosta: spróbuj przekazać przeciwnikowi „zimną” liczbę. Jest to zawsze możliwe, pod warunkiem, że prezentowany jest „gorący” numer. Które liczby są „gorące”, a które „zimne”, można określić rekurencyjnie :

liczba 0 to „zimno”, a 1 „gorąco”
jeśli wszystkie liczby 1 .. N zostały sklasyfikowane jako „gorące” lub „zimne”, to wtedy
- liczba N + 1 jest „zimna”, jeśli tylko liczby „gorące” można uzyskać przez odjęcie dodatniego kwadratu
- liczba N+1 jest „gorąca”, jeśli co najmniej jedna „zimna” liczba może zostać osiągnięta przez odjęcie dodatniego kwadratu

Korzystając z tego algorytmu, można łatwo wyprowadzić listę zimnych liczb:

0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, … (sekwencja A030193 w OEIS )

Szybszy algorytm dziel i zwyciężaj może obliczyć tę samą sekwencję $n$ , aż do dowolnego progu , w czasie $O (n \ log ^ {2} n)}$ .

Zimnych liczb jest nieskończenie wiele. Co więcej, liczba zimnych liczb do pewnego progu musi być co najmniej proporcjonalna do pierwiastka kwadratowego z $n}$ $w$ przeciwnym razie nie byłoby ich wystarczająco dużo, aby zapewnić zwycięskie ruchy ze wszystkich n {\ gorące numery. Zimne liczby zwykle kończą się na 0, 2, 4, 5, 7 lub 9. Zimne wartości, które kończą się innymi cyframi, są dość rzadkie. Dotyczy to w szczególności zimnych liczb kończących się na 6. Ze wszystkich ponad 180 000 zimnych liczb mniejszych niż 40 milionów tylko jeden kończy się na 6: 11 356.

Żadne dwie zimne liczby nie mogą różnić się o kwadrat, ponieważ gdyby tak było, ruch od większej z nich do mniejszej byłby wygraną, co jest sprzeczne z założeniem, że obie są zimne. Dlatego zgodnie z twierdzeniem Furstenberga-Sárközy'ego gęstość naturalna zimnych liczb wynosi zero. Oznacza to, że dla każdego $epsilon$ $> 0}$ \ displaystyle n} jest mniejszy niż ϵ > $\$ ${\ displaystyle \ epsilon}$ . Silniej, na każdy istnieją ${\ displaystyle n}$

{\ Displaystyle O (n / (\ log n) ^ {{\ Frac {1} {4}} \ log \ log \ log \log n})}

zimne liczby do ${\ displaystyle n}$ . Dokładne tempo wzrostu zimnych liczb pozostaje nieznane, ale eksperymentalnie liczba zimnych pozycji do dowolnego określonego progu $displaystyle$ się być w przybliżeniu $n ^ {0,7}}$ .

Rozszerzenia

W grę „odejmowanie kwadratu” można również grać z wieloma liczbami. W każdej turze gracz, który ma wykonać ruch, najpierw wybiera jedną z liczb, a następnie odejmuje od niej kwadrat. Taką „sumę normalnych gier” można przeanalizować za pomocą twierdzenia Sprague-Grundy'ego . Twierdzenie to stwierdza, że każda pozycja w grze odejmij kwadrat może być odwzorowana na równoważny rozmiar sterty nim . Optymalna gra polega na przejściu do zbioru liczb takiego, że suma nim ich równoważnych rozmiarów sterty nim wynosi zero, jeśli jest to możliwe. Równoważny rozmiar sterty nim dla pozycji można obliczyć jako minimalna wykluczona wartość równoważnych rozmiarów pozycji, które można osiągnąć jednym ruchem. Dla pozycji odejmowania do kwadratu wartości 0, 1, 2, ... równoważne rozmiary sterty nim to

0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 3, 4, … (sekwencja A014586 w OEIS ).

W szczególności pozycja odejmowania kwadratu jest zimna wtedy i tylko wtedy, gdy jej równoważny rozmiar sterty nim wynosi zero.

Możliwe jest również rozgrywanie wariantów tej gry przy użyciu innych dozwolonych ruchów niż liczby kwadratowe. Na przykład Golomb zdefiniował analogiczną grę opartą na sekwencji Mosera-de Bruijna , sekwencji rosnącej z podobną asymptotyczną szybkością do kwadratów, dla której można łatwiej wyznaczyć zbiór zimnych pozycji i zdefiniować łatwy do obliczenia optymalna strategia ruchu.

Dodatkowe bramki mogą być również dodawane dla graczy bez zmiany warunków wygranej. Na przykład zwycięzca może otrzymać „wynik” na podstawie liczby ruchów potrzebnych do wygrania (celem jest uzyskanie najniższego możliwego wyniku), a przegranemu dać cel, aby zmusić zwycięzcę do jak najdłuższego dotarcia zwycięstwo. Przy tej dodatkowej parze bramek i założeniu optymalnej gry obu graczy, wyniki dla pozycji startowych 0, 1, 2, ... są

0, 1, 2, 3, 1, 2, 3, 4, 5, 1, 4, 3, 6, 7, 3, 4, 1, 8, 3, 5, 6, 3, 8, 5, 5, 1, 5, 3, 7, … (sekwencja A338027 w OEIS ).

Misère gra

Odejmowanie do kwadratu może być również rozgrywane jako gra misère , w której gracz, który dokona ostatniego odjęcia, przegrywa. Algorytm rekurencyjny do określania „gorących” i „zimnych” liczb w grze misère jest taki sam, jak w normalnej grze, z wyjątkiem tego, że w grze misère liczba 1 jest „zimna”, podczas gdy 2 jest „gorąca”. Wynika z tego, że zimne liczby dla wariantu misère to zimne liczby dla normalnej gry przesunięte o 1:

Misère gra „zimne” liczby: 1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 40, 45, ...

Zobacz też