Zagadka kaczmarologiczno-numizmatyczna

[dauri]

Pewien ojciec napisał do syna Stacha:

Stach! Pieniądze Ci posyłam, jakeś chciał!
Na dziewuchy nie wydawaj, przyjdą same

ale Stach, niestety, nie posłuchał…

Pewna dziewucha zaproponowała Stachowi (w zamian za pewne usługi) następującą grę. Ułożyli w szeregu 50 monet należących do Stacha (o różnych nominałach) i każde wybierało na przemian monetę zajmującą jedną z dwóch skrajnych pozycji, zaczynając od dziewuchy.

Należy udowodnić, że w każdej sytuacji dziewucha jest w stanie obrać taką strategię, która umożliwi jej uzyskanie łącznej kwoty nie mniejszej od kwoty zebranej przez Stacha.

[MacB]

A nie da się tego zrobić normalnie, tak po ludzku: z Turkami i chrześcijanami?

[dauri]

Nie da się. Turcy by po prostu zabrali wszystkie monety siłą i powbijali chrześcijan na pal. ;(

[TomciO]

Ponumerujmy (od lewej) kolejne monety liczbami od 1 do 50. Wyszczególnijmy dwie grupy monet:

-monety o numerach nieparzystych: 1, 3, 5, ..., 49 (czyli zaczynamy od pierwszej, a potem co druga)
-monety o numerach parzystych: 2, 4, 6, ..., 50 (czyli zaczynamy od drugiej i co druga)

Wyszczególnione grupy dają w sumie wszystkie monety. Z tych dwóch grup wybierzmy tą, w której łączna wartość wszystkich monet jest nie mniejsza niż łączna wartość wszystkich monet w pozostałej grupie. Łatwo zauważyć, że sytuacja jest zupełnie symetryczna, a więc bez straty ogólności możemy skupić się na przypadku, w którym pierwsza grupa posiada większą łączną wartość wszystkich monet.
I teraz kluczowa obserwacja: dziewucha może grać tak żeby zgarnąć monety z pierwszej grupy. W pierwszym ruchu bierze monetę 1. Jeśli Stach weźmie monetę 2 (teraz skrajną) to ona bierze 3. Jak Stach weźmie monetę 50 to ona bierze 49. Ogólnie, jeśli Stach robi ruch po lewej stronie to dziewucha też robi po lewej, a jak po prawej to też po prawej. Wówczas, po każdym ruchu dziewuchy monety skrajne mają numery parzyste, a więc po ruchu Stacha jedna moneta zawsze będzie mieć numer nieparzysty i tą właśnie monetę wybiera dziewucha. A więc kończy ona z monetami: 1, 3, 5, ..., 49, a Stach z pozostałymi, czyli dziewucha wygrywa.

[dauri]

I to jest bardzo dobre rozwiązanie!