Zadanie
Maťkovi sa podarilo v Koši Môjho Šťastia vyhrať \(2021\) eur, a tak sa vybral na dovolenku do Vysokých Tatier. Lenže vodička taxíka zablúdila a zaviezla ho namiesto toho do pohoria Vysoké Taury. Maťko si povzdychol a povedal si, že keď tu už je, tak si aspoň pocestuje lanovkami vo Vysokých Taurách.
Vo Vyskoých Taurách sa nachádza až \(n \geq 3\) staníc, medzi ktorými premávajú lanovky, medzi každou dvojicou staníc vždy najviac jedna (obojsmerná). Maťko je veľký cestovateľ, no nie až tak moc. Preto chce navštíviť len nejakú trojicu navzájom rôznych staníc \(A,\, B,\, C\), v tomto poradí. Zistil, že nech si trojicu \(A,\, B,\, C\) vyberie ľubovoľne, vie sa medzi nimi presunúť lanovkami na najviac \(2\) prestupy. T. j. na ceste z \(A\) do \(B\) a z \(B\) do \(C\) využije dohromady najviac \(3\) lanovky (nie nutne rôzne; ak niektorú využije \(2\)-krát, budeme to považovať za použitie dvoch lanoviek), bez ohľadu na to, ktoré stanice označí ako \(A,\, B,\, C\). V závislosti od \(n\) určte najmenší možný počet lanoviek vo Vysokých Taurách.
Danko[email protected] Mišo M.[email protected]
Pozrime sa najprv na možnosti, ktoré máme. Lanovka môže byť medzi každou dvojicou staníc, teda z každej z \(n\) staníc vychádza lanovka do všetkých \(n-1\) ostatných staníc. Avšak lanovka vychádzajúca z \(A\) do \(B\) je tá istá, ako lanovka z \(B\) do \(A\), čo platí pre všetky lanovky, a preto maximálny počet lanoviek je \(\frac{n(n-1)}{2}\).
Mohli by sme skúsiť na nejakom príklade postupne tieto lanovky pridávať, kým nebude splnená podmienka zo zadania, no bude ich treba celkom veľa. Určite musíme pospájať všetky stanice, keďže Maťko si na svoju cestu môže vybrať ktorúkoľvek z nich, a nie len tak akýmkoľvek spôsobom. Môže sa nám stať, že pridáme skoro všetky, ale nejaká stanica bude voči ostatným „v nepriaznivej pozícii“. Skúsme sa zamyslieť, čo by také niečo mohlo znamenať. Problém nastane, ak na presun medzi nejakými dvomi stanicami potrebujeme najmenej dva prestupy, pretože ak vyberieme tieto dve a ešte tretiu, dokopy použijeme \(3\) prestupy. Podobný problém nastane, ak z nejakej stanice vieme ísť do dvoch iných najmenej jedným prestupom. Ak si Maťko vyberie túto stanicu ako strednú zastávku medzi zvyšnými dvomi, tiež bude potrebovať \(3\) prestupy.
Toto už vyzerá ako celkom obmedzujúca podmienka, lebo v podstate hovorí, že z každej stanice sa nevieme priamo dostať najviac do jednej inej. Zároveň sa v takomto prípade do nej určite vieme dostať na \(1\) prestup, pretože obe tieto stanice sú spojené priamo so všetkými ostatnými stanicami. A to stačí ako záruka podmienky zo zadania, keďže nemôže nastať ani predošlý problém.
Koľko najviac vieme teda lanoviek ušetriť oproti maximu? Spomedzi všetkých staníc môžeme bez ujmy na všeobecnosti vybrať dvojicu a nemať medzi nimi lanovku. Potom vieme, že z nich do ostatných bude viesť lanovka. Zvyšné stanice sú teda všetky ekvivalentné a môžeme vytvoriť ďalšiu dvojicu. Takto teda dosiahneme, že lanoviek bude od maximálneho počtu menej o toľko, koľko dvojíc medzi stanicami vieme vytvoriť. Vo Vysokých Taurách je teda najmenej \(\frac{n(n-1)}{2} - \lfloor \frac{n}{2} \rfloor\) lanoviek.
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ť.