A B. 5140. feladat (2020. december)

B. 5140. Egy szigeten 10 ország található, ezek közül némelyek szomszédosak egymással, mások nem. Mindegyik ország egy saját valutát használ. Mindegyik országban egyetlen pénzváltó működik, a következő szabályok szerint: aki az adott ország valutájából 10 darabot befizet, az kap az összes szomszédos ország valutájából 1-1 darabot. Arisztid és Tasziló fejenként 100-100 egységgel rendelkeznek mindegyik ország valutájából. Ezután mindketten a nekik tetsző sorrendben váltogatják a pénzüket a különböző országok pénváltóiban, amíg csak van olyan valutájuk, amit tudnak váltani (tehát legalább 10 darab van belőle). Bizonyítsuk be, hogy a végén pontosan ugyanannyi bergengóc tallérja lesz Arisztidnek és Taszilónak (a bergengóc tallér a sziget egyik országának valutája).

Mészáros Gábor (Budapest) ötletéből

(6 pont)

A beküldési határidő 2021. január 11-én LEJÁRT.

Megoldás. Azt állítjuk, hogy Arisztid és Tasziló minden egyes ország pénzváltóját pontosan ugyanannyiszor fogja használni. Így mivel pontosan ugyanazokat a tranzakciókat hajtják végre (csak a sorrend különbözik), a végén is ugyanaz marad meg mindkettejüknél.

Jelölje \(\displaystyle a_1,a_2,\ldots,a_{10}\), illetve \(\displaystyle t_1,t_2,\ldots,t_{10}\) azt, hogy hányszor használta Arisztid, illetve Tasziló az egyes országok pénzváltóit összesen.

Indirekt tegyük fel, hogy van legalább egy olyan \(\displaystyle i\) index, amelyre \(\displaystyle a_i > t_i\). Ekkor vizsgáljuk meg Arisztid pénzváltásainak sorozatát, és keressük meg az első olyan váltást, amikor valamilyen \(\displaystyle k\)-ra legalább \(\displaystyle (t_k+1)\)-edik alkalommal használja a \(\displaystyle k\)-adik ország pénzváltóját. Tekintsük a kérdéses váltás előtti pillanatot. Ebben a pillanatban minden \(\displaystyle k \neq i\)-re teljesül, hogy az \(\displaystyle i\)-edik ország pénzváltóját Arisztid legfeljebb \(\displaystyle t_i\)-szer használta. Így nála legfeljebb \(\displaystyle 100 - 10t_k + \sum_{i \neq k} t_i\) darab lehet a \(\displaystyle k\)-adik ország valutájából. De ez a \(\displaystyle 100-10t_k + \sum_{i \neq k} t_i\) mennyiség éppen annyi, amennyije Taszilónak van a \(\displaystyle k\)-adik ország valutájából, amikor a saját váltás-sorozatának a végére ért. Tehát az értéke 10-nél kevesebb. Ez viszont azt jelenti, hogy Arisztidnak a viszgált pillanatban 10-nél kevesebb darabja van a \(\displaystyle k\)-adik ország valutájából, tehát nem is tudja elvégezni a következő váltását, ellentmondás.

Következésképpen minden \(\displaystyle i\) indexre teljesül, hogy \(\displaystyle a_i \leq t_i\); de ugyanígy beláthatnánk azt is, hogy \(\displaystyle t_i \leq a_i\). Tehát valójában \(\displaystyle a_i = t_i\), azaz tényleg mindegyik pénzváltót ugyanannyiszor használták.

Megjegyzés: a gondolatmenet kicsit általánosabb környezetben is működik, ld. Mikkel Thorup: Firing Games című rövid cikkét (1996): http://hjemmesider.diku.dk/~mthorup/PAPERS/fire.ps.gz

Statisztika:

44 dolgozat érkezett.
6 pontot kapott:	Bán-Szabó Áron, Csonka Illés, Duchon Márton, Fülöp Csilla, Hegedűs Dániel, Jánosik Máté, Kercsó-Molnár Anita, Kovács 129 Tamás, Kökényesi Márk Péter, Mezey Dorottya, Móra Márton Barnabás, Móricz Benjámin, Nádor Benedek, Németh Márton, Simon László Bence, Sztranyák Gabriella, Terjék András József, Tóth 057 Bálint, Török Ágoston, Varga Boldizsár.
5 pontot kapott:	Csizmadia Miklós, Kalocsai Zoltán.
4 pontot kapott:	13 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	5 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2020. decemberi matematika feladatai