Zadanie
V kruhu je \(100\) zelených mimozemšťanov, každý z nich má \(100\) tabletov. V rámci jedného ťahu ľubovoľný mimozemšťan zoberie niekoľko svojich tabletov a rozdelí ich medzi ostatných mimozemšťanov (nie nutne rovnomerne a nie nutne medzi všetkých). Po akom najmenšom počte ťahov vedia mimozemšťania docieliť, aby žiadni dvaja z nich nemali rovnaký počet tabletov?
Na začiatok si potrebujeme uvedomiť toto: Ak na konci máme n mimozemšťanov, ktorí majú menej ako 100 tabletov, museli ich darovať. Keďže tablety sa dajú "stratiť" iba počas ťahu daného mimozemšťana vieme, že počet ťahov musel byť aspoň \(n\).
Pozrime sa, koľko najviac tabletov môže týchto \(n\) mimozemšťanov stratiť a koľko minimálne musí zvyšných \(100-n\) mimozemšťanov prijať.
Vezmime od našich \(n\) mimozemšťanov čo najviac tabletov. Najlepšie by pre nás bolo od každého zobrať \(100\) tabletov, ale keďže na konci chceme mať jedinečné počty, zoberieme od nich postupne \(100, 99, 98, \cdots, 100-(n-1)\) tabletov. Všimnime si, že súčet tabletov, ktoré dal prvý a posledný mimozemšťan z našich \(n\) mimozemšťanov je rovnaký ako súčet tabletov, ktoré dali druhý a predposledný mimozemšťania z našich \(n\) mimozemšťanov, atď. Ľahko si teraz spočítame, že celkový počet darovaných tabletov je: \[\frac{(100+100-(n-1))\cdot n}{2} = \frac {(201-n)\cdot n}{2}.\] Použili sme vlastne súčet členov aritmerickej postupnosti.
Skúsme sa teraz zamyslieť nad tým, koľko tabletov musí zvyšných \(100-n\) mimozemšťanov dostať, aby mali každý tiež jedinečný počet. Budeme mať teda zvyšných mimozemšťanov, ktorým sme darovali postupne \(0, 1,2, \cdots, 100-n-1\). Celkový počet tabletov, ktorý musia dostať si vieme spočítať analogicky ako v predchádzajúcej časti a vyjadriť nasledovne: \[\frac{(0+99-n) \cdot (100-n)}{2} = \frac{(99-n) \cdot (100-n)}{2}.\]
Uvedomme si, že musí platiť, že počet tabletov, ktoré môže \(100-n\) mimozemšťanov dostať, musí byť určite menší alebo rovný počtu tých, ktoré môže \(n\) mimozemšťanov darovať. Riešme preto nasledujúcu nerovnicu: \[\frac{(201-n) \cdot n}{2} \geq \frac {(99-n) \cdot (100-n)}{2}.\] To si vieme prepísať ako: \[n^2-200n+4950 \leq 0.\] Či už budeme skúšať dosadzovať hodnoty alebo použijeme vzorec na výpočet koreňov kvadratickej rovnice zistíme, že \(n=28\) je ešte málo, ale \(n=29\) nám už stačí. Ukážme si, že to naozaj ide – 28 mimozemšťanov daruje postupne 100, 99, .. 73 tabletov, všetci ich darujú 29. mimozemšťanovi. Po 28 ťahoch má on veľa tabletov, ktoré rozdelí medzi ostatných tak, že im daruje postupne 0, 1, ... 70 tabletov a všetci budú mať rôzny počet.
Zistili sme, že najmenší počet ťahov je \(29\).
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ť.