Rząd monet: rozwiązanie zagadki

https://xpil.eu/423

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.

https://xpil.eu/423

4 komentarze

  1. 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 😉

  2. 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.

  3. 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%?

    1. 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.

Skomentuj Waldek Anuluj pisanie odpowiedzi

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.