3784497994

4 Urszula Pastwa i Joachim Jelisiejew

Najpierw rozważmy małe liczby zapałek. Z założenia, zero zapałek to pozycja przegrywająca. Jeżeli gracz zaczyna z jedną zapałką, to może ją zabrać, zostawiając przeciwnika z przegraną. Podobnie dla 2, 3, 4, 5, 6 zapałek. Jeżeli jednak gracz zaczyna mając 7 zapałek, to nie może zabrać wszystkich i niezależnie od tego ile zabierze, jego przeciwnik może wygrać, zabierając resztę. Wobec tego 7 zapałek jest pozycją przegrywającą. Mając osiem zapałek, gracz zabiera jedną i jego przeciwnik zostaje w pozycji przegrywającej. Tak więc 8 = 7+1 zapałek jest wygrywającą pozycją. Podobnie 9 = 7+2,...,13 = 7 + 6 zapałek. Jeżeli gracz zaczyna z 14 zapałkami, musi zostawić swojemu przeciwnikowi 8 lub 9 lub 10 ... lub 13 zapałek, czyli pozycję wygrywającą. Wobec tego 14 zapałek to pozycja przegrywająca.

Ogólnie możemy sformułować hipotezę, że

n zapałek jest pozycją przegrywającą wtedy i tylko wtedy, gdy 7 dzieli n.

Uzasadnienie tej obserwacji jest proste: z pozycji z n zapałkami, gdzie 71 n, gracz zawsze przechodzi do pozycji z n' zapałkami dla 7\n', natomiast z pozycji z n zapałkami, gdy 7fn, gracz może przejść do pozycji z n! zapałkami, gdzie 71 n!.

Skoro 7-f 100, to 100 jest pozycją wygrywającą. Aby wygrać, zaczynający Bolek zabiera dwie zapałki, zostawiając Lolkowi 98 = 7 • 14 zapałek. Potem Bolek dba o to, by zawsze po jego ruchu Lolek znalazł się w pozycji przegrywającej, czyli by została liczba zapałek podziełna przez 7.

Zadanie 2. Mamy okrągły stolik. Gracze na zmianę kładą na nim monety jed-nozłotowe (ale tak, aby się nie nakładały oraz nie wychodziły poza krawędź stolika).

Rozwiązanie

Na stole zmieści się tylko skończenie wiele monet, więc gra zakończy się. Wygrywa Bolek. W pierwszym ruchu kładzie on monetę dokładnie na środku stołu. Potem, po każdym ruchu Lolka kładzie monetę symetrycznie względem środka stołu do monety położonej przez Lolka. Dzięki temu układ zachowuje symetrię i jeżeli Lolek zdołał położyć monetę, to i Bolek położy swoją symetrycznie.

Pytanie dodatkowe: który z graczy wygrałby, gdyby okrągły stolik miał dokładnie na środku okrągłą dziurę?

Zadanie 3. Na stole leży 9 żetonów z numerami od 1 do 9. Ruch polega na usunięciu ze stołu żetonu z wybraną liczbą oraz wszystkich żetonów z dzielnikami tej liczby.

Rozwiązanie

Skoro w każdym ruchu usuwamy co najmniej jeden żeton, to gra zakończy się (po co najwyżej 9 ruchach).