Zadanie
Hazard je jedna z najstarších voľnočasových aktivít, akej sa kedy ľudstvo venovalo. Historické pramene uvádzajú, že už počas ranej doby kamennej prevádzkovali kmeňoví šamani nasledovnú hru:
Šaman položí na stôl tri obrovské mamutie lebky. Každý hráč si musí nezávisle vybrať práve jednu z nich a hodiť do nej jeden mamutí chvost – vtedajšie platidlo, bolo ho dokonca možné deliť na zlomky. Následne šaman skontroluje, či sú všetky počty mamutích chvostov v lebkách rôzne. Ak je v niektorých lebkách rovnako chvostov, mamutie chvosty sa vrátia hráčom a hra sa začne odznova. Ak sú počty v každej lebke iné, zistí v ktorej lebke je najmenej mamutích chvostov. Hráči, ktorí vložili svoje mamutie chvosty do tejto lebky sú výhercovia hry a získajú od šamana dva mamutie chvosty, plus si rozdelia mamutie chvosty z lebky, v ktorej bolo najviac chvostov. Chvosty z najprázdnejšej aj strednej lebky si ponecháva šaman. Pomôžte šamanovi zistiť, pre aké počty hráčov sa mu oplatí hru prevádzkovať1.
Śamanovi sa oplatí hru prevádzkovať ak pri veľkom počte odohratých hier získa v priemere viacej mamutích chvostov, ako stratí.↩
Našou úlohou je zistiť, kedy šaman zarobí na svojej hre. Vieme, že keď je v niektorých dvoch lebkách rovnaký počet, tak sa nič nestane. Z tohto vyplýva, že keby to šaman hral s jedným alebo dvoma ľuďmi, tak by asi umreli od nudy. Lebo keď hrá jeden, tak môže dať chvost len do jednej a v ostatných dvoch je \(0\), a keď sú dvaja, tak buď dajú do tej istej, čo je to isté ako pri jednom hráčovi, alebo každý do inej, kde potom v dvoch bude po jednom chvoste.
Takže teraz vieme, že hra je „hrateľná“, len keď počet hráčov je \(H \geq 3\). Pozrime sa teraz na tieto možnosti. Keďže sú v lebkách rôzne počty chvostov, môžeme si ich zoradiť od najprázdnejšej po najplnšiu a označiť ich zaradom \(A,B,C\). Potom platí nerovnosť \(0 \leq A \leq B \leq C \leq H\). Prípady, keď platí rovnosť nás nezaujímajú, lebo vtedy sa nič nestane. Keď nastane prípad \(0 \leq A < B < C \leq H\), tak šaman zaplatí \(2\cdot A\) chvostov a dostane \(A+B\) chvostov. A teda šaman zarobí, ak platí \(2\cdot A < A+B\), z čoho keď odčítame \(A\) dostaneme, že \(A < B\), čo platí.
Z tohto nám vyplýva, že šamanovi sa hra oplatí hrať vždy, keď má aspoň troch hráčov.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.