Zadanie 21

Na stole leży n zapałek. Dwóch zawodników na przemian bierze pewną liczbę zapałek. Pierwszy z nich bierze nie mniej niż 1 i nie więcej niż n - 1 zapałek. W każdym kolejnym kroku biorący nie może użyć więcej zapałek niż wziął jego przeciwnik w poprzednim kroku. Wygrywa ten, kto bierze ostatnią zapałkę. Dla jakich n jeden z zawodników może zapewnić sobie wygraną?

Rozwiązanie

Gdy jest nieparzysta liczba zapałek to rozpoczynający grę bierze jedną zapałkę, drugi gracz tez jedną i tak dalej, aż drugi gracz przegra, a pierwszy weźmie ostatnią zapałkę.

Gdy na stole leży parzysta znalazlem zaleznosc, ze jeżeli liczba zapalek wynosi to rozpoczynający grę przegrywa, drugi gracz powinien tylko zrobic tak, aby przeciwnik natknal się na liczbę niepodzielną przez 4. Natomiast gdy liczba zapałek jest parzysta, ale nie wynosi ona to rozpoczynający grę wygrywa posługując się pułapką opisaną powyżej.

Opracowałem również "schemat blokowy" wygrywalności:

Odpowiedż

Dla n równych 2k-1, gdzie k jest liczbą naturalną pierwszy gracz wygrywa. Gdy liczba zapałek wynosi to wygrywa gracz drugi. Natomiast gdy liczba zapałek nie wynosi to wygrywa także gracz pierwszy.

Karol Masłowski