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. Ez év március 29. és április 5. között került sor, ezúttal Budapesten, immár a tizenkettedik alkalommal az izraeli és magyar diákok közötti matematikaversenyre. A két országot, most először, hattagú csapatok képviselték. A magyar csapat tagjai a következők voltak:
Csikvári Péter | 11. évf. | (Fővárosi Fazekas Mihály Gyakorló Gimnázium); | Csóka Endre | 10. évf. | (Fazekas Mihály Gimnázium, Debrecen); | Harangi Viktor | 11. évf. | (Fővárosi Fazekas Mihály Gyakorló Gimnázium); | Horváth Illés | 11. évf. | (Fővárosi Fazekas Mihály Gyakorló Gimnázium); | Vizer Tibor | 12. évf. | (Révai Miklós Gimnázium, Győr); | Vörös László | 12. évf. | (Piarista Gimnázium, Kecskemét). |
A verseny első két napján a Nemzetközi Matematikai Diákolimpiák lebonyolítása szerint három-három feladattal kellett megbirkózniuk a versenyzőknek. Mindkét napon 4,5 óra gondolkodási idő állt rendelkezésre és az egyes feladatok kifogástalan megoldásával 7-7 pontot lehetett szerezni. A feladatsor meglehetősen nehéznek bizonyult, a legnehezebb, hatodik feladatra nem érkezett teljes megoldás. A legjobb eredményt Ran Tessler izraeli diák érte el 38 ponttal. A magyar versenyzők teljesítménye a következőképpen alakult: Csóka Endre: 37 pont; Csikvári Péter: 31 pont; Harangi Viktor: 30 pont; Vörös László: 27 pont; Horváth Illés: 12 pont; Vizer Tibor: 11 pont. Bár a verseny egyéni volt, természetesen kiszámoltuk a két csapat összpontszámát: eszerint, akárcsak az egyéni versenyben, a vendégek egyetlen ponttal bár, de megelőzték a magyar csapatot. A harmadik napon a hagyományos csapatversenyre került sor. A téma, amit egy hónappal korábban megkaptak a felkészülő diákok, a verseny magyar névadója, Turán Pál tiszteletére a következő volt: Extremális gráfok és Turán típusú tételek. A csapatverseny feladatsorát Simonovits Miklós, a Rényi Alfréd Matematikai Kutatóintézet tudományos tanácsadója állította össze. A kitűnően felkészült csapatok lényegében valamennyi feladatot megoldották. Az utolsó oldalon a versenyen készült fényképek láthatók. A továbbiakban a verseny magyar résztvevőinek beszámolóját közöljük: hogyan látták ők ezt a néhány napot.
A budapesti Lauder Javne iskola volt a vendéglátója az idei találkozónak, amely szokás szerint a kétnapos egyéni versennyel kezdődött 2001. március 30-án, pénteken. Külön kihívás volt számunkra, hogy a sabbath, a zsidó szombat miatt a második versenynapot csak naplemente után kezdhettük. Így mi este 6 órakor, az izraeliek pedig 8-kor vágtak neki a 4 és fél órás versenynek. Meglehetősen nehéz volt végig koncentrálni. Másnap a kiránduláson pihenhettük ki a fáradalmakat. Fogaskerekűvel felmentünk a János-hegyre, ahol a kilátóból megcsodálhattuk Budapest látképét, majd lelibegőztünk. Ekkor adódott először lehetőségünk arra, hogy megismerkedjünk az izraeli diákokkal. A hétfői csapatverseny kellemes légkörben telt el ‐ ennek az eredménye ugyanis nem számított bele a két egyéni dolgozat értékelésébe. A feladatok is könnyebbnek bizonyultak, csupán a 2. feladatot nem oldotta meg az összes csapat. Kedden délelőtt két előadást hallgattunk meg angol nyelven; az izraeliek kísérőtanárát, majd Simonovits Miklóst, a csapatverseny feladatainak összeállítóját. Ezután a díszebéden belekóstolhattunk a kóser konyhaművészetbe. Lehetőségünk nyílt közös játékra is, és tapasztalhattuk, hogy Izraelben is igen népszerű a foci. A folytatásban T. Sós Vera és Tardos Gábor adott elő a Lauder iskola csodálatosan felszerelt multimédia termében. Mindketten a matematika egymástól távol eső területeinek meglepő kapcsolatáról beszéltek. Végül megnéztünk egy angol nyelvű, Erdős Pálról szóló dokumentumfilmet. Az utolsó napon a búcsúünnepségen tudtuk meg, hogy összesítésben egy ponttal kikaptunk. Nem baj, majd a diákolimpián
Csikvári Péter, Gerencsér Balázs, Harangi Viktor, Horváth Illés |
Fazekas M. Főv. Gyak. Gimn., 11. o.t. |
12. Gillis‐Turán Matematikaverseny, 2001 tavaszán Első nap
1. Keressünk olyan pozitív egész , , számokat, amelyekre továbbá, amelyekre teljesül, hogy .
2. Adottak az egyenesen az , , és pontok ebben a sorrendben. Mi azon pontok mértani helye a síkban, amelyekre az és a szögek egyenlők?
3. Határozzuk meg azokat a folytonos függvényeket, amelyekre minden valós számra
4. . Adjunk meg olyan harmadfokú polinomot, amelynek a gyökei a gyökeinek az ötödik hatványai.
5. Az háromszög beírt körének középpontja , és az , illetve az oldalak felezőpontjai. A és egyenesek -ben és -ben metszik -t, illetve -t. Tudjuk, hogy az és az háromszögek területe egyenlő. Mekkora a szög?
6. Adott pozitív egész úgy, hogy egyikük sem nagyobb -nál, az összegük pedig . Bizonyítsuk be, hogy két egyenlő összegű csoportba rendezhetők.
Az alábbi feladatokban mindig -pontú egyszerű (többszörös élek nélküli, hurokél mentes) gráf, pedig az -pontú teljes gráf. a éleinek a számát jelöli.
1. Bizonyítsuk be, hogy ha éleit színnel színezzük úgy, hogy minden szín ténylegesen előfordul, akkor az így kapott színezett gráf tartalmaz olyan háromszöget, amelynek élei különböző színűek.
2. Bizonyítsuk be, hogy ha akkor tartalmaz két olyan háromszöget, amelyeknek egyetlen közös csúcsa van.
3. Bizonyítsuk be, hogy ha akkor tartalmaz hosszúságú kört.
4. a) Jelölje azt a teljes páros gráfot, amelynek fekete és fehér csúcsa van. Bizonyítsuk be, hogy ha nem tartalmazza -at, akkor b) Bizonyítsuk be, hogy ha adott pont a síkon, akkor a köztük fellépő távolságok közül legfeljebb lehet egységnyi hosszú.
5. Legyen adott prím és tekintsük az egész számpárokat . Készítsük el azt a gráfot, amelynek csúcsai ezek a párok, és két csúcs, és között pontosan akkor halad él, ha Az ily módon esetleg létrejövő hurokéleket hagyjuk el a gráfból. a) Bizonyítsuk be, hogy az így kapott gráf nem tartalmaz hosszúságú kört. b) Bizonyítsuk be, hogy az végtelen sok értékére létezik olyan gráf, amelyiknek legalább éle van és nem tartalmaz hosszúságú kört.
Az alábbiakban közöljük a verseny legnehezebb feladatának a megoldását.
6. Adott pozitív egész úgy, hogy egyikük sem nagyobb -nál, az összegük pedig . Bizonyítsuk be, hogy két egyenlő összegű csoportba rendezhetők.
Megoldás. Az állítás bizonyítását több segédtételre bontjuk. A bizonyítás során föltesszük, hogy az adott számok, , , , nagyság szerint növekvő sorba vannak rendezve.
1. Lemma. Ha a pozitív egész számokból álló sorozatra teljesül, hogy minden esetén, akkor a sorozat ,,univerzális", azaz minden 1 és közötti pozitív egész előáll az különböző elemeinek az összegeként. A lemma állítása többé-kevésbé ebben a formában az 1960. évi Kürschák verseny 2. feladata volt, és azóta lényegében közismertté vált. A bizonyítás teljes indukcióval történhet, és megtalálható Hajós György‐Neukomm Gyula‐Surányi János: Matematikai Versenytételek II. című alapvető művében. (Tankönyvkiadó, Budapest, 1988) Ha a sorozat részletösszegei helyett a sorozat tagjait vizsgáljuk, akkor az alábbi, könnyebben kezelhető elégséges feltételt kapjuk: Ha teljesül minden esetén, akkor az sorozat univerzális. A bizonyítás nyilvánvaló, és ahogyan például az egyik legismertebb univerzális sorozat, a 2-hatványok sorozata mutatja, a feltétel valóban csupán elégséges.
2. Lemma. Ezt a lemmát is általános alakban mondjuk ki, mert ebben a formában a paraméterek különböző értékeire is felhasználjuk majd a bizonyítás során. Ha adott darab növekvően elrendezett pozitív egész szám, amelyek összegére (ez most nyilván teljesül, hiszen ) akkor a sorozatra teljesül , ha . (Az adott intervallum akkor nem üres, ha , de ez most nyilván teljesül.) Ez azt jelenti, hogy az 1. Lemma következményeként adódó feltétel csak a sorozat kezdetén és végén sérülhet.
Bizonyítás. Az alábbi becslés nyilvánvaló: | | (1) | és így | | (*) | Eszerint az egyenlőtlenségből következik az feltétel. Ez utóbbi pedig egyenértékű a másodfokú egyenlőtlenséggel. Mivel , ami a feltétel () szerint valóban negatív, a lemma állítását igazoltuk.
Megjegyzés. Érdemes felfigyelni arra, hogy a (2) egyenlőtlenség szerint a növekvő módon elrendezett sorozatban az -dik, középső tagra szimmetrikusan sérülhet az feltétel.
3. Lemma. Ha (a korábbi jelölésekkel) , és az első tag univerzális sorozatot alkot, akkor előáll a sorozat néhány elemének az összegeként.
Bizonyítás. Mivel és , ezért bármely pozitív egész előáll ebben az intervallumban. Térjünk most rá a feladat állításának a bizonyítására. Ha a sorozat ,,alacsony értékekkel kezdődik'', azaz már az első elemtől kezdve univerzális, vagyis és , akkor a 2. lemma szerint az első szám univerzális sorozatot alkot, és így a 3. lemma szerint készen vagyunk. Ha nem ez a helyzet, akkor . Mivel láttuk, hogy , ha , mindenképpen teljesül, hogy . Az elemek rendezése miatt így . Két esetet különböztetünk meg aszerint, hogy értéke 2 vagy pedig 3. 1. eset: . Az feltételből most miatt következik, hogy . Ismét a 2. lemmát alkalmazzuk. Tegyük félre a két darab 2-est, és rendezzük a sorozat páratlan értékű tagjait tetszőlegesen párokba. Ez most megtehető, hiszen a számok összege páros. Így legalább páros számot kapunk. Most , tehát ebben az esetben az eredeti sorozat bármely két tagjának az összege kisebb vagy egyenlő, mint 60. Felezzük meg a két darab 2-essel együtt összesen darab páros számot! Így az sorozatot kapjuk, amelyre . Erre a ,,felezett'' sorozatra még mindig teljesül, hogy , tehát a 2. lemma szerint , ha , és mivel , a 3. lemma felhasználásával következik, hogy a sorozat elemeiből előállítható a 30. Ez pedig, 2-vel szorozva, a 60 előállítását adja az sorozat elemeiből. 2. eset: . Láttuk, hogy , ezért most . Az előző trükk most is működik: megmutatjuk, hogy a 3-asokat félretéve a megmaradó számok elegendően sok 3-mal osztható összegű csoportba rendezhetők. Most , tehát a sorozat bármely három tagjának az összege kisebb 60-nál. Az előbbi trükk szerint tegyünk félre két darab 3-ast ‐ láttuk, hogy most van legalább ennyi. A megmaradó 30 szám összege osztható 3-mal, és így legalább csoportba rendezhetők (egyesével, kettesével, illetve hármasával) úgy, hogy a csoportok összege 60-nál kisebb, 3-mal osztható szám. Az így adódó darab számot (a két darab félretett 3-assal együtt) 3-mal elosztva az alábbi sorozatot kapjuk: | | Készen vagyunk, hiszen most is , így a , , , univerzális, tehát a 3. lemma szerint előállítható az elemeiből.
Megjegyzések. 1. Szó szerint ugyanígy igazolható, hogy ha adott darab szám, amelyek összege és egyikük sem nagyobb, mint , akkor ezek a számok két egyenlő összegű csoportra oszthatók. (A feladatban , , .) Az is látható, hogy az állítás éles, két példa is mutatja, hogy darab számra ez már nem feltétlenül tehető meg. Könnyen bizonyítható, hogy bárhogyan osztjuk is két csoportra az alábbi számokat, a csoportokban sosem lehet egyenlő a számok összege. | |
2. A feladat egy némileg általánosabb probléma ‐ talán legnehezebb ‐ részfeladata. Az általános kérdés a következő: milyen feltétel biztosítja, hogy egy összegű elemű halmaz két egyenlő összegű csoportra legyen felbontható (a nyilvánvalóan szükséges feltételen kívül.) Azonnal adódik, hogy ha az páratlan, akkor ez soha nem tehető meg. Ha páros, de nem osztható 4-gyel, akkor azt kapjuk, hogy a kritikus elemszám . Ha osztható 4-gyel, de nem osztható 3-mal, akkor ez , a versenyen kitűzött feladat pedig lényegében annak az esetnek a vizsgálata volt, amikor osztható 3-mal is és 4-gyel is. Ilyenkor a legalacsonyabb a kritikus elemszám, . Az olvasó könnyen találhat példákat, hogy az egyes esetekben megadott értékek valóban élesek és a fenti bizonyítás elemeit felhasználva maga is igazolhatja a kimondott állításokat. 3. A feladat egy természetesen adódó algoritmus elemzésével is megoldható, pontosabban úgy is eljuthatunk az alapvető 2. lemma egy változatához. Sajnos ez sem intézi el az idegesítő esetet, így a ,felezési', illetve ,harmadolási' trükk nem látszik elkerülhetőnek. Az algoritmus leírásakor természetesebben hangzik, ha a feladat szövegét némileg átalakítjuk: a számokról mint súlyokról beszélünk majd ‐ tekintsük őket mondjuk grammokban adott mérőszámoknak ‐, a feladat pedig azt követeli meg, hogy ezeket a súlyokat két, egyenlő tömegű csoportra osszuk, ha úgy tetszik, egy mérleg két serpenyőjében rendezve el őket. Tekintsük tehát a súlyok növekvően elrendezett sorozatát, és tegyünk a mérleg két serpenyőjébe egy-egy zárt tartályt, amelyekbe pontosan grammnyi tömeg fér. A legnehezebbikkel kezdve helyezzük el a súlyokat egyesével a tartályokban, az éppen sorra kerülőt a könnyebbik (nem nehezebbik) serpenyőbe téve. Ha elakadunk, azaz a soron következő súly egyik tartályban sem fér el, akkor megállunk. Ha ez a kiegyensúlyozó algoritmus úgy ér véget, hogy valamennyi súlyt sikerült elhelyeznünk, akkor nyilván megvalósítottuk a kívánt felosztást. Nézzük, mi történik, ha elakadás nélkül sikerült elhelyeznünk az -nél nem könnyebb súlyokat. Ha a két tartály tartalmát ebben az állapotban és jelöli ( nyilván föltehető), akkor nyilván . Ha most , akkor az súly is elfér, az eljárás tehát nem akad el. Ez biztosan teljesül, ha . Vegyük észre az 1-est a jobb oldalon, ez azért illeszthető ide, mert egész számokkal dolgozunk. Ez viszont nem egyéb, mint ‐ ismerős? ‐ így ha | | akkor a kiegyensúlyozó algoritmus lépéseivel akadálytalanul elhelyezhetők az súlyok! A Kürschák-feladat feltétele ebben az értelmezésben az algoritmus sikeres lefutását biztosítja! Vegyük észre, hogy mivel a nagy súlyok a feltétel szerint nem nagyobbak -nél, az algoritmust el tudjuk indítani. Ezzel becsatlakoztunk a fenti megoldásba, hiszen ott láttuk, hogy -ból következik , ami most elégséges ahhoz, hogy sikeresen lefusson az algoritmus. Az kis kezdőértékek most azt jelentik, hogy amikor elértünk -hoz, akkor ezután az eljárás befejezhető. Ebben a változatban nincs szükség az egyébként triviális 3. lemmára, a megoldás csak azon múlik, hogy jól kezdődik-e a sorozat (akkor végződik jól az algoritmus). Ebben a változatban a megoldás valamivel egyszerűbbé vált, aminek az lehet az oka, hogy itt kizárólag a kiegyensúlyozásra törekszünk, nem foglalkozunk azzal, hogy egyébként milyen számok állíthatók elő a megadott sorozat segítségével.
|