Student World

pravidelné páteční „přetištění“ staršího článku

Následující úloha je dobře známá v jednotlivých konkrétních případech, pokusíme se ji ale formulovat obecněji…

Máme hromadu sirek (x), z níž lze v každém tahu odebrat pouze určitý počet sirek (1 až y), a to tak, že y = f (x). Obra hráči se střídají. Na koho zbude poslední sirka, prohrává. Jaká je optimální strategie?

První verze, asi nejjednodušší, se obvykle zadává jako úloha, kdy se v každém tahu přičítají k aktuálnímu součtu čísla volitelná od 1 do 10 a kdo součet doplní na 100, vyhrává. Začíná se od nuly. Algoritmus je dobře známý. Kdo je na tahu při čísle 89, prohrává. Kdo je na tahu při čísle 78, prohrává. A tak dále. Vítězná řada je tedy 1, 12, 23… Kdo začíná, vítězí.
Jednoduchou modifikací je změnit horní hranici z 10 na jiné číslo. Jaká je v tomto případě optimální strategie?

Tyto případy až dosud vlastně popisovaly výchozí sirkovou úlohu, kdy y = 0x + k. Co ale pokud je (viz zadání) maximální hodnota odebraných sirek funkcí aktuálního stavu? Řekněme, že v každém tahu je maximální hodnota povoleného odběru rovna 1/2 aktuálního stavu (zaokrouhleno na celá čísla dolů). Nebo jedné třetině.
Jaká je vítězná strategie pro obě tyto varianty a jak by šla zapsat obecně?

Malá nápověda: Optimální strategii lze poměrně odvodit indukcí, kdy si budeme pod sebe psát jednotlivá čísla a k tomu výsledek (pro toho, kdo je na tahu).
V případě maximálního odběru 1/2 např. nějak takto:

1… prohrávám
2… vyhrávám
3… prohrávám
4… vyhrávám
5… vyhrávám (odeberu 2 sirky)
6… vyhrávám (odeberu 3 sirky)
7… prohrávám (jakýkoliv odběr povede k 4, 5, 6, kdy vyhrává soupeř).
atd.

Závěrečná úloha: Obě předešlé verze lze kombinovat, respektive maximální povolený odběr definovat jako y = f (x). Uvažujme pouze lineární vztah, tedy y (maximální odběr) = a * x + k. Smysl má úloha samozřejmě pouze tehdy, pokud „a“ je menší než 1 a „k“ je menší než „x“. Jaká je v tomto případě obecně optimální strategie?

autor Pavel Houser