Feladat: Gy.2784 Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Koblinger Egmont 
Füzet: 1993/január, 23. oldal  PDF  |  MathML 
Témakör(ök): Gráfok összefüggősége, Konstruktív megoldási módszer, Gyakorlat
Hivatkozás(ok):Feladatok: 1992/szeptember: Gy.2784

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Vizsgáljunk egy várost, jelölje ezt A. Ebből közvetlenül legfeljebb 3 másikba juthatunk el. E három városból pedig legfeljebb további 3⋅2=6 város érhető el közvetlenül, mindegyikből 3-3, de azokból az egyik A.
Ez A-val együtt legfeljebb 10 várost jelent. Minthogy A-ból legfeljebb egy átszállással csak a már felsorolt városokba juthatunk, igy a gépek legfeljebb 10 város között járnak.
Ez a maximális szám el is érhető. Tekintsük ugyanis az alábbi ábrát, ahol minden csúcs egy-egy várost jelöl, a köztük futó élek pedig járatokat.

 
 

Látható, hogy minden csúcsból pontosan három él indul ki (azaz minden városból pontosan három járat indul). Az is könnyen ellenőrizhető, hogy legfeljebb egy átszállással mindenhonnan 9 másik városba lehet eljutni (vagyis az összes többibe). Ehhez elég 1‐1 várost a ,,külső'', illetve a ,,belső'' ötszögből megnézni: mindkettőből 3‐3 másikba, majd azokból további 3⋅2-be lehet eljutni, ami összesen 9.
Tehát a kérdésre a válasz 10.
Megjegyzés. Belátható, hogy 2,3,...,8 városra szintén létezik ilyen repülőjáratrendszer, de 9-re nem. Sokan ‐ tévesen ‐ ebből arra következtettek, hogy 8 a maximális szám.