gra Luna: Niech n>=3 będzie liczbą naturalną. Dwóch uczniów X i Y gra w następującą grę: na tablicy zapisuje się liczby 1,2,3,...,n i zaczynając od ucznia X wymazuje z planszy jedną liczbe po drugiej, a gra kończy się, gdy zostaną na planszy dwie liczby. Jeśli suma dwóch pozostałych liczb jest podzielna przez 3, wygrywa uczeń Y, w przeciwnym razie wygrywa uczeń X. Określ który z dwóch uczniów ma zwycięską strategię.

wredulus_pospolitus: To jest zadanie podane przez nauczyciela czy przez Ciebie wymyślone? Pytanie o tyle istotne. że odpowiedź (kto wygrywa i jaka jest strategia) jest zależne od tego jaka jest wartość 'n', a konkretniej, jakiej jest postaci: 6k , 6k + 1 , 6k+2 , 6k + 3 , 6k + 4 , 6k + 5 (dla niektórych strategia będzie powielona)

Luna: OK spoko muszę jeszcze nad tym pomyśleć

wredulus_pospolitus: Zauważ, że: dla n = 3 wygrywa zawsze gracz Y (zmazuje '3' i ma wygraną) dla n = 4 wygrywa gracz X ponieważ: 1. jeżeli w pierwszym ruchu zmażesz 1 lub 4 ... to X zmazuje 2 i po ptakach 2. jeżeli w pierwszym ruchu zmażesz 2 ... to po ptakach 3. jeżeli w pierwszym ruchu zmażesz 3 ... to X zmazuje 2 i po ptakach

wredulus_pospolitus: z kolei dla n = 5 wygrywa gracz Y (zmazuje '3' i zostaje parzysta liczba par liczb których suma podzielna jest przez 3 ... i wystarczy odpowiednio reagować na to co robi X)

wredulus_pospolitus: A teraz zauważ, że: Y ma zagwarantowaną wygraną, jeżeli po jego ruchu mamy 2k liczb, z których (wszystkich) możemy utworzyć k takich par, że suma każdej z pary będzie podzielna przez 3. Wtedy wystarczy odpowiednio 'odpowiadać' na poczynania gracza X, aby w efekcie mieć na koniec jedną taką parę liczb. Związku z tym, przed ruchem Y muszą być same pary + jedna liczba bez pary i takie sytuacje to: n = 6k + 1, n = 6k + 3, n = 6k + 5. Dla pozostałych przypadków, należy zauważyć, że ostatni ruch wykonuje X, jakie są możliwe sytuacje: 1. 1,1,1 −−− automatyczna przegrana Y 2. 1,1,2 −−− X skreśla '2' 3. 1,1,0 −−− automatyczna przegrana Y 4. 0,0,0 −−− w tej sytuacji wygrywa Y 5. 0,0,1 −−− X skreśla '0' pozostałe sytuacje, to po prostu zamiana '2' i '1' miejscami, więc je pominę. W efekcie −−− w pozostałych sytuacjach jedyna możliwość to pozostawienie trzech '0' przed ruchem gracza X. Wiedząc to ... gracz X będzie w pierwszej kolejności eliminował '0', wymazując wszystkie, pozostawiając jedną lub dwie. Gracz Y nic na to nie może poradzić, bo tych liczb jest mniej niż sumarycznie pozostałych. jako: 0 −−− myślę o liczba postaci 3m 1 −−− liczby postaci 3m+1 2 −−− liczby postaci 3m+2