Zoznam úloh

4. Klub Mirových Spoluhráčov (κ ≤ 4)

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á:

  1. Necinkajú si poháriky do kríža.

  2. V danej sekunde si každý môže cinknúť nanajvýš raz.

    Za koľko najmenej sekúnd si môže cinknúť každý s každým?

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é.

Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný matematický seminár zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty