Cím: A 2006. évi Kürschák József Matematikai Tanulóverseny feladatinak megoldásai
Szerző(k):  Fleiner Tamás 
Füzet: 2007/február, 68 - 74. oldal  PDF  |  MathML 
Témakör(ök): Kürschák József (korábban Eötvös Loránd), Matematika, Szakmai cikkek

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.

1. feladat. Létezik-e a 3-dimenziós térben olyan, 2006 pontból álló H halmaz, amelyre az alábbi tulajdonságok teljesülnek:
(a) H pontjai nem esnek egy síkba,
(b) H-nak semelyik három pontja sem esik egy egyenesre, továbbá
(c) a H bármely két pontját összekötő egyeneshez létezik tőle különböző, vele párhuzamos, H két pontját összekötő egyenes?

 
Megoldás. Vegyük észre, hogy n≥5 esetén egy szabályos n oldalú sokszög csúcsainak H' halmaza teljesíti a feladatban előírt (c) feltételt.
Legyenek ugyanis P,Q∈H' tetszőleges csúcsok. Ekkor a PQ egyenesnek valamelyik partján legalább két H'-beli pont van. Tekintsük ebben a félsíkban a szabályos sokszögnek a P-vel szomszédos P', illetve a Q-val szomszédos Q' csúcsát. Mivel a szabályos n-szög körülírt körén PP' és QQ' azonos nagyságú ívet határoznak meg, azért a hozzájuk tartozó PQP' és QP'Q' kerületi szögek egyenlőek, tehát e szögek a párhuzamos PQ és P'Q' egyenesekhez tartozó váltószögek.
 
 

Válasszunk egy 1002 oldalú szabályos sokszöget, és egy ettől különböző síkba eső, 1004 oldalú szabályos sokszöget úgy, hogy O középpontjuk közös legyen, és a két sokszög síkjának metszésvonalán egyik sokszögnek se legyen csúcsa. Állítjuk, hogy e két sokszög csúcsainak H halmaza megfelelő, ezért a feladat kérdésére igen a válasz.
Világos, hogy H-nak éppen 2006 pontja van. A konstrukció miatt H pontjai nem esnek egy síkba: (a) teljesül. A szabályos sokszögek konvex tulajdonsága miatt egy egyenes a két sokszög bármelyikének legfeljebb két csúcsát tartalmazhatja. Márpedig ha egy egyenes valamelyik sokszögből két csúcsot tartalmaz, akkor annak a síkjában fut, tehát a másik sokszögnek nem tartalmazza egyetlen további csúcsát sem. A (b) tulajdonság is teljesül tehát.
A (c) tulajdonság igazolásához tegyük fel először, hogy P és Q ugyanannak a sokszögnek csúcsai. Ekkor legelső megfigyelésünk szerint találunk megfelelő P'-t és Q'-t már ugyanebben a sokszögben is. Ha azonban P és Q nem ugyanabba a sokszögbe esnek, akkor az O-ra vonatkozó P' és Q' tükörképeik szintén H-beliek, különböznek P-től és Q-tól, és PQ∥P'Q'.  □
 
Megjegyzés. A fenti megoldásban vázolt konstrukció szépséghibája, hogy túl sok (szám szerint 1004) pont esik egy síkba. Természetes kérdés, hogy a feladat feltételeit teljesítő H halmazban legfeljebb hány pontnak engedhetjük meg, hogy egy síkba essen. Egyrészt világos, hogy egy ilyen H halmaznak mindig van 4 egysíkú pontja, hisz ha PQ∥P'Q', akkor a P, Q, P', Q' pontok közös síkban fekszenek. Másfelől, a megoldás konstrukciójának módosításával tudunk olyan H-t mutatni, ahol ez a szám 6. Ha ugyanis 501 különböző síkban fekvő, szabályos hatszöget választunk úgy, hogy az egyik átmérőjük közös, akkor e hatszögek csúcsainak H halmaza is megfelel a feladatbeli feltételeknek. Sajnos azonban a hatszögek közös átmérőjére merőleges síkok közül kettő is tartalmaz 1002 pontot. Ezen úgy tudunk segíteni, hogy nem szabályos hatszögekből, hanem azok vetületeiből építkezünk. Könnyen látható, hogy az ezen hatszögek csúcsai alkotta halmaz is megfelelő, és alkalmas vetítések választásával elérhető, hogy a legtöbb egysíkú pontot akkor kapjuk, ha egy konstrukcióbeli hatszög síkját tekintjük.
A feladat megoldásában leírt konstrukció egy másik sajátossága, hogy a kapott H halmaz centrálszimmetrikus lesz. Ennek egy következménye, hogy H páros számú pontot tartalmaz. Létezik azonban páratlan sok (mondjuk 2007) pontból álló H halmaz is, azonban a középpontos szimmetria abban is lényeges szerepet kap. Belátható, hogy ha két nem egysíkú, közös átmérőjű szabályos 1004 oldalú szabályos sokszög csúcsai közül elhagyjuk az egyik közös csúcsot, akkor az (a), (b) és (c) feltételt kielégítő, 2007 pontú H halmazt kapunk. Nem világos, hogy páratlan méretű, kívánt tulajdonságú halmazból létezik-e olyan, ami nem ,,ennyire'' centrálszimmetrikus. Mint láttuk, a síkban van ilyen, pl. egy páratlan oldalú szabályos sokszög (vagy annak vetülete).
 
2. feladat. Legyenek a, n és t pozitív egészek, amelyekre a≤n teljesül. Tekintsük az {1,2,...,n} halmaz azon részhalmazait, melyekben bármely két elem különbsége legalább t. Bizonyítsuk be, hogy e halmazok közül az a-t nem tartalmazók száma legfeljebb t2-szerese az a-t tartalmazók számának.
 
Megoldás. Tekintsük az {1,2,...,n} halmaz azon a-t tartalmazó részhalmazait, melyekben bármely két különböző elem különbsége legalább t. Legyen H ezen részhalmazok halmaza. Álljon a K halmaz az {1,2,...,n} halmaz mindazon részhalmazaiból, amelyek a-t nem tartalmazzák, és amelyekben bármely két elem különbsége legalább t. Azt kell megmutatnunk, hogy |K|≤t2⋅|H| teljesül.
Ezt úgy bizonyítjuk be, hogy K minden eleméhez hozzárendeljük H egy-egy elemét úgy, hogy H minden egyes elemét K-nak legfeljebb t2 eleméhez rendeljük hozzá. Más szóval, mutatunk egy f:K→H leképezést, amire az teljesül, hogy H minden egyes eleme legfeljebb t2 elem képeként áll elő. Tetszőleges X∈K részhalmazhoz tekintsük az
f(X):=(X∖{a-t+1,a-t+2,...,a+t-2,a+t-1})∪{a}
halmazt, azaz hagyjuk el X-ből azokat az elemeket, amik a-hoz t-nél közelebb vannak, és vegyük be a-t f(X)-be. Világos, hogy f(X)∈H, hisz a∈f(X) teljesül, f(X)∖{a} bármely eleme legalább t-vel különbözik a-tól, továbbá f(X) bármely két a-tól különböző eleme egyúttal X-nek is eleme, ezért különbségük legalább t.
Megmutatjuk, hogy H bármely Y eleméhez legfeljebb t2-féleképpen választhatunk olyan X∈K-t, amelyre f(X)=Y. Hogyan képezhetjük egy adott Y-hoz ezeket az X halmazokat? Világos, hogy minden ilyen X-et megkaphatunk úgy, hogy Y-ból elhagyjuk az a elemet, majd további elemeket veszünk be az [a-t+1,a-1], illetve az [a+1,a+t-1] intervallumból úgy, hogy az így kapott halmazban is teljesüljön, hogy bármely két elem különbsége legalább t. Ez azt jelenti, hogy mind az [a-t+1,a-1], mind az [a+1,a+t-1] intervallumokból legfeljebb egy-egy elemet választhatunk ki. Mivel mindkét intervallum t-1 elemet tartalmaz, azért mindkét intervallum esetén t-féle választási lehetőségünk van: (t-1)-féleképp választhatunk ki egy elemet, illetve egyféleképp tehetjük meg, hogy nem választunk egyetlen elemet sem. Összességében tehát legfeljebb t⋅t=t2 a lehetőségeink száma. Ezért H tetszőleges eleme legfeljebb t2 K-beli elem képe, így csakugyan igaz, hogy
|K|≤t2|H|.□

 
Megjegyzés. A fenti becslés t>2 esetén javítható, ugyanis amikor Y∈H-hoz konstruálunk olyan X∈K-t, amire f(X)=Y teljesül, akkor általában nem tehetjük meg, hogy tetszőlegesen választjuk az [a-t+1,a-1]-beli és az [a+1,a+t-1]-beli elemeket. Ügyelnünk kell ugyanis arra is, hogy e két kiválasztott elem különbsége se legyen t-nél kisebb. Ezt figyelembe véve a becslésbeli t2 tényező 12⋅(t2+3t-2)-re javítható.
 
3. feladat. Egy kör alakú asztalnál n játékos foglal helyet, akik között valahogyan szétosztunk n-1 kártyalapot. Ezután a játékosok a következő szabály szerint cserélgetik egymás között a lapjaikat: ha létezik olyan játékos, akinél legalább két kártyalap van, akkor valamelyik ilyen játékos átad egy-egy kártyát a két szomszédjának. Bizonyítsuk be, hogy bárhogyan is cserélgetnek, előbb-utóbb minden játékosnál legfeljebb egy kártyalap lesz.
 

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.