Feladat: 2006. évi Kürschák matematikaverseny 3. feladata Korcsoport: - Nehézségi fok: -
Füzet: 2007/február, 70 - 74. oldal  PDF  |  MathML 
Témakör(ök): Kürschák József (korábban Eötvös Loránd), Logikai feladatok, Többszemélyes véges játékok
Hivatkozás(ok):Feladatok: 2007/február: 2006. évi Kürschák matematikaverseny 3. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A megoldások során az alábbi szóhasználattal élünk. Azt mondjuk, hogy az x játékos oszt, ha x a kezében levő legalább két kártyalap közül egyet-egyet átad a szomszédainak.

 
I. megoldás. Elsőként azt bizonyítjuk, hogy lesz olyan játékos, aki a játék során egyáltalán nem fog osztani. Tegyük fel, hogy a játékban használt kártyalapok egymástól jól megkülönböztethetőek, és a játékosok az alábbi megkötéssel játsszák a játékot:

Ha x és y szomszédos játékosok, és kettőjük közül x oszt előbb, akkor az a kártya, amit x az első osztásakor átad y-nak, ezentúl csak x és y között fog mozogni.

Könnyű meggondolni, hogy az eredeti játék tetszőleges lejátszását meg lehet tenni a fenti szabály betartásával. Ha ugyanis x első osztását követően valamikor az x vagy y játékos oszt, akkor két lehetőség van. Ha az osztónál van a szabályban meghatározott κ kártya, akkor az tud úgy osztani, hogy a κ kártya x és y között mozogjon. Ha pedig κ nincs az osztónál, akkor kell lennie az osztónál egy olyan κ' kártyának, amit nem kell a fenti szabály miatt az osztó másik szomszédjának átadni. Ha tehát κ' mozog x és y között, az nem sérti a szabályt.
Világos, hogy a fenti szabály minden szomszédos játékospárhoz legfeljebb egy kártyát rendel, mégpedig úgy, hogy különböző játékospárok különböző kártyákon osztoznak. Mivel csak n-1 kártya van játékban, azért legfeljebb n-1 szomszédos játékospárnak lesz ,,közös kártyája''. Lesz tehát két szomszédos játékos (mondjuk x és y), akik sosem fognak egymásnak kártyát adni. Más szóval sem x, sem y nem oszt a játékban.
A fenti gondolatmenetből csak annyit használunk, hogy x sosem fog osztani. Ezért x bármelyik szomszédja csak véges sokszor oszthat a játék során, hiszen minden osztáskor x-hez kerül egy-egy lap, ami onnantól x-nél marad. A játékban tehát előbb-utóbb eljön egy pillanat, ami után x szomszédai már nem osztanak többször. Ezt követően x másodszomszédai is csak véges sokszor oszthatnak, hiszen e másodszomszédok minden egyes osztásakor x valamelyik szomszédjához kerül egy kártya, aki azt már sosem osztja ki. Előbb-utóbb tehát a másodszomszédok sem fognak osztani, így a gondolatmenet megismételhető az x játékos harmadik szomszédaira, azok szomszédaira stb. Azt kapjuk, hogy véges sok osztás után bekövetkezik egy olyan pillanat, amikor már egyik játékos sem tud osztani. Ez pedig azt jelenti, hogy olyan helyzethez érkeztünk, amikor bármelyik játékosnál legfeljebb 1 kártya található. Nekünk pedig pontosan ezt kellett bizonyítanunk.  □
 
A továbbiakban nevezzük játékosok egy H valódi részhalmazát csapatnak, ha a H-beli játékosok egymás közvetlen szomszédai az asztal valamely körüljárása által meghatározott sorrendben, azaz, ha a H-beli játékosok egy ívet határoznak meg az asztal mentén.
 
II. megoldás. Indirekt bizonyítunk: tegyük fel, hogy a játék sosem ér véget, azaz végtelen sok osztás történik. Állítjuk, hogy tetszőleges 1≤k≤n-1 egész szám esetén a játékban előbb-utóbb elérkezik egy pillanat, amikortól kezdve bármely k tagú csapatnál összesen legfeljebb k kártya lesz. A k=1 eset éppen a bizonyítandó állítás. A fenti állítást k szerinti teljes indukcióval bizonyítjuk: k=(n-1)-re az állítás nyilvánvaló, hiszen összesen n-1 kártya van forgalomban. Tegyük fel tehát, hogy egy k-ra már bizonyítottuk az indukciós feltevést, és a cél, hogy (k-1)-re igazoljuk azt. (Annyiban szokatlan ez a teljes indukció, hogy a k változó csökken, és nem növekszik.)
Legyenek tehát x1,x2,...,xk-1 szomszédos játékosok, és tekintsük azt, az indukciós feltevés értelmében előbb-utóbb elérkező t időpillanatot, amikortól kezdve bármely k tagú csapatnál legfeljebb k kártya van. Legyen x0 az x1 játékos x2-től különböző szomszédja1. Ha az x0 játékos innentől sosem oszt, akkor x0-nál csak halmozódnak a kártyák, ezért x0 szomszédai is csak véges sokszor oszthatnak a játék folyamán. Egy pillanattól kezdve tehát x0 szomszédai már nem osztanak, de innentől fogva náluk is halmozódnak a lapok, tehát x0 másodszomszédai is csak véges sokszor oszthatnak stb. Azt kapjuk, hogy minden játékos véges sokszor oszt, tehát az egész játék véges sok osztásból áll, ami ellentmond az indirekt feltevésnek.
Látjuk tehát, hogy x0 a t időpont után is előbb-utóbb osztani fog. Ekkor x0-nál legalább két kártya van, az {x0,x1,...,xk-1} csapatnál pedig az indukciós feltevés miatt legfeljebb k kártya található. Tehát az x1,...,xk-1 játékosok ekkor legfeljebb k-2 kártyát tartanak. Megmutatjuk, hogy az {x1,...,xk-1} csapat ezt követően sosem fog (k-1)-nél több kártyát birtokolni. Tegyük fel ugyanis, hogy ez mégiscsak megtörténik egy osztás után. Világos, hogy ezt az osztást csak x0 vagy az xk-1 játékos xk-2-től különböző xk szomszédja végezhette. Mivel az osztás után az {x1,...,xk-1} csapatnál összesen legalább k kártya lesz, azért az osztást megelőzően az x1,...,xk-1 játékosoknál és az osztónál együttesen legalább k+1 kártya volt. Márpedig ez az indukciós feltevés szerint lehetetlen, hiszen egy k tagú csapatnál a t időpont után legfeljebb csak k kártya lehet.
A fentiek szerint tehát egy időponttól kezdve bármely k-1 tagú csapatnál legfeljebb k-1 kártya lesz. Ezzel az indukciós lépést igazoltuk, a feladat állítását bebizonyítottuk.  □
 
Megjegyzések. 1. A feladatban leírt játék az ún. ,,chip firing'' játék egy speciális esete. Az általános chip firing játékban adott egy G gráf, aminek a csúcsaiban ülnek a játékosok, akik között a kártyákat szétosztjuk. Ha egy x játékosnál legalább annyi kártya van, mint ahány szomszédja, akkor x megteheti, hogy minden szomszédjának átad egy-egy kártyát. Az I. megoldás módszerével megmutatható, hogy ha a G gráf összefüggő, és a kiosztott kártyák száma kevesebb |E(G)|-nél, akkor a játék előbb-utóbb véget ér, ugyanis lesz G-nek olyan éle, amelyhez nem ragad kártya, azaz a két végpontban ülő játékosok sosem osztanak. (A II. megoldás is általánosítható: ekkor k tagú csapat helyett k csúcs által feszített összefüggő részgráfokra vonatkozik az indukciós feltevés.)
2. Érdekes megfigyelés, ami a megoldáshoz úgy tűnik nem vezet közelebb, hogy a játék lejátszása nélkül megállapítható, hogy melyik játékosnál nem lesz kártya a játék végén. Ha ugyanis az asztal egy körüljárása szerint megszámozzuk a játékosokat 1-től n-ig, és minden kártyához hozzárendeljük az adott kártyát birtokló játékos sorszámát, akkor egy osztás után a kártyákhoz rendelt számok összegének n-nel vett osztási maradéka nem változik. Ha tehát tudjuk, hogy véget ér a játék, és az i sorszámú játékosnál nem marad kártya, akkor 1+2+...+n-i ugyanannyi maradékot ad n-nel osztva, mint a kiinduláskor kiszámolt összeg. Ebből pedig i egyértelműen meghatározható.
3. A fenti megfigyelés általánosítható. Nemcsak az igaz, hogy a végső állapot független a játék konkrét lejátszásától, hanem az is, hogy a végső állapothoz vezető osztások száma sem függ attól, hogy hogyan megy végbe a játék. Ez az alábbi, az általános chip firing játékra is érvényes (és hasonlóan bizonyítható) tényből következik:
 
Állítás. Tegyük fel, hogy az S kiindulási helyzetben az x1,x2,...,xn játékosoknál rendre a1,a2,...,an kártya van. Tegyük fel továbbá, hogy S-ből kiindulva a játék egy bizonyos lejátszás szerint véget ér, és eközben az x1,x2,...,xn játékosok rendre b1,b2,...,bn osztást végeznek. Ekkor az S helyzetből kiindulva a játék tetszőleges lejátszás szerint véget ér, és a végső állapotba eljutásig az x1,...,xn játékosok rendre b1,...,bn számú osztást végeznek.
 
Bizonyítás. Tegyük fel, hogy egy S-ből induló lejátszásban van olyan xi játékos, aki bi-nél többször oszt. Válasszuk ki azt az xi játékost, akivel ez először bekövetkezik. Az xi játékos (bi+1)-edik osztása előtt xi-nél legfeljebb k=ai-2⋅bi+bi-1+bi+1 számú kártya található, hisz xi-1 és xi+1 eddig legfeljebb bi-1, illetve bi+1 osztást végeztek. Márpedig a referencialejátszás végén pontosan k az xi-nél található kártyák száma, ezért k kisebb xi szomszédai számánál, azaz 2-nél. Tehát egyetlen xi játékos sem tud bi-nél többször osztani, amennyiben az S állapotból indul a játék.
A fentiek miatt nem történhet meg, hogy azonos állapotból kiindulva, két különböző lejátszás szerint egy játékos kevesebbszer oszt az egyik lejátszásban, mint a másikban. Tehát minden játékos ugyanannyiszor oszt, függetlenül a lejátszásbeli osztások sorrendjétől.  □
 
Következmény. Ha egy S állapotból kiindulva véget ér a chip firing játék, akkor S-ből indulva a játék tetszőleges lejátszás esetén véget ér, és a végső állapot nem függ az osztások sorrendjétől.
 
Bizonyítás. A játék bármely lejátszása b1+b2+...+bn számú osztásból áll, és a lejátszás után az xi játékosnál található kártyák száma
ri=ai-2⋅bi+∑{bj:xj  az  xi  szomszédja}.
A kapott ri mennyiség független a lejátszástól.  □
 
Következmény. Ha egy S állapotból kiindulva véget ér a chip firing játék, akkor lesz olyan játékos, aki a játék során egyáltalán nem oszt.
 
Bizonyítás vázlat. Tegyük fel, S-ből indulva úgy ér véget a játék, hogy a játékosok által elvégzett b1,b2,...,bn osztások számának mindegyike pozitív. Legyen xi az a játékos, aki egy lejátszás során elsőként fejezi be a saját osztásait, és jelölje di az xi szomszédainak számát. Ezen osztás után az xi-nél található kártyák száma legfeljebb
ai-di⋅bi+∑{bj-1:xj  az  xi  szomszédja}==(ai-di⋅bi+∑{bj:xj  az  xi  szomszédja})-di<0,


ami ellentmondás.  □
 
Az idei 3. feladat kapcsolódik az 1984. évi Kürschák verseny 3. feladatához, illetve az 1986. évben rendezett Nemzetközi Matematikai Diákolimpia 3. feladatához. Mindkét említett feladat megoldható volt egy alkalmas energiafogalom bevezetésével, és ez a mostani 3. feladatra is igaz.
 
III. megoldás (vázlat). A játék egy pillanatában egy H csapat energiája legyen a H által birtokolt kártyák számának és a H csapat létszámának abszolút különbsége, a rendszer energiája pedig legyen az összes lehetséges csapat energiájának összege.
Vizsgáljuk meg, hogy egy x játékos osztása után hogyan változik a rendszer energiája! Világos, hogy az egyszemélyes {x} csapat energiája nem növekszik az osztás után. Az x-től különböző játékosok alkotta X csapat energiája pedig szigorúan csökken, hiszen az osztás előtt és után is legfeljebb annyi kártyájuk volt, mint ahányan voltak. Könnyen ellenőrizhető, hogy e két csapaton túl pontosan azoknak a H csapatoknak változik az energiája, amelyekre H∪{x} és H∖{x} is csapat. Az ilyen csapatok diszjunkt párokba rendezhetőek, ahol minden pár egy x-et nem tartalmazó H csapatból és az x-et tartalmazó H∪{x} csapatból áll. Ezen csapatok mindegyikének pontosan 1-gyel változik az energiája x osztása után. Ha egy ilyen H csapat energiája növekszik, akkor az osztás előtt a H-beli játékosoknál már legalább |H| kártya volt, ezért a H∪{x} csapat az osztás előtt legalább |H|+2>|H∪{x}| kártyát tartott kézben. Vagyis x osztása után a H∪{x} csapat energiája csökken. Azt kaptuk, hogy a párokba osztott csapatok összenergiája nem növekedhet. Összességében tehát a rendszer energiája minden osztással szigorúan csökken.
A rendszer energiája a játék minden pillanatában egy pozitív egész szám, így az csak véges sokszor csökkenhet. Ezért a játék során előbb-utóbb bekövetkezik egy pillanat, amikor a rendszer energiája már nem csökkenhet tovább, azaz nem végezhető újabb osztás. Márpedig ekkor minden játékosnál legfeljebb egy kártya található.  □
1Ha x0-nak nincs két különböző szomszédja, akkor n=2, és a bizonyításhoz nincs szükség indukcióra.