Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem A. 701. (September 2017)

A. 701. An airline operates flights between any two capital cities in the European Union. Each flight has a fixed price which is the same in both directions. Furthermore, the flight prices from any given city are pairwise distinct. Anna and Bella wish to visit each city exactly once, not necessarily starting from the same city. While Anna always takes the cheapest flight from her current city to some city she hasn't visited yet, Bella always continues her tour with the most expensive flight available. Is it true that Bella's tour will surely cost at least as much as Anna's tour?

(Based on a Soviet problem)

(5 pont)

Deadline expired on October 10, 2017.


Sorry, the solution is available only in Hungarian. Google translation

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 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.


Statistics:

20 students sent a solution.
5 points: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 points:Szabó Kristóf.
1 point:2 students.
0 point:8 students.

Problems in Mathematics of KöMaL, September 2017