Tri mestá A,B,C je potrebné spojiť cestami tak, aby sa po nich dalo prejsť z každého mesta do každého iného mesta. Ako to realizovať, aby bol súčet dĺžok týchto ciest čo najmenší?
Obrázok vľavo pochopiteľne neznázorňuje optimálne riešenie. Ak Vás tento slávny problém zaujme, napíšeme si o ňom viac.
Poznámka 18.2.: Táto úloha nie je úplne triviálna. Nebojte sa pri riešení použiť silnejší matematický aparát, napríklad diferenciálny počet funkcií dvoch premenných. Na druhej strane, bolo by veľmi pekné, keby niekto z Vás našiel elementárne riešenie (presnejšie rigorózny dôkaz optimality daného riešenia) s použitím stredoškolskej matematiky.
Dobrá stránka aj so stredoškolskou matematikou na túto tému je na Cut The Knot.
OdpovedaťOdstrániťLev: Velmi dobry odkaz; to si dal niekto naozaj poriadnu namahu.
OdpovedaťOdstrániťJa som sa k tomuto problému dostal v zaujimavej knihe od Brinkhuisa a Tikhomirova (snad budem mat niekedy cas si ju precitat celu).
Tam sa ani tak nespominaju geometricke dokazy, ako skor aplikacie a interpretacie.
Napriklad sa jedna o najjednoduchsi netrivialny pripad problemu "facility location", resp. "mnohorozmerneho medianu", t.z.v. Fermatovho-Weberovho problemu.
Alebo z uplne ineho sudka: Ak by body A,B,C boli na stole, prevrtali by ste v nich dieru a pustili cez diery tri zavazia na spagatoch spolocne zauzlenych na konci, tak sa ten uzol stabilizuje akurat vo Fermatovom bode.
Tento problem ma vela zaujimavych a velmi netrivialnych zovseobecneni, ku ktorym sa mozno este dostanem aj na tomto blogu.