Liczydłomatematyka · webp.pl

Egzamin ósmoklasisty – grudzień 2017 – zadanie 18

Egzamin ósmoklasisty · 2017 · Grudzień · kombinatoryka · 2 punkty

Ania i Jarek grali w kamienie. Na początku gry kamienie układa się w dwóch stosach. Następnie gracze wykonują ruchy na przemian. Ruch w grze polega na wzięciu dowolnej liczby kamieni tylko z jednego ze stosów. Przegrywa ten, kto nie może już wykonać ruchu.

Na pewnym etapie gry pierwszy stos zmalał do jednego kamienia, a na drugim znajdowały się trzy kamienie. Ruch miała wykonać Ania. Uzasadnij, że aby zagwarantować sobie wygraną, Ania musiała wziąć dwa kamienie z drugiego stosu.

Odpowiedź (klucz CKE)
2 kamienie z drugiego stosu

Rozwiązanie przygotowane z pomocą AI — sprawdź rachunki

Rozwiązanie wygenerowane przez AI — sprawdź rachunki.

Rozważamy sytuację, gdzie pierwszy stos ma 1 kamień, drugi stos ma 3 kamienie, a ruch należy do Ani.

Gra jest wersją gry Nim z dwoma stosami. Wygrywa gracz, który doprowadzi do sytuacji, gdzie oba stosy są puste (przeciwnik nie może wykonać ruchu). Kluczowe są pozycje bezpieczne (przegrywające): są to takie pozycje, że suma binarna liczby kamieni w stosach daje zero (tzw. suma nim).

Obliczamy sumę nim dla pozycji (1,3): zapisujemy liczby w systemie binarnym: 1 = 01₂, 3 = 11₂. Suma nim (XOR): 01 ⊕ 11 = 10₂ = 2 ≠ 0, więc pozycja (1,3) jest niebezpieczna (wygrywająca). Gracz na ruchu (Ania) może przejść do pozycji bezpiecznej (suma nim = 0).

Ania musi wykonać ruch, który zmieni układ na (a,b) taki, że a ⊕ b = 0. Możliwe ruchy: wziąć kamienie z pierwszego stosu (można wziąć jedyny kamień, wtedy stos pierwszy ma 0, drugi 3 → 0 ⊕ 3 = 3 ≠ 0) lub z drugiego stosu. Jeśli weźmie 1 kamień z drugiego stosu: pozycja (1,2): 1 ⊕ 2 = 01 ⊕ 10 = 11₂ = 3 ≠ 0. Jeśli weźmie 2 kamienie z drugiego stosu: pozycja (1,1): 1 ⊕ 1 = 0 → bezpieczna. Jeśli weźmie 3 kamienie z drugiego stosu: pozycja (1,0): 1 ⊕ 0 = 1 ≠ 0.

Jedynym ruchem prowadzącym do pozycji bezpiecznej jest wzięcie 2 kamieni z drugiego stosu, co daje układ (1,1). Wtedy Jarek będzie w pozycji przegrywającej: niezależnie od jego ruchu, Ania będzie mogła zrobić ruch prowadzący do kolejnej pozycji bezpiecznej i ostatecznie wygrać.

Odpowiedź: Ania musi wziąć dwa kamienie z drugiego stosu, aby zagwarantować sobie wygraną.

‹ Poprzednie zadanieNastępne zadanie ›

Cały arkusz: Egzamin ósmoklasisty 2017 · Grudzień · wszystkie arkusze — egzamin ósmoklasisty