Rząd monet: rozwiązanie zagadki

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.

Zapisz się
Powiadom o
guest
4 komentarzy
Inline Feedbacks
Zobacz wszystkie komentarze
4
0
Zapraszam do skomentowania wpisu.x
()
x