4×4
Czekoladowy chomp z przedpoprzedniego wpisu to gra, w której remis jest niemożliwy. Zawsze ktoś musi wygrać i zawsze tym kimś może być Pn (wykonujący pierwszy ruch i wszystkie nieparzyste), niezależnie od tego, jak będzie grał Dp (drugi ruch i parzyste). Można elegancko wykazać, że Dp stoi na straconej pozycji. Prosty dowód nie wprost opiera się na założeniu, że jest odwrotnie, czyli to Dp ma jakąś metodę (strategię) zapewniającą wygraną. A skoro tak, to po pierwszym ruchu Dp, czyli ogólnie po drugim, zawsze powinien pozostać taki kawałek czekolady, jaki nie może pozostać po żadnym pierwszym ruchu Pn. Gdyby bowiem Pn, wykonując pierwszy ruch, mógł doprowadzić do takiej sytuacji, jak Dp po drugim, to tym samym „podkradłby” zwycięską strategię Dp. I właśnie tak sprytnie „po złodziejsku” może zagrać Pn – ruch polega na zabraniu jednej narożnej kostki. Jakiegokolwiek kawałka nie odgryzie teraz Dp, zawsze o tym, który pozostanie, Pn będzie mógł powiedzieć: „ten kawałek nie może zapewnić ci wygranej, bo taki sam ja mogę pozostawić wcześniej – po pierwszym ruchu”. Stąd wniosek, założenie było błędne, czyli Dp nie ma zwycięskiej strategii, a zatem ma ją Pn. Inna sprawa, że nie wiadomo konkretnie jaka jest ta strategia.
Chomp należy do gier typu nim, które – ogólnie rzecz biorąc – wyglądają tak: ze zbioru elementów podzielonego na podzbiory gracze na zmianę usuwają po ileś elementów zgodnie z jakąś regułą; kto bierze ostatni element, ten wygrywa. Czasem gra jest ciekawsza albo w ogóle ma sens dopiero wówczas, gdy wzięcie ostatniego elementu oznacza przegraną. Tak właśnie jest w chompie i paru innych odmianach nima dwuwymiarowego. Za protoplastę chompa można uznać tac-tix, grę Pieta Heina, staruszkę, która liczy sobie już blisko 70 lat.
16 pionków stoi na planszy 4×4. W jednym ruchu można zabrać od 1 do 4 pionków, ale zawsze tylko z jednego rzędu i zawsze – jeśli 2, 3 lub 4 – z kolejnych, sąsiednich pól. Na rysunku przedstawiona jest sytuacja w trakcie gry – z planszy ubyło już 9 pionków.
Wykonujący teraz ruch może wziąć tylko:
– 2 pionki w kombinacjach [a2-b2], [b2-c2], [c2-d2], [b2-b3], [b3-b4], [c1-c2];
– 3 pionki – [a2-b2-c2], [b2-c2-d2], [b2-b3-b4].
– 1 pionek – skąd chce, a 4 – wiadomo.
Jaki ruch należy wykonać, aby wygrać?
Przypominam: przegrywa kto sprząta ostatni pionek.
Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3 dni.
Komentarze
Wydaje mi się, że wygrywające ruchy są dwa: a2 albo b2.
zabralbym pionek z b2
Proszę o wyjaśnienie tej zasady, bo… jakoś nie rozumiem:
[…]W jednym ruchu można zabrać od 1 do 4 pionków, ale zawsze tylko z jednego rzędu i zawsze – jeśli 2, 3 lub 4 – z kolejnych, sąsiednich pól.[…]
szczególnie tego:
[…]i zawsze – jeśli 2, 3 lub 4 – z kolejnych, sąsiednich pól.[…]
Wiązie, może tak:
– tylko takie 2 pionki możemy usunąć z rzędu, które stoją na dwóch sąsiednich polach;
– tylko takie 3 pionki możemy usunąć z rzędu, które stoją na trzech kolejnych polach (te trzy pola tworzą jeden „kawałek”).
Usuwanie 1 lub 4 pionków jest jednoznaczne.
mp
no to [b2-b3]
Jeśli dobrze przeanalizowałem, to przedstawiona pozycja jest przegrywająca.
Pozdrawiam,
jazz
poprawka: [c2], poprzedni ruch był wg zasady: kto ostatni ten wygrywa, jak zwykle czytam za szybko 🙂
Zabrałbym pionek z c1.
Zabranie 2, 3 lub 4 pionów to pozycja przegrywająca.
a2
C1 przegrywa? A dlaczego?
a2
Ach. Już widzę: po [a2-b2]
Odpowiedz moja [c2] została uwolniona, albo nie rozumiem reguł (co nie wykluczone) albo … czyzby to bylo zle rozwiazanie? Hmmm nie jestem mistrzem, no ale zadanko jest na tyl e proste, ze nie widze bledu, ruch ten jest wygrywajacy (jesli ostniego gryza psy pczywiście )
🙂 Eh…. szkoda gadac :):):) Aż wstyd! :):)
Teraz myślę, że b2.
Wstyd, wstyd i jeszcze raz wstyd, moja ostateczna i definitywna odpowiedz to [a2]!
Na moje usprawiedliwienie powiem tylko, ze na łamibloga wpadam na szybkie 5 minut, no ale po takiej wpadce musiałem wygospodarowac troche wiecej czasu! Dobrze, że mam w komórce blokusa, to w drodze się odpreze teraz i odpoczne 😉 psychicznie! od łamibloga.
Wygrywa b2 – to łatwo znalezc. Trudniej odkryc, ze wygrywa takze a2.
a
Dlaczego przegrywa C1:
JA – C1
on – B2C2
JA – A2
on – B3B4
JA – D2 lub
JA – C1
on – B2C2
JA – 2D
on – B3B4
JA – A2 lub
JA – C1
on – B2C2
JA – B3B4
on – A2 lub D2
JA – D2 lub A2
To chyba nie tak, bo nie wziąłem jeden możliwości pod uwagę.
Moim zdaniem sa dwa wygrywające ruchy: a2 i b2. Po kazdej odpowiedzi przeciwnika, można doprowadzić do jednego z trzech układów wygrywających:
– pojedynczego pionka
– trzech izolowanych pionków
– dwóch par pionków
To chyba nie przypadek, że tak łatwo popełnić tu błąd. To zadanie musi mieć jakąś szczególną cechę – być może związaną z naturą tego typu gier. Trudność może wynika z tego, że nie dość, że tylko jedno z pierwszych posunięć jest słuszne, to jeszcze zwykle tylko jedna – przez co trudna do spostrzeżenia – odpowiedź przeciwnika na nasz błędny ruch prowadzi go do zwycięstwa.
Przy rozwiązywaniu pomaga spostrzeżenie tego, że jeśli mamy grupę rozproszonych pionków i jeden zestaw pionków obok siebie (w rzędze albo kolumnie) to zawsze może wygrać ten, na kogo przypada wtedy ruch.
Do s1m:
Po moim c1 i b2c2 zabrałbym b3 (albo b4).
Według mnie istnieją dwa wygrywające ruchy: A2 lub B2.
No.
[b2].
I w sumie tyle.
nie wiem, czy miało być tylko jedno rozwiązanie, bo wydaje się, że czy wezmę pionek z a2, czy z b2, to przeciwnik już się nie pozbiera.
Zastanawiam się nad łatwą do zastosowania przez człowieka metodą znajdowania wygrywających posunięć (dla trochę bardziej skomplikowanych układów).
Na przykład gdyby pozycja wyglądała jak na obrazku w linku:
http://pokazywarka.pl/bxw6lp/
Wiem że istnieje wygrywający ruch, ale jak go znaleźć?