Adventný Logboj - Adventný Logboj je individuálna súťaž v riešení logických úloh, v ktorej môžu súťažiť základoškoláci, stredoškoláci aj starší. Na stránke súťaže bude každý decembrový deň až do vianoc sprístupnená jedna úloha, … Prejsť na článok
×7. príklad - Vzorové riešenie
Zadanie
Macker má vo vrecku 2021 mincí hodnôt 1 až 2021 (jednu mincu každej hodnoty). Ak hodí do studne mince aspoň v hodnote 2022, tak sa mu splní jedno želanie a studňa mu vráti mincu, ktorej hodnota je priemerná hodnota mincí, ktoré do nej vhodil (takáto minca nemusí mať celočíselnú hodnotu). Koľko najviac želaní si vie splniť?
Vzorové riešenie
Ako prvé si uvedomme, že aritmetický priemer n čísel je menší alebo rovný číslu najväčšiemu z nich. Vezmime si preto n čísel, označme ich a_1, a_2, \ldots,a_n a dajme im poradie: a_1 \leq a_2 \leq \ldots \leq a_n . Podľa toho platí, že a_i \leq a_n a preto: \dfrac{a_1 + a_2 + \ldots + a_n}{n} \leq \dfrac{a_n + a_n + \ldots + a_n}{n} = \dfrac{n \cdot a_n}{n} = a_n
Najvyššia hodnota mince na začiatku je 2021. Nové mince vznikajú ako aritmetický priemer hodnôt mincí, ktoré do studne hodíme. Ako sme práve ukázali, aritmetický priemer skupiny čísel (hodnôt mincí) je nanajvýš najväčšie číslo z nich, takže nám nikdy nevznikne minca s hodnotou viac ako 2021. Keďže do studne musíme hodiť mince s hodnotou aspoň 2022 a najväčšia minca má hodnotu najviac 2021, tak do studne musíme vždy hodiť aspoň 2 mince.
Keď hodíme do studne dve mince, dostaneme jednu naspäť, preto sa náš počet mincí zníži o jeden. Všimnime si, že aj ak dáme do studne mincí viac (aj s hodnotou oveľa väčšou ako 2022), tak stále dostaneme iba jednu mincu naspäť. Keďže začíname s 2021 mincami, tak vieme splniť najviac 2020 želaní, než nám zostane iba jedna minca. Vieme, že táto minca má hodnotu určite menšiu ako 2022, preto už nemôžeme splniť ďalšie želania.
Teraz si ukážeme, ako vieme splniť 2020 želaní a tým vyriešime úlohu, lebo sme práve dokázali, že viac sa nedá.
Najskôr mince do studne budeme hádzať nasledovne: 1 a 2021, 2 a 2020, 3 a 2019,\ldots Mince vždy dávajú súčet 2022, lebo hodnotu menšej mince zvýšime o 1 a hodnotu väčšej mince zvýšime o 1. Studňa nám zakaždým vráti mincu s hodnotou \frac{2022}{2} = 1011. Počet mincí je nepárny a teda nám zostane 1 minca bez dvojice. Táto minca sa nachádza presne v strede medzi 1 a 2021, teda jej hodnota je \frac{1 + 2021}{2} = 1011.
Týmto spôsobom sme spárovali všetky okrem 1 mince a teda sme spravili \frac{2021-1}{2} = 1010 dvojíc. Každou dvojicou sme si splnili jedno želanie a studňa nám vrátila mincu s hodnotou 1011. Ostáva nám 1011 mincí s hodnotou 1011. Teraz budeme hádzať do studne vždy 2 mince s hodnotou 1011. Pri každom hode si splníme 1 želanie a studňa nám vráti jednu mincu s hodnotou \frac{2 \cdot 1011}{2} = 1011. Vždy vymeníme 2 mince s hodnotou 1011 za 1 želanie a 1 mincu s hodnotou 1011. Takto vymeníme 1011 mincí za 1010 želaní, lebo na konci nám musí ostať 1 minca.
Odpoveď: Spolu sme si splnili 1010 želaní v prvom kroku plus 1010 želaní v druhom kroku, teda 2020 želaní celkovo.