Az A. 918. feladat (2025. november)

A. 918. Egy \(\displaystyle n\) csúcsú fagráf (\(\displaystyle n\geq 2\)) csúcsait jelöljük \(\displaystyle v_1\), \(\displaystyle v_2\), ..., \(\displaystyle v_n\)-nel. Minden csúcson ül egy törpe, és minden törpének van valamennyi, de legalább \(\displaystyle n\) darab pénzérméje. Sorban, az indexek szerint növekvő sorrendben végighaladunk a csúcsokon, és mindig a soron következő csúcson ülő törpe elvesz egy érmét a leggazdagabb szomszédjától; ha több leggazdagabb is van, akkor mindegyiktől egyet-egyet.

Határozzuk meg \(\displaystyle n\) függvényében azt a legkisebb \(\displaystyle k\) értéket, amelyre teljesül, hogy tetszőleges \(\displaystyle n\) csúcsú fagráf esetén van olyan kezdeti pénzérme kiosztás, hogy kezdetben bármely két törpe pénzérméinek száma legfeljebb \(\displaystyle k\)-val térjen el egymástól, és a folyamat végén minden törpének pontosan ugyanannyi pénzérméje legyen, mint kezdetben volt.

Javasolta: Németh Márton (Budapest)

(7 pont)

A beküldési határidő 2025. december 10-én LEJÁRT.

Válasz: Megmutatjuk, hogy a legkisebb ilyen \(\displaystyle k\) érték az \(\displaystyle n-2\).

Konstrukció: Ahhoz, hogy \(\displaystyle k\geq n-2\), tekintsük az \(\displaystyle n-1\) csúcsú csillaggráfot, melynek közepe \(\displaystyle v\), levelei \(\displaystyle w\), \(\displaystyle w_2\), \(\displaystyle \ldots\), \(\displaystyle w_{n-2}\), illetve \(\displaystyle w\)-hez kössünk hozzá még egy levelet, \(\displaystyle u\)-t. Legyen a csúcsok indexelési sorrendje \(\displaystyle v, w, w_2, \ldots, w_{n-2}, u\).

A kulcsészrevétel az, hogy amikor egy levelen ülő törpe sorra kerül, akkor biztosan egy érmét vesz el egyetlen szomszédjától, vagyis amikor a szomszédja került sorra, akkor éppen ez a levél volt a leggazdagabb szomszédja (esetleg holtversenyben). Tehát az első lépésben \(\displaystyle v\)-be legalább \(\displaystyle n-3\) érme kerül. Ezután \(\displaystyle w\) biztosan elvesz érmét \(\displaystyle u\)-tól, azaz \(\displaystyle u\) kezdetben legalább \(\displaystyle n-3\) érmével gazdagabb \(\displaystyle v\)-nél. Ez javítható \(\displaystyle n-2\)-re, ha észrevesszük, hogy az \(\displaystyle n-3\) csak akkor lenne elérhető, ha \(\displaystyle v\) nem vesz el érmét \(\displaystyle w\)-től, azaz \(\displaystyle w\) sem vesz érmét \(\displaystyle v\)-től, azaz amikor \(\displaystyle w\) kerül sorra, akkor \(\displaystyle u\) szigorúan gazdagabb \(\displaystyle v\)-nél, ami ellentmondás.

Bizonyítás: Erősebben azt fogjuk megmutatni, hogy tetszőleges fa és sorrend mellett létezik olyan kiosztás, hogy minden törpe az összes szomszédjából elvesz érmét, amikor sorra kerül. Ez elégséges, hiszen ha egy csúcs fokszáma \(\displaystyle d\), akkor \(\displaystyle d\) alkalommal veszít rajta a törpe \(\displaystyle 1\) érmét, és egy alkalommal nyer \(\displaystyle d\)-t.

Minden fagráf egyben páros gráf is, úgyhogy színezzük a csúcsokat feketével és fehérrel úgy, hogy szomszédos csúcsok különböző színt kapjanak. Elegendő olyan konstrukciót találnunk, ahol a fekete és a fehér mezőkön külön-külön legfeljebb \(\displaystyle n-2\) a kezdeti érmeszám páronkénti különbözete, hiszen ekkor (az általánosság elvesztése nélkül) a fehér mezőkön ugyanannyivel növelve az érmék számát elérhető, hogy az egész gráfban legfeljebb \(\displaystyle n-2\) legyen ez a különbség. Ez a módosítás nem változtat a folyamaton, hiszen egy fekete csúcsot vizsgálva csak fehér mezők egymáshoz viszonyított érmeszáma számít.

Vizsgáljuk tehát csak a fekete mezőket. Vegyünk egy tetszőleges \(\displaystyle B\) fekete csúcsot, és adjunk neki \(\displaystyle 0\) érmét (nem zavar minket, ha a folyamat során az érmék száma negatívba megy, ezt is el tudjuk tolni). Ezután az \(\displaystyle i=2, 4, 6, \ldots\) lépésekben megadjuk, hogy hány érmét rakunk az olyan fekete csúcsokra, melyek \(\displaystyle B\)-től \(\displaystyle i\) távolságra vannak.

Egy \(\displaystyle i\) távolságra lévő \(\displaystyle B_i\) fekete csúcs esetén (\(\displaystyle i\geq 2\)) legyen \(\displaystyle BW_1B_2W_3\ldots B_i\) az (egyértelmű) út \(\displaystyle B\) és \(\displaystyle B_i\) között. Tekintsük azt a pillanatot, amikor a \(\displaystyle W_{i-1}\)-en ülő törpe vett el érmét a szomszédjaitól. Tegyük fel, hogy eddig \(\displaystyle B_{i-2}\)-nek \(\displaystyle a_1\) szomszédja vett el érmét, és maga \(\displaystyle B_{i-2}\) eddig \(\displaystyle \varepsilon_1\in \{0, 1\}\)-szer vett el érmét. Jelölje \(\displaystyle b_1\) a hozzárendelt érmeszámot, mely értelmes, hiszen \(\displaystyle i-2 < i\). Hasonlóan tegyük fel hogy \(\displaystyle B_i\)-nek eddig \(\displaystyle a_2\)-ször vett el érmét szomszédja, ő maga \(\displaystyle \varepsilon_2\in \{0, 1\}\)-szer. Végül jelölje \(\displaystyle d(v)\) a \(\displaystyle v\) csúcs fokszámát a gráfban.

Adjunk \(\displaystyle b_2 = b_1+\varepsilon_1d(B_{i-2})-a_1+a_2-\varepsilon_2 d(B_i)\) érmét \(\displaystyle B_i\)-nek! Most megmutatjuk, hogy a fekete (és logikusan a fehér) mezők ilyen érmekiosztása mellett bármely törpe minden szomszédjától vesz el érmét.

Ez utóbbit a csúcsok indexelése szerinti teljes indukcióval tesszük meg. Az első törpére a \(\displaystyle v\) csúcsban igaz az állítás, hiszen a fenti képletben az \(\displaystyle a_i\) és \(\displaystyle \varepsilon_i\) értékek \(\displaystyle 0\)-k lesznek, vagyis \(\displaystyle v\) minden szomszédja azt a \(\displaystyle b\) értéket kapja, amit \(\displaystyle v\) elsőként vizsgált szomszédja.

Ezután ha valamely lépésben (az általánosság elvesztése nélkül) egy fehér csúcs vesz el érméket, akkor tegyük fel, hogy annak a \(\displaystyle B\)-hez legközelebbi szomszédja \(\displaystyle B_{i-2}\), mely \(\displaystyle b_1\) érmét kapott. Az indukciós feltevés szerint kapott továbbá \(\displaystyle \varepsilon_1d(B_{i-2})\) érmét, illetve vesztett \(\displaystyle a_1\) érmét, tehát most \(\displaystyle b_1+\varepsilon_1d(B_{i-2})-a_1\) érméje van. A csúcs egy másik, \(\displaystyle B_i\) szomszédja \(\displaystyle b_2 = b_1+\varepsilon_1d(B_{i-2})-a_1+a_2-\varepsilon_2 d(B_i)\) érmével rendelkezett kezdetben, majd kapott \(\displaystyle \varepsilon_2 d(B_i)\) érmét, és vesztett \(\displaystyle a_2\)-t, tehát jelenleg szintén \(\displaystyle b_1+\varepsilon_1d(B_{i-2})-a_1\) érméje van. Ezzel az állítást beláttuk.

Elegendő tehát belátni, hogy két fekete csúcs kezdeti érméinek számának abszolút különbsége valóban legfeljebb \(\displaystyle n-2\). Legyen \(\displaystyle B_1\) és \(\displaystyle B_k\) tetszőleges két fekete csúcs. Legyen az őket összekötő út \(\displaystyle B_1W_1B_2W_2\ldots W_{k-1}B_k\). Jelölje továbbá \(\displaystyle x_i\) és \(\displaystyle y_i\) a \(\displaystyle B_i\) csúcson lévő érmék számát rendre abban a pillanatban, mielőtt a \(\displaystyle W_i\) illetve a \(\displaystyle W_{i-1}\) csúcs vett el érméket. A fentiek alapján \(\displaystyle x_i = y_{i+1}\).

Tudjuk, hogy \(\displaystyle |x_i-y_i|\leq d(B_i)\), hiszen \(\displaystyle B_i\) érméinek száma összesen \(\displaystyle d(B_i)\)-vel nőtt és csökkent, tehát ennyi lehet a maximális változása. Tehát

\(\displaystyle |x_1 - y_k| = |x_{k-1} - y_2|\leq \sum_{i=2}^{k-1} |x_i-y_i|\leq \sum_{i=2}^{k-1} d(B_i). \)

Továbbá a \(\displaystyle B_1\)-re írt érmeszám és \(\displaystyle x_1\) legfeljebb \(\displaystyle d(B_1)\)-gyel tér el. Hasonlóan a \(\displaystyle B_k\)-ra írt kezdeti érmeszám és \(\displaystyle y_k\) legfeljebb \(\displaystyle d(B_k)\)-val tér el. Tehát a keresett különbség legfeljebb

\(\displaystyle d(B_1) + \sum_{i=2}^{k-1} d(B_i) + d(B_k) \leq n-1, \)

hiszen a fekete csúcsokból induló élek nem esnek egybe.

Vizsgáljuk meg az egyenlőség esetét. Ekkor az \(\displaystyle x_i-y_i\) értékek azonos előjelűek, abszolút értékben egyenlőek \(\displaystyle d(B_i)\)-vel. Hasonlóan \(\displaystyle B_1\) kezdeti érmeszáma és \(\displaystyle x_1\) eltérése, illetve \(\displaystyle B_k\) kezdeti érmeszáma és \(\displaystyle y_k\) eltérése szintén megegyezik előjelben, és abszolút értékben \(\displaystyle d(B_1)\) és \(\displaystyle d(B_k)\). Ekkor viszont \(\displaystyle W_1\) illetve \(\displaystyle W_{k-1}\) rendre \(\displaystyle B_1\) és \(\displaystyle B_k\) előtt kerültek sorra, ami ellentmondás. Ezzel az állítást igazoltuk.

Statisztika:

Az A. 918. feladat értékelése még nem fejeződött be.

A KöMaL 2025. novemberi matematika feladatai