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 magyar‐izraeli matematikaverseny 1994 márciusában ötödször került megrendezésre, ezúttal Izraelben, a Weizmann Intézetben. A magyar csapat tagjai: Csörnyei Marianna, Futó Gábor, Koblinger Egmont és Párniczky Benedek voltak, valamennyien a Fővárosi Fazekas Mihály Gyakorló Gimnázium tanulói, Koblinger III. osztályos, a többiek IV. osztályosak. A magyar csapat vezetője Pelikán József (Eötös Loránd Tudományegyetem, Budapest) volt. Az izraeli csapat tagjai Maxim Iorsh, Chagai Shkolnikov, Lior Silberman és David Yeger voltak, vezetőjük Shay Guéron (Technion, Haifa) volt. A verseny szokásos ─ más versenyektől némileg eltérő ‐ módon zajlott. Az első versenynapon minden versenyzőnek 4 feladatot kellett 4 óra alatt megoldania. Minden feladat helyes megoldásáért 7 pont járt, az egy versenyző által elérhető maximális pontszám tehát 28 volt. (A feladatokat alább ismertetjük.) Ez tehát hagyományos típusú versenynap volt. A második versenynapon viszont csapatverseny volt: mindkét csapatnak előre meghatározott témából 5 feladatot kellett megoldania. Az előre meghatározott ─ évenként változó ─ téma idén algoritmusok, elsősorban gráfalgoritmusok vizsgálata volt. Erről a témáról a KöMaL olvasóinak egy igen jó magyar nyelvű bevezető tankönyvet ajánlhatók: Gács‐Lovász: Algoritmusok (Tankönyvkiadó, 1987.). Hogy a két csapat tagjainak azonos előismereteket biztosítsunk, az izraeli csapatvezetővel abban állapodtunk meg, hogy mindkét csapat tagjai Sedgewick: Algorithms (Addison‐Wesley, 1988.) című, angol nyelvű könyvét használhatják a felkészüléshez. (A csapatverseny feladatai a cikk végén olvashatók.) Hagyomány már, hogy a csapatversenyen nem hirdetünk formálisan eredményt, hanem mindkét csapat teljesítményét szóban értékeljük. Az egyéni versenyben Csörnyei és Futó 28 pontot, Koblinger 27 pontot, Párniczky pedig 23 pontot szerzett. Az izraeli csapatból Iorsh 14, Shkolnikov 12, Yeger 7, Silberman pedig 6 pontot ért el. A magyar csapat összpontszáma tehát a lehetséges 112 pontból 106, az izraelié 39 pont volt. A csapatversenyben a magyarok kifogástalanul megoldották a 2., 3. és 4. feladatot, az 1. feladatban a kívánt állításnál valamivel gyengébb állítást bizonyítottak, az 5. feladatot pedig részben oldották meg. Az izraeliek megoldották a 3. feladatot, az 1. és 5. feladatban pedig kezdeti lépésekig jutottak. Abban, hogy a csapatot a középiskolai tananyagtól távolabb eső ,,Algoritmusok'' témakörből jól felkészíthessük és a versenyre megfelelő nehézségű és érdekes feladatokat találjunk, több, itthon és külföldön dolgozó kollégám, barátom segített: Babai László, Elekes György, Friedl Katalin, Lovász László, Seress Ákos és Tardos Éva. Valamennyiük segítségét szeretném megköszönni. Ugyancsak köszönet illeti izraeli vendéglátóinkat, akik kellemes körülményeket és programokat biztosítottak (galileai, jeruzsálemi kirándulás, múzeumlátogatások, stb.), külön megemlítve a Weizmann Intézetben dolgozó régi barátunkat, a Debrecenből származó Feldman Lajost (Joel Feldman). Mindenekelőtt azonban Reiman Istvánnak (Budapesti Műszaki Egyetem) kell köszönetet mondanom, aki, mint sok éve mindig, idén is a csapat és a tágabb olimpiai keret felkészítésének fáradságos és időigényes munkáját végezte.
Az egyéni verseny feladatai 1. Legyen és két különböző pozitív egész szám. Bizonyítsuk be, hogy létezik olyan valós szám, amire
(Itt az valós szám törtrészét jelenti, vagyis .) 2. Legyenek pozitív számok . Rögzítsük az értékeket. Hogyan kell megválasztanunk az számokat, hogy az
összeg minimális legyen ? 3. Három egyenlő sugarú kör egy közös ponton megy át, további, páronként vett metszéspontjaik . A három kört magába foglalja az háromszög, amelynek oldalai rendre érintenek kettőt-kettőt az adott körök közül. Bizonyítsuk be, hogy
4. Nevezzünk ,,‐-társaság''-nak egy lányból és fiúból álló társaságot. Bizonyítsuk be, hogy léteznek olyan számok, hogy minden ‐ társaságban található 5 lány és 5 fiú úgy, hogy közülük mindegyik lány ismeri mindegyik fiút, vagy pedig található 5 lány és 5 fiú úgy, hogy közülük semelyik lány sem ismeri semelyik fiút sem.
A csapatverseny feladatai 1. Legyen egy irányítatlan gráf; a csúcsok, az élek halmaza. Legyen egy függvény, amely egy ,,súly''-nak nevezett valós értéket rendel minden élhez. Élek egy nem-üres halmazának max-súlya alatt a benne szereplő élek súlyainak maximumát értjük. Tegyük fel, hogy összefüggő. Keressünk lépésben olyan feszítőfát, amelynek max-súlya minimális. (Egy lépésben elvégezhető két valós szám összehasonlítása és a megfelelő ,,pointer administration'' (nyilvántartás).) 2. összefüggő, irányítatlan gráf, egy súlyfüggvény, pedig egy rögzített éle. Döntsük el lépésben , hogy létezik-e minimális súlyösszegű feszítőfa, amely -t tartalmazza. Megjegyzés: Gráfok mindig szomszédsági listával vannak megadva: minden csúcshoz adott szomszédainak listája. 3. Adott egy irányított gráf, egy kitüntetett csúcs (a ,,forrás''), egy függvény, amely minden élhez egy pozitív súlyt rendel és egy függvény. Valaki azt állítja, hogy minden csúcsra az irányított utak súlyösszegeinek minimuma. Döntsük el lépésben, igaz-e ez az állítás. (; egy lépésben elvégezhető egy aritmetikai művelet, vagy két valós szám összehasonlítása, továbbá a megfelelő ,,pointer administration'' (nyilvántartás).) 4. -reguláris gráfon olyan (irányítatlan) gráfot értünk, amelyben minden pont foka . a) Mutassuk meg, hogy minden 3-reguláris gráf élhalmaza két , részre bontható úgy, hogy a és gráfok mindegyikében minden pont foka legfeljebb 2. b) Határozzunk meg ilyen , -t, időben . c) Egy gráf éleinek színezése akkor jó, ha közös végpontú élek színe mindig különböző. Adjunk meg idejű algoritmust egy 3-reguláris gráf éleinek 4 színnel való jó színezésére. 5. Legyenek ismeretlen számok. Meg akarjuk határozni -t (vagyis az -k között a -ek számának paritását). ,,Lineáris kérdés''-eket tehetünk fel. Egy lineáris kérdés valós szám: megadásából áll. A válasz egy ilyen kérdésre ,,IGEN'', ha
egyébként ,,NEM''. Bizonyítsuk be, hogy ha van olyan stratégiánk, ami biztosan megállapítja -t legfeljebb db lineáris kérdés segítségével (bármi volt is ), akkor (2 alapú logaritmus). Megjegyzés. Stratégiánk determinisztikus: következő kérdésünk az addigi kérdésekre adott válaszok függvénye.
|