Zadanie
Mr. Miro bol pozvaný na párty dlhorukých basketbalistov. Všetkých $2017$ účastníkov párty si posadalo za okrúhly stôl, každý s pohárikom v ruke. Každú sekundu si štrngnú pohárikmi, pričom dodržiavajú nasledovné dve pravidlá:
- Necinkajú si poháriky do kríža.
- V danej sekunde si každý môže cinknúť nanajvýš raz.
Na začiatok si môžeme skúsiť úlohu vyriešiť pre menší počet basketbalistov, kde si vieme rozpísať alebo nakresliť všetky štrngnutia. Ľahko tak nadobudneme tušenie, že \(n\) basketbalistov si vie poštrngať za \(n\) sekúnd (okrem zopár výnimok, keď \(n < 3\)). Poďme teda dokázať toto naše tušenie pre \(2017\) basketbalistov.
Skúsme najprv zistiť, prečo si basketbalisti nevedia štrgnúť za menej ako \(2017\) sekúnd. Vieme, že samotný Mr. Miro potrebuje aspoň \(2016\) sekúnd na to, aby si štrngol so všetkými spoluhráčmi. Prečo ale \(2016\) sekúnd nestačí? Keďže hráčov je nepárny počet, v prvej sekunde (a rovnako aj v každej ďalšej) si aspoň jeden basketbalista s nikým neštrngne. Tento chudáčik bude teda potrebovať ešte aspoň \(2016\) ďalších sekúnd, aby si štrngol s ostatnými. Preto potrebujeme aspoň \(2017\) sekúnd, aby si všetci poštrngali.
Ešte potrebujeme ukázať, že za \(2017\) sekúnd si basketbalisti môžu poštrngať. Popíšeme teda postup štrngania, ktorým to dosiahnu. Aby si nekrižovali ruky a aby si ich čo najviac štrnglo, tak by si mohli štrngať „rovnobežne“, ako na obrázku. V ďalších sekundách budeme potom tento vzor štrngaia „otáčať“. Potrebujeme však tento postup opísať poriadne. To môžeme spraviť s využitím basketbalistu, ktorý si neštrngá. V jednej sekunde budeme mať jedného basketbalistu \(X\), ktorý si neštrngá. V tejto sekunde si štrngnú tí basketbalisti, ktorí sú od basketbalistu \(X\) vzdialení o rovnaký počet miest. Vzdialenosťou basketbalistov \(A\) a \(B\) tu myslíme počet basketbalistov, ktorí sa medzi nimi nachádzajú (z tej kratšej strany). „Otáčanie“ realizujeme tým, že v každej sekunde si zvolíme iného basketbalistu, ktorý si nebude štrngať.
Štrngne si týmto spôsobom každý s každným? To musíme dokázať. Zoberme si teda ľubovoľných basketbalistov \(A\) a \(B\) a nájdime sekundu, v ktorej si štrgnú. Basketbalistov \(A\) a \(B\) oddeľuje z jednej strany stola párny a z druhej strany nepárny počet basketbalistov. Je tomu tak preto, lebo zvyšných basketbalistov je \(2015\), čo je nepárne číslo. V časti stola s nepárnym počtom basketbalistov sa nachádza jeden basketbalista \(C\), ktorý je rovnako vzdialený od basketbalistu \(A\), aj \(B\). Basketbalisti \(A\) a \(B\) si preto štrngnú v tej sekunde, keď si basketbalista \(C\) nebude štrngať.
Týmto sme ukázali, že za \(2017\) sekúnd si basketbalisti vedia poštrngať každý s každým podľa zadania. To je zároveň aj najkratší čas, za ktorý to je možné.
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ť.
Tatiana Vargicová
Ten pocit, keď sa vám dobre neofotí obrázok a stratíte na tom polku bodov...