Táborová hra
Na táboře děti hrály hru s klasickou šestistěnnou hrací kostkou. Kostkou házel vždy kapitán. Pokud padlo liché číslo, musel celý tým jít tolik kilometrů na sever, kolik padlo na kostce. Pokud hodil sudé číslo, musel celý tým jít na jih, a to polovinu kilometrů, než padlo na kostce. Kolik nejvíce kilometrů mohl nachodit tým, který se po pěti hodech a následných pochodech dostal opět na místo, odkud vyšel?
Odpovědi
Diskuze
prozkoumejme nejprve problém, s nímž se potýkáme. Lichá čísla objevující se na šestistěnné kostce jsou 1, 3, 5, tedy po obdržení lichého čísla se děti vydaly o 1, 3 nebo 5 kilometrů na sever. Sudá čísla na kostce jsou 2, 4, 6, tedy po obdržení sudého čísla se děti vydaly o 1, 2 nebo 3 kilometry na jih.
Pokud bychom odhlédli od podmínky návratu na původní pozici, v rámci 5 hodů je možné urazit nejvíce 5*5 = 25 kilometrů a nejméně 1 * 5 = 5 kilometrů. Tyto hodnoty tedy představují horní a dolní omezení našeho řešení.
Abychom maximalizovali uraženou vzdálenost, zkusme postupovat následovně. Uvědomme si, že nezáleží na tom, v jakém pořadí byla jednotlivá čísla hozena. Můžeme tedy zkusit předpokládat, že byla nejprve hozena hodnota 5, tedy děty musely urazit 5 kilometrů směrem na sever (což je nejvyšší možná délka trasy daná jedním hodem). Lze snadno nahlédnout, že další hodnota 5 hozena být určitě nemohla, neboť bychom se nacházeli 10 kilometrů na sever od výchozího bodu a nebyli bychom schopni se v rámci 3 zbývajících hodů vrátit do původní pozice. Uvažujme tedy o tom, že byla hozena hodnota 3, tj. nacházíme se 8 kilometrů na sever od původní pozice. Nyní jsme schopni se v rámci 3 hodů (hodnoty 6, 6, 4) vrátit do původní pozice, tj. v rámci 5 hodů jsme urazili 16 km.
Zdá se, že toto řešení je optimální, neboť jsme vždy volili maximální možnou délku trasy. Tj. řešením je 16 km, což je dáno hozením čísel 5, 3, 6, 6, 4.
Otázka je, jak tuto skutečnost ověřit. Můžeme si pro začátek uvědomit, že výsledek musí být vždy nutně sudý, neboť pracujeme pouze s celými čísly a polovina nachozených kilometrů musela být realizována cestou na sever a polovina cestou na jih, abychom se dostali do výchozího bodu. Reprezentujme kladným číslem pochod na sever a záporným pochod na jih o dané délce.
Aby součet výsledků pěti výběrů z množiny {1, 3, 5, -1, -2, -3} byl sudý (zde nulový), musí být nutně vybrán sudý počet lichých čísel. Jelikož zde máme pouze jedno sudé číslo, musí se tedy ve výsledku vždy objevit. Není možné jej vybrat pětkrát, neboť bychom se nacházeli 10 kilometrů na jih od výchozího bodu. Pokud bychom jej vybrali třikrát, nacházeli bychom se šest kilometrů na jih od výchozího bodu. Ve dvou hodech bychom sice byli schopni vrátit se do výchozího bodu, nicméně urazili bychom pouze 12 kilometrů. Pokud tedy existuje lepší řešení pro situaci, kdy byla hodnota 4 hozena právě jednou, musí být 4 nutně hozena právě jednou. Takové řešení jsme našli, tedy víme, že 4 byla hozena právě jednou.
Nacházíme se tedy s jistotou dva kilometry na jih od výchozího bodu a máme 4 hody, abychom se dostali do výchozího bodu a maximalizovali délku cesty, přičemž číslo 4 už nesmí padnout. Ukázali jsme si, že pokud vybereme čísla 5, 3, -3, -3, získáme platné řešení a současně pokud vybereme víc než jednu pětku, platné řešení určitě nezískáme. Proto je náš výběr optimální a řešením je 16.