Jelentés a 2025. évi Kürschák József Matematikai Tanulóversenyről

Fleiner Tamás

A Bolyai János Matematikai Társulat a 2025. évi Kürschák József Matematikai Tanulóversenyt október 10-én, közép-európai idő szerint 14 órai kezdettel rendezte meg a következő tizenhárom helyszínen: Budapest, Cambridge, Csíkszereda, Debrecen, Eger, Győr, Gyula, Ithaca, Kolozsvár, Miskolc, Szeged, Székesfehérvár és Veszprém.

A Társulat elnöksége a verseny lebonyolítására az alábbi bizottságot kérte fel: Biró András, Fleiner Tamás (elnök), Frenkel Péter, Harangi Viktor, Kós Géza, Kovács Benedek (titkár), Maga Péter, Pach Péter Pál és Tóth Géza. A bizottság szeptember 10-i ülésén az alábbi feladatokat tűzte ki:

1. Legyen \(\displaystyle n\) rögzített pozitív egész. Írjuk fel a \(\displaystyle 0\), \(\displaystyle 1\), \(\displaystyle \ldots\), \(\displaystyle n-1\) számokat egy táblára valamilyen sorrendben. Két szám egymással inverzióban áll, ha a nagyobb megelőzi a kisebbet. Egy \(\displaystyle k\) számot nevezzünk sajátságosnak, ha pontosan \(\displaystyle k\) másikkal áll inverzióban. Legfeljebb hány sajátságos szám lehet a táblán?

2. Ebben a feladatban tízes számrendszerben felírt számokról lesz szó. Megengedünk nullával kezdődő felírásokat is. Egy páros sok számjegyből álló számot vághatónak nevezünk, ha két egyenlő hosszú részre félbevágva a részek összegének négyzete az eredeti szám. Például \(\displaystyle 2025=(20+25)^2\) és \(\displaystyle 0001=(00+01)^2\) négyjegyű vágható számok. Bizonyítsuk be, hogy a \(\displaystyle 2n\)-jegyű vágható pozitív egész számok száma minden \(\displaystyle n\)-re 2-hatvány.

3. Adott \(\displaystyle n\ge 10\) pont a síkon, nincs három egy egyenesen. Bizonyítsuk be, hogy ki lehet őket színezni pirossal és kékkel úgy, hogy minden félsík, ami legalább \(\displaystyle 10\) pontot tartalmaz, tartalmaz piros és kék pontot is.

A bizottság november 27-i ülésén, a beérkezett dolgozatok átnézése után a következő jelentést fogadta el:

,,A verseny minden helyszínen rendben zajlott le, 119 regisztrált versenyzőtől összesen 104 dolgozat érkezett be.

A bizottság a versenyt követően szerzett tudomást arról, hogy a 2. feladat szerepelt az MBL tábor idei felvételi tesztjén. Sajnos az is csak későn derült ki, hogy a 3. feladat nehezebb formában nem csupán az 1992. évi Kürschák versenyen, hanem 2002-ben a KöMaL-ban is kitűzésre került A.281-es sorszám alatt. A bizottság egyelőre nem tervezi, hogy a feladatot a jövőben ismételten kitűzi.

Az idei versenyen 53-an oldották meg az első feladatot kisebb-nagyobb hiányossággal, a második feladatban pedig 15-en értek el érdemi eredményt. A harmadik feladat bizonyult a legnehezebbnek: ebben mindössze 9 versenyző tudott nemtriviális részeredményt felmutatni.

Két versenyző lényegében helyesen oldotta meg mindhárom kitűzött feladatot, ezért

I. díjat és \(\displaystyle 100\;000\) Ft pénzjutalmat nyer

Aravin Péter, az Ithaca High School 9. osztályos tanulója (tanárai Frederick Deppe, Pósa Lajos és Damásdi Gábor) valamint

Bodor Mátyás, a csíkszeredai Márton Áron Főgimnázium 12. osztályos tanulója (tanára Páll Olga).

Egy versenyző helyesen oldotta meg az 1. feladatot, azonban a 2. és 3. feladatokra adott megoldása kisebb kiegészítésre szorul. Ezért a teljesítményért

II. díjban és \(\displaystyle 60\;000\) Ft pénzjutalomban részesül

Morvai Várkony Albert, a Gödöllői Török Ignác Gimnázium 10. osztályos tanulója (tanárai Balázsné Zsigó Ágnes, Damásdi Gábor, Dobos Sándor és Kovács Benedek).

Kilenc versenyző az 1. feladat mellett egy másik feladatot is lényegében helyesen oldott meg. Ennek megfelelően

dicséretet érdemel

Czanik Pál, a Budapesti Fazekas Mihály Gyakorló Általános Iskola és Gimnázium érettségizett tanulója (tanárai Kocsis Szilveszter, Lenger Dániel, Dobos Sándor, Gyenes Zoltán, Hujter Bálint, Sándor András, Pósa Lajos, Nádor Benedek és Kovács Benedek),

Hajba Milán, a győri Révai Miklós Gimnázium és Kollégium 11. osztályos tanulója (tanárai Csete Lajos és Árki Tamás),

Holló Martin, a Budapesti Fazekas Mihály Gyakorló Általános Iskola és Gimnázium 12. osztályos tanulója (tanárai Hujter Bálint, Gyenes Zoltán, Kiss Géza, Dobos Sándor, Surányi László és Nagy Kartal),

Sánta Gergely, a Budapesti Fazekas Mihály Gyakorló Általános Iskola és Gimnázium 11. osztályos tanulója (tanárai Dobos Sándor, Lenger Dániel, Gyenes Zoltán és Pósa Lajos),

Sárdinecz Dóra, a Budapesti Fazekas Mihály Gyakorló Általános Iskola és Gimnázium 12. osztályos tanulója (tanárai Hujter Bálint, Gyenes Zoltán és Kiss Géza),

Sarusi-Kis Balázs, az ELTE Radnóti Miklós Gyakorló Gimnázium 12. osztályos tanulója (tanárai Steller Gábor, Kornai Júlia és Nagy Kartal),

Schmidt Botond, a budapesti Szent István Gimnázium 10. osztályos tanulója (tanárai Juhász István és Juhász Péter),

Varga Boldizsár, a Békásmegyeri Veres Péter Gimnázium érettségizett tanulója, aki jelenleg az ELTE TTK matematika szakos hallgatója (tanára Holló Gábor) és

Vödrös Dániel, a Budapesti Fazekas Mihály Gyakorló Általános Iskola és Gimnázium 11. osztályos tanulója (tanárai Dobos Sándor, Lenger Dániel, Pósa Lajos, Simon Péter, Gyenes Zoltán, Ádám Réka és Fazakas Tünde).

A versenybizottság ezúton köszöni meg minden versenyző, felkészítő tanár és a lebonyolításban közreműködő kolléga munkáját, valamint a Lovász Alapítvány pénzdíjakhoz nyújtott támogatását, a díjazottaknak pedig további sikereket kívánva gratulál.''

A 2025. évi Kürschák József Matematikai Tanulóverseny feladatainak megoldásai

1. feladat. Legyen \(\displaystyle n\) rögzített pozitív egész. Írjuk fel a \(\displaystyle 0, 1,\ldots, n-1\) számokat egy táblára valamilyen sorrendben. Két szám egymással inverzióban áll, ha a nagyobb megelőzi a kisebbet. Egy \(\displaystyle k\) számot nevezzünk sajátságosnak, ha pontosan \(\displaystyle k\) másikkal áll inverzióban. Legfeljebb hány sajátságos szám lehet a táblán?

Az 1. feladat 1. megoldása. Megmutatjuk, hogy egy \(\displaystyle k\) szám pontosan akkor sajátságos, ha az őt megelőző számok közül pontosan annyi \(\displaystyle k\)-nál kisebb van, mint ahány \(\displaystyle k\)-nál nagyobb. Egy \(\displaystyle k\) szám inverzióban áll

• azon \(\displaystyle k\)-nál kisebb számokkal, amik \(\displaystyle k\) után állnak a táblán, illetve
• azon \(\displaystyle k\)-nál nagyobb számokkal, amik \(\displaystyle k\) előtt állnak a táblán.

Az előbbiek számát jelölje \(\displaystyle x\). Ekkor \(\displaystyle k\) pontosan akkor sajátságos, ha az utóbbiak száma \(\displaystyle k-x\), ami viszont éppen azon \(\displaystyle k\)-nál kisebb számok száma, amik \(\displaystyle k\) előtt állnak a táblán.

Következésképp egy szám csak akkor lehet sajátságos, ha páros sok szám előzi meg a táblán (azaz páratlanadik pozícióban áll), így legfeljebb \(\displaystyle \lceil \frac{n}{2} \rceil\) db sajátságos szám állhat a táblán. Ennyi lehet is: tekintsük a

\(\displaystyle 0, \ast, 1, \ast, 2, \ast, \ldots \)

sorrendet, ahol a \(\displaystyle 2k+1\)-edik helyen a \(\displaystyle k\) szám áll \(\displaystyle k=0,1,\ldots, \lceil n/2 \rceil-1\) esetén, míg a \(\displaystyle \ast\)-gal jelölt páros pozíciókban bármilyen szám állhat, ami legalább \(\displaystyle \lceil n/2 \rceil\). Ekkor minden \(\displaystyle k \in \big \{ 0,1,\ldots, \lceil n/2 \rceil -1 \big\}\) sajátságos, mert \(\displaystyle k\) után nincs nála kisebb szám, az előtte lévő \(\displaystyle 2k\) szám közül pedig minden második nagyobb nála, így valóban pontosan \(\displaystyle k\) számmal áll inverzióban.

Az 1. feladat 2. megoldása. Megmutatjuk, hogy a táblán nem lehet két szomszédos sajátságos szám. Tegyük fel, hogy \(\displaystyle a\) és \(\displaystyle b\) szomszédos számok a táblán (\(\displaystyle ab\) vagy \(\displaystyle ba\) sorrendben). Legyen \(\displaystyle a<b\), és a többi számot osszuk három csoportba nagyság szerint: \(\displaystyle a\)-nál kisebbek (kicsik), \(\displaystyle a\) és \(\displaystyle b\) közöttiek (közepesek), valamint \(\displaystyle b\)-nél nagyobbak (nagyok). Jelölje az \(\displaystyle a,b\) előtt álló kicsi, közepes, illetve nagy számok számát rendre \(\displaystyle x_1\), \(\displaystyle y_1\), illetve \(\displaystyle z_1\). Hasonlóan, az \(\displaystyle a,b\) után álló kicsi, közepes, illetve nagy számok száma legyen \(\displaystyle x_2\), \(\displaystyle y_2\), illetve \(\displaystyle z_2\). Vegyük észre, hogy a közepes számok száma

\(\displaystyle y_1+y_2=b-a-1. \)

1. eset: \(\displaystyle ab\) sorrend. Ekkor \(\displaystyle a\) pontosan \(\displaystyle x_2+y_1+z_1\) számmal áll inverzióban, míg \(\displaystyle b\) pontosan \(\displaystyle x_2+y_2+z_1\) számmal. Ha \(\displaystyle a\) és \(\displaystyle b\) is sajátságos volna, akkor

\(\displaystyle b-a=(x_2+y_2+z_1)-(x_2+y_1+z_1)=y_2-y_1 \leq y_1+y_2=b-a-1, \)

ami ellentmondás.

2. eset: \(\displaystyle ba\) sorrend. Ebben az esetben \(\displaystyle a\) és \(\displaystyle b\) egymással is inverzióban áll, így \(\displaystyle a\) pontosan \(\displaystyle x_2+y_1+z_1+1\) számmal áll inverzióban, míg \(\displaystyle b\) pontosan \(\displaystyle x_2+y_2+z_1+1\) számmal. Ha tehát \(\displaystyle a\) és \(\displaystyle b\) is sajátságos volna, akkor

\(\displaystyle a-b=(x_2+y_1+z_1+1)-(x_2+y_2+z_1+1)=y_1-y_2 \leq y_1+y_2=a-b-1, \)

ami ellentmondás.

Ezt a gondolatmenetet esetszétválasztás és képletek nélkül is el lehet mondani: \(\displaystyle a\) és \(\displaystyle b\) szomszédos számokra tekintsük azokat a számokat, amik pontosan az egyikkel állnak inverzióban. Könnyen meggondolható, hogy ezek éppen a közepes számok, azaz \(\displaystyle b-a-1\) ilyen van. Tehát legfeljebb ennyiben térhet el \(\displaystyle a\) és \(\displaystyle b\) ``inverzió-száma''. Így nem lehet mindkettő sajátságos, különben ez az eltérés \(\displaystyle b-a\) volna.

Vagyis a sajátságos számok között nincsenek szomszédosak, így legfeljebb \(\displaystyle \lceil n/2 \rceil\) sajátságos szám lehet a táblán. Ennyi elő is fordulhat: tekintsük az

\(\displaystyle n-1, \ast, n-2, \ast, n-3, \ast, \ldots \)

sorrendet, ahol a \(\displaystyle \ast\)-gal jelölt páros pozíciókban bármilyen sorrendben állhatnak a maradék számok.

Az 1. feladat 3. megoldása. (Schmidt Botond megoldása alapján.) Egy táblán lévő \(\displaystyle k\) számra tekintsük a pozícióját (\(\displaystyle p\)), illetve a vele inverzióban álló számok számát (\(\displaystyle i\)). Azt állítjuk, hogy \(\displaystyle k+p+i\) mindig páratlan.

Ez nyilván teljesül, amikor a számok növekvő sorrendben vannak, hiszen ekkor \(\displaystyle p=k+1\) és \(\displaystyle i=0\). Most egy tetszőleges sorrend esetén vizsgáljuk, mi történik, ha két szomszédos számot megcserélünk. Ha nincs köztük \(\displaystyle k\), akkor persze \(\displaystyle p\) és \(\displaystyle i\) változatlanok maradnak. Ha az egyikük \(\displaystyle k\), akkor pedig mind \(\displaystyle p\), mind \(\displaystyle i\) pontosan \(\displaystyle 1\)-gyel változik, vagyis \(\displaystyle p+i\) paritása ismét változatlan. Mivel szomszédos számok megcserélésével bármilyen sorrendhez eljuthatunk, beláttuk, hogy \(\displaystyle k+p+i\) valóban mindig páratlan.

Ha \(\displaystyle k\) sajátságos, akkor \(\displaystyle i=k\), vagyis ekkor \(\displaystyle 2k+p\) páratlan, azaz ez csak páratlan \(\displaystyle p\) pozíciójú számokkal eshet meg.

Az 1. feladat 4. megoldása. (Molnár István Ádám megoldása alapján.) Jelölje \(\displaystyle \ell\) a táblán lévő utolsó számot. Ez a nála nagyobb számokkal áll inverzióban, azaz \(\displaystyle n-1-\ell\) számmal. Vagyis pontosan akkor sajátságos, ha \(\displaystyle n=2 \ell+1\). Vagyis ez csak páratlan \(\displaystyle n\) esetén következhet be.

Továbbá vegyük észre, hogy ha töröljük \(\displaystyle \ell\)-et a tábláról, valamint minden \(\displaystyle \ell\)-nél nagyobb számot \(\displaystyle 1\)-gyel csökkentünk, akkor a sajátságosság tulajdonsága nem változik: az \(\displaystyle \ell\)-nél kisebb számok inverzió-száma nem változik; egy \(\displaystyle \ell\)-nél nagyobb számé ugyan \(\displaystyle 1\)-gyel csökken, de maga a szám is ugyanígy változik.

Most vegyük az \(\displaystyle n\) szám egy tetszőleges sorrendjét. Minden lépésben az utolsó számot a fenti módon törölve elérjük, hogy végül üres legyen a tábla. Az eredeti sorrendben \(\displaystyle m\)-edik szám pontosan akkor sajátságos, ha \(\displaystyle n-m\) törlés után megmaradó \(\displaystyle m\) szám közül az utolsó sajátságos. Mint láttuk, ez az aktuálisan utolsó szám csak akkor lehet sajátságos, ha \(\displaystyle m\) páratlan. Ez azonnal mutatja, hogy csak a páratlan pozícióban álló számok lehetnek sajátságosak.

Ezzel a megközelítéssel az is könnyen átgondolható, milyen sorrendek esetén lesz minden páratlan pozícióban álló szám sajátságos.

2. feladat. Ebben a feladatban tízes számrendszerben felírt számokról lesz szó. Megengedünk nullával kezdődő felírásokat is. Egy páros sok számjegyből álló számot vághatónak nevezünk, ha két egyenlő hosszú részre félbevágva a részek összegének négyzete az eredeti szám. Például \(\displaystyle 2025=(20+25)^2\) és \(\displaystyle 0001=(00+01)^2\) négyjegyű vágható számok. Bizonyítsuk be, hogy a \(\displaystyle 2n\)-jegyű vágható pozitív egész számok száma minden \(\displaystyle n\)-re 2-hatvány.

A 2. feladat megoldása. Legyen \(\displaystyle q=99\dots9=10^n-1=q_1\cdots q_s\), ahol \(\displaystyle q_1\), ..., \(\displaystyle q_s\) egymáshoz páronként relatív prím prímhatványok. Legyen \(\displaystyle \varepsilon_i\in\{0,1\}\) \(\displaystyle (i=1, \dots, s)\); ez \(\displaystyle 2^s\) lehetőség. Az \(\displaystyle x\equiv \varepsilon _i\mod q_i\) \(\displaystyle (i=1, \dots, s)\) szimultán kongruenciarendszernek a kínai maradéktétel szerint pontosan egy \(\displaystyle x\) megoldása van az \(\displaystyle \{1, \dots, q\}\) halmazban, hiszen ez teljes maradékrendszer mod \(\displaystyle q_1\cdots q_s\). Ekkor \(\displaystyle x^2\) egy \(\displaystyle 2n\)-jegyű vágható pozitív egész szám. Valóban, legyen \(\displaystyle x^2=10^nu+v\), ahol \(\displaystyle u,v\in\{0,\dots, q\}\). Ekkor \(\displaystyle u<x\), emiatt \(\displaystyle x-q\le0< u+v<x+q\), továbbá \(\displaystyle u+v\equiv (q+1)u+v=x^2\equiv \varepsilon_i^2=\varepsilon_i\equiv x\mod q_i\) minden \(\displaystyle i\)-re, ahonnan \(\displaystyle u+v\equiv x\mod q\); emiatt \(\displaystyle u+v=x\).

Minden \(\displaystyle 2n\)-jegyű vágható pozitív egész számot pontosan egyszer kapunk meg a fenti eljárással. Valóban, ha legalább egy \(\displaystyle \varepsilon_i\) értékét megváltoztatjuk, akkor \(\displaystyle x\) és így \(\displaystyle x^2\) is megváltozik. Másrészt, ha \(\displaystyle 10^nu+v=(u+v)^2\) egy \(\displaystyle 2n\)-jegyű vágható pozitív egész szám, akkor legyen \(\displaystyle x=u+v\in\{1, \dots, q\}\). Ekkor \(\displaystyle x(x-1)=x^2-x=qu\), de \(\displaystyle x\) és \(\displaystyle x-1\) relatív prímek, így minden \(\displaystyle i\)-re \(\displaystyle x\) vagy \(\displaystyle x-1\) osztható \(\displaystyle q_i\)-vel.

Mindezek alapján a \(\displaystyle 2n\)-jegyű vágható pozitív egész számok száma \(\displaystyle 2^s\).

3. feladat. Adott \(\displaystyle n\ge 10\) pont a síkon, nincs három egy egyenesen. Bizonyítsuk be, hogy ki lehet őket színezni pirossal és kékkel úgy, hogy minden félsík, ami legalább \(\displaystyle 10\) pontot tartalmaz, tartalmaz piros és kék pontot is.

A 3. feladat 1. megoldása. Megmutatjuk, hogy az állítás \(\displaystyle 10\) helyett \(\displaystyle 3\)-mal is teljesül. Világos, hogy elég a pontosan három pontot levágó félsíkokról igazolni, hogy piros és kék pontot is tartalmaznak. Tekintsük a megadott pontok konvex burkának csúcsait, és vegyük ezen csúcsok egy olyan, tartalmazásra nézve minimális \(\displaystyle P\) részhalmazát, ami az összes, félsíkkal levágható ponthármasból legalább egy pontot tartalmaz. (Mivel minden levágható ponthármas tartalmazza a konvex buroknak legalább egy csúcsát, ezért bizonyosan létezik ilyen \(\displaystyle P\) részhalmaz.) Színezzük a \(\displaystyle P\)-beli pontokat pirosra, az összes többit pedig kékre.

Most vágjunk le \(\displaystyle 3\) pontot egy félsíkkal. A \(\displaystyle P\) választása miatt a levágott \(\displaystyle 3\) pont között van piros. Indirekt tegyük fel, hogy mind a három levágott pont piros. Ekkor e három pont mindegyike a konvex burok egy-egy csúcsa. Figyeljük meg, hogy e három piros pont közül a középsőt kékre átszínezve továbbra is igaz lesz, hogy minden levágható ponthármas tartalmaz piros pontot. Ez ellentmond a \(\displaystyle P\) halmaz minimalitásának. Tehát a levágott három pont között kéknek is kell lennie, és ezzel a bizonyítást befejeztük.

A 3. feladat 2. megoldása. Ez a megoldás \(\displaystyle 10\) helyett \(\displaystyle 5\)-tel bizonyítja be az állítást. Sorszámozzuk meg a konvex burok csúcsait körbe (\(\displaystyle 1\)-essel kezdve). Színezzük ki a konvex burok csúcsait pirosra, a konvex burok belsejébe eső pontokat pedig kékre. Ez majdnem jó: csak az olyan, félsíkkal levágható \(\displaystyle 5\)-ösökkel lehet gond, amelyek a konvex burok \(\displaystyle 5\) egymást követő csúcsából állnak. Minden ilyen esetben színezzünk át kékre egy olyan páros indexű csúcsot, ami nem az első és nem az utolsó a levágott \(\displaystyle 5\) csúcs közül. A konvex burok kékre színezett csúcsai tehát rendelkeznek azzal a tulajdonsággal, hogy a konvex burok tetszőleges kék csúcsa és a vele szomszédos piros csúcsok alkotta háromszög belsejébe nem esik pontja a vizsgált halmaznak. Ezért ha egy félsík úgy vág le legalább két pontot a ponthalmazból, hogy az egyik levágott pont a konvex burok kék csúcsa, akkor e kék csúcs valamelyik piros szomszédját is le kell vágnia.

Most vágjunk le \(\displaystyle 5\) pontot egy félsíkkal. Ha mind az \(\displaystyle 5\) levágott pont a konvex burok csúcsa, akkor világos, hogy van köztük legalább egy páratlan indexű (ami biztosan piros) és van legalább egy kékre színezett páros indexű is. Ha a levágott pontok között van olyan is, ami a konvex burok belsejébe esik, akkor az nyilván kék. Ha a konvex buroknak legalább két csúcsát vágtuk le, akkor nem lehet ezek mindegyike kék, hiszen a páratlan indexű közülük piros. Ha pedig csak egy kék csúcsot vágtunk le a konvex burokról, akkor levágtunk \(\displaystyle 4\) kék pontot is a konvex burok belsejéből. Ekkor azonban a levágott konvex burok csúcs nem lehet kék a fenti megfigyelésünk miatt. Mivel minden esetet megvizsgáltunk, az állítást beláttuk.