Az A. 701. feladat (2017. szeptember)

A. 701. Egy légitársaság az Európai Unió bármely két tagállamának fővárosa között egy rögzített árú járatot üzemeltet (az ár oda és vissza mindig megegyezik). Tudjuk még, hogy egy városból nem indul két azonos árú járat. Anna és Bella mindegyik várost pontosan egyszer szeretné meglátogatni, nem feltétlenül ugyanabból a városból indulva. Anna úgy tervezi útját, hogy egy városból mindig abba a még nem meglátogatott városba megy tovább, amibe a lehető legolcsóbb járat vezet. Bella pedig minden városból a lehető legdrágább járaton megy tovább.

Igaz-e, hogy Bella útja biztosan legalább annyi pénzbe kerül, mint Anna útja?

(Szovjet feladat alapján)

(5 pont)

A beküldési határidő 2017. október 10-én LEJÁRT.

Megoldás. Az Európai Unióban \(\displaystyle n\) darab főváros található.

[Megjegyzés. Figyeljük meg, hogy Bella útja pontosan akkor kerül mindig legalább annyiba, mint Annáé, hogyha Anna \(\displaystyle k\)-adik legolcsóbb járata sosem kerül többe, mint Bella \(\displaystyle k\)-adik legolcsóbb járata minden \(\displaystyle k\)-ra. Soroljuk ugyanis fel az összes járatárat növekvő sorrendben: ekkor Anna és Bella útja csak attól függ, hogy e sorrendben hányadik az egyes városok közötti járatok ára. Ha előfordulhat egy \(\displaystyle k\)-ra, hogy Anna \(\displaystyle k\)-adik legolcsóbb járata drágább, mint Bella \(\displaystyle k\)-adik legolcsóbb járata, akkor a relációs sorrendet megtartva tudjuk úgy változtatni a járatárakat, hogy Anna teljes útja is drágább legyen.]

Belátjuk, hogy Anna \(\displaystyle k\)-adik járata legfeljebb annyi pénzbe kerül, mint Bella \(\displaystyle k\)-adik legolcsóbb járata (minden \(\displaystyle k=1,2,\dots,n\) esetén).

Állításunk következik abból, hogy minden \(\displaystyle k=1,2,\dots,n\) esetén Bella \(\displaystyle k\) darab legolcsóbb járatát tekintve, Annának legalább \(\displaystyle k\) darab olyan járata van, ami ezek valamelyikénél nem drágább. (Ha ugyanis van Annának \(\displaystyle k\) darab járata, ami nem drágább, mint Bella \(\displaystyle k\)-adik legolcsóbb járata, akkor a \(\displaystyle k\)-adik legolcsóbb járata is olcsóbb. Nem a megoldásba tartozik, de hasonló ötletet hordoz a Kőnig(-Hall)-tétel is.)

A városrendszer képzeletben átrendezhető úgy, hogy Bella nyugat felől kelet felé haladva látogassa végig a fővárosokat. Azt mondjuk, hogy egy járat kellemes, hogyha legfeljebb annyi pénzbe kerül, hogy Bella \(\displaystyle k\)-adik legolcsóbb járata, és legyenek Bella kellemes járatai

\(\displaystyle x_1y_1\), \(\displaystyle x_2y_2\), \(\displaystyle \dots\), \(\displaystyle x_ky_k\) (ahol \(\displaystyle x_1,x_2,\dots,x_k\) és \(\displaystyle y_1,y_2,\dots,y_k\) nyugat felől kelet felé haladó sorrendben vannak).

Egy város jó avagy rossz lehet attól függően, hogy Anna azon városból induló járata kellemes-e avagy nem kellemes (vagy nem létezik).

\(\displaystyle \bullet\) Hogyha minden \(\displaystyle x_i\) jó, máris találtunk Anna útjában \(\displaystyle k\) darab kellemes járatot.

\(\displaystyle \bullet\) Egyéb esetben valamely \(\displaystyle \ell\)-re \(\displaystyle x_1,x_2,\dots,x_{\ell-1}\) jó, de \(\displaystyle x_\ell\) már nem jó. Minden \(\displaystyle x_\ell\)-ből kelet felé haladó járat kellemes, mert Bella módszeréből adódóan legfeljebb annyi pénzbe kerül, mint \(\displaystyle x_\ell y_\ell\).

\(\displaystyle \bullet\) Mivel \(\displaystyle x_\ell\) rossz, ezért mikor Anna \(\displaystyle x_\ell\)-be látogatott, az összes attól keletre lévő várost már végigjárta (egyébként választhatott volna kellemes járatot \(\displaystyle x_\ell\)-ből kelet felé).

\(\displaystyle \bullet\) Ha \(\displaystyle v\) egy, az \(\displaystyle x_\ell\)-től keletre fekvő város, Anna \(\displaystyle v\)-ből a \(\displaystyle vx_\ell\) kellemes járaton vagy egy még olcsóbb járaton haladt tovább.

\(\displaystyle \bullet\) Tehát \(\displaystyle x_1,x_2,\dots,x_{\ell-1}\) és \(\displaystyle y_\ell,y_{\ell+1},\dots,y_k\) mind jó város, és így Annának legalább \(\displaystyle k\) darab kellemes járata volt.

Ezzel beláttuk, hogy Bella \(\displaystyle k\)-adik legolcsóbb járatánál Anna \(\displaystyle k\)-adik legolcsóbb járata nem lehet drágább (\(\displaystyle k=1,2,\dots,n\) esetén), és így a feladat állítása igaz.

Statisztika:

20 dolgozat érkezett.
5 pontot kapott:	Bukva Balázs, Döbröntei Dávid Bence, Egri Máté, Gáspár Attila, Imolay András, Matolcsi Dávid, Molnár-Sáska Zoltán, Németh 123 Balázs, Perényi Gellért.
4 pontot kapott:	Szabó Kristóf.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	8 versenyző.

A KöMaL 2017. szeptemberi matematika feladatai