Zagadka jest prościutka: pierwszy gracz musi sobie ponumerować monety od 1 do 100 (zaczynając od dowolnego końca), następnie policzyć łączną wartość monet na pozycjach nieparzystych i osobno na parzystych, i zawsze zabierać monetę z grupy o większej wartości.
Zauważmy bowiem, że drugi gracz zawsze będzie miał do swojej dyspozycji monety na pozycjach o tej samej parzystości.
Weźmy nieduży przykład: dajmy na to, że monet jest nie 100 a 10, i leżą w następującej kolejności:
1,2,5,2,2,1,5,2,1,1,5,2,5,1
Numerujemy je od lewej do prawej.
Suma nieparzystych wynosi 25: 1,2,5,2,2,1,5,2,1,1,5,2,5,1.
Suma parzystych - 12.
Stąd też pierwszy gracz zaczyna od wzięcia jedynki w lewego końca, a potem za każdym razem bierze monetę z tego samego końca, co jego przeciwnik, dzięki czemu przeciwnikowi zawsze zostaną monety na parzystych pozycjach.
A jak Wam poszło?
1Pierwszy odezwał się Cichy Fragles, który opisał powyższą metodę w dużo krótszy i bardziej elegancki sposób. Zasugerował też, że gdyby monety były bardzo wartościowe, być może warto rozrysować pełne drzewko wszystkich możliwych kombinacji i wybrać z niego optymalną ścieżkę.
2Drugi był Waldek, który swoje rozwiązanie nadesłał w przeddzień rwania ósemki, w związku z czym był na silnych pigułach przeciwbólowych. Nie wiem, czy go nie zdyskwalifikować za doping 😉 Ale rozwiązanie podał poprawne, chociaż oparte na liczeniu zębów.
3Trzeci wysłał rozwiązanie Butter:
Wybieram monetę o większym nominale. Jeśli obie są równe, wybieram taką, żeby przeciwnik po moim ruchu miał do wyboru mniejsze nominały.
Rozwiązanie Buttera jest błędne, ponieważ często będzie tak, że za monetą o odrobinę wyższym nominale będzie siedzieć jeszcze większy nominał, a za monetą o odrobinę niższym - blotka. Przykład: 1,1,4,5,9,2,4,3,7,2. Postępując według algorytmu Buttera biorę dwójkę, przeciwnik bierze siódemkę. Potem ja trójkę, przeciwnik czwórkę, ja dwójkę, przeciwnik dziewiątkę... i już przegrałem.
zastanawiałem się na nad wariantem że coś wartościowszego leże na dalszych miejscach, ale na stwierdzeniu, że coś by trzeba było z tym zrobić się skończyło 😉
Niestety nie odpowiedziałem. Szybko zauważyłem, że końce są dwa, zwróciłem też uwagę, że trzeba brać pod uwagę sumę i pchało mnie w stronę rekurencyjnego dowodu, ale stwierdziłem, że potrzeba na to więcej czasu. To, że pierwszy wybór determinuje w praktyce czy wybierane są monety parzyste czy nie, niestety umknęło mej uwadze.
Podczas wyrywania zęba zastanawiałem się nad nieco zmodyfikowaną wersją tej zagadki: na początku gry mamy tylko 99 monet, czyli rozpoczynający weźmie 45, a ten drugi 44 monety.
Czy drugi gracz ma jakąś szansę na wygraną?
Znając rozwiązanie zagadki ze stoma monetami wiadomo, że może nie tylko zremisować, ale też wygrać. Z jakim prawdopodobieństwem? Mniej, czy więcej niż 50%?
Tylko 18%!
Wszystko zależy od tego, czy rozpoczynający grę trafi na którymś z dwóch końców monetę o wartości większej niż różnica parzyste-nieparzyste z pozostałych 98 monet.