Problem B. 5140. (December 2020)

B. 5140. There are 10 countries on an island, some of which share a border, and some do not. Each country uses a currency of its own. Every country operates a single exchange office, by the following rules: if you pay 10 units of the currency of that country, you will get 1 unit of each of the currencies of the bordering countries. Initially Arthur and Theodore each own 100 units of the currency of every country. Then each of them shops around the exchange offices of various countries in any order they like, and keeps exchanging money while they can (that is, while they have at least 10 units of a kind). Prove that Arthur and Theodore will have the same number of Bergengocian dollars at the end (the Bergengocian dollar is the currency of one of the countries on the island).

Based on the idea of G. Mészáros, Budapest

(6 pont)

Deadline expired on January 11, 2021.

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

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

Statistics:

44 students sent a solution.
6 points:	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 points:	Csizmadia Miklós, Kalocsai Zoltán.
4 points:	13 students.
3 points:	1 student.
2 points:	5 students.
1 point:	1 student.
0 point:	2 students.

Problems in Mathematics of KöMaL, December 2020