9. príklad - Vzorové riešenie
Kategórie:
5
6
7
8
9
Zadanie
V mestečku Pod Horou bola postavená nová sieť autobusových tratí. Je zostavená veľmi zaujímavým spôsobom. Na každej trati sú
tri zastávky. Okrem toho každé dve trate buď nemajú spoločnú zastávku, alebo majú len jednu spoločnú zastávku. Aký najväčší
počet tratí môže byť v mestečku, ak vieme, že je len deväť rôznych zastávok?
Vzorové riešenie
Opravovali: david, erik, repa, ľubo
Na začiatok pre prehľadnosť pri riešení je fajn si zastávky v mestečku Pod Horou nejak označiť. Keďže naše zastávky nám pripomínajú body v geometrii, budeme si ich teda označovať písmenami abecedy a síce A-I. Skúsme sa teraz pozrieť, čo sa stane, ak vytvoríme trať ABC. V zadaní sa píše, že ľubovoľné dve trate môžu mať najviac jeden bod spoločný. Preto naša trať ABC spôsobí, že už žiadna trať nemôže mať spojenie AB, BC alebo AC. Inak by sme mali dve trate, ktoré majú spoločné dve zastávky. Zistili sme vlatne, že pre jednu trať máme 3 spojenia, ktoré už nevieme použiť. Skúsme sa teraz pozrieť na to, koľko spojení máme celkovo v našom mestečku. Hľadáme teda všetky dvojice z 9 bodov. Ľahko sa môžeme presvedčiť, že týchto spojení je 36. A keďže na každú trať si minieme 3 spojenia, tak máximálny počet tratí dostaneme ľahko ako \frac{36}{3}=12. Vyšlo nám teda, že maximálny počet tratí je 12. Ideálne je ešte overiť si, že či je aj takýto počet tratí reálne možné vytvoriť. Túto úlohu už ale necháme na čitateľa (hint: v 3x3 štvorci sa tvárime, že pri šikmých tratiach vieme chodiť cez steny).