Erdős Pál Emlékverseny

A verseny véget ért. Az első öt helyezett a következő:

1. Bakos Balázs 13.A, 125 pont

2. Mezei Adrián 13.A, 117 pont

3. Kudlik László 13.A, 96 pont

4. Székely Ákos 11.D, 93 pont

5. Reisz Fanni 11.A, 70 pont

A Karinthy Frigyes Gimnázium matematika tanárainak munkaközössége versenyt rendez érdeklődő tanulóink számára. A verseny jól szolgálja az egyéb versenyekre való felkészülést, az érettségin való minél eredményesebb szereplést. A versenyen minden héten két feladatot tűzünk ki, amelyeket nagyjából azonos nehézségűnek tervezünk. Egy feladat hibátlan megoldása 4 pontot ér. 32 pont elérése után a versenyző elveszít 32 pontot (létraverseny), és tanára díjazza az elért eredményt (ötös,dicséret, egyéb elismerés). Így bárki bármikor bekapcsolódhat a versenybe, az elismerés mindenki számára elérhető lehet.

A feladatok megoldásait mindig a megadott határidőig, A4-es lapon, névvel, osztállyal megjelölve kell beadni a 44-es teremben. A verseny október első hetében indul, és április közepéig tart.

18. (utolsó) forduló
Beadási határidő: 2013. április 4. csütörtök

Itt az ideje, hogy végre felfedjük, miért is Erdős Pál volt versenyünk névadója. Erdős Pál a huszadik század talán legnagyobb matematikusa, s ezt talán senki hozzáértő nem is vitatja. Erdős 1913. március 26-án született Budapesten, és éppen a tavaszi szünet idején ünnepelhetjük születésének 100. évfordulóját. A versennyel egyéb fontos tanítási célok mellett  erre akartuk felhívni a figyelmet.

Erdős  kutatásainak középpontjában a matematika két – laikusoknak is érthetően elmagyarázható – fejezete állt: a számelmélet és a kombinatorika. Több mint 1000 tudományos cikkét lehetetlen röviden összefoglalni, de mégis teszünk egy halvány kísérletet legalább két tételének ismertetésével.

1.   Tudjuk, hogy a prímszámok eloszlására nincsen effektív képlet, azaz olyan formula, hogy abba behelyettesítve n-et, megkapjuk az n-edik prímszámot. Ezért már régóta próbáltak olyan összefüggést keresni, amely legalább becslést ad  egy adott n értékig a prímszámok számára. Végül 1896-ban egymástól függetlenül J. Hadamard francia és Ch.de la Vallée-Poussin belga matematikusoknak komplex-függvénytani eszközökkel sikerült a jelenleg is legjobb becslést, az úgynevezett prímszámtételt, bizonyítaniuk. Ennek legemészthetőbb alakja a következő: Jelölje az x-nél nem nagyobb pozitív prímszámok számát  . Ekkor  ,ahol    jelenti, hogy    tart 0-hoz, ha x minden határon túl nő. Erdős Pál 1949-ben bizonyította a tételt elemi eszközökkel, ami nem egyszerűt jelent, hanem csak azt, hogy nem használ komplex függvénytant a bizonyításhoz. Ez a bizonyítás magyarázatokkal megtalálható a Matematikai Lapok 1972. évi 1-2. számában a 31-51. oldalon Hoffmann György és Surányi László tollából.

2.   Talán kevesekben tudatosult, hogy a gráfelmélet a kombinatorika egy gazdag és tartalmas fejezete, hiszen a kombinatorika legegyszerűbb meghatározása: a véges halmazok elmélete. A gráfelmélet egyik gyönyörű problémaköre a Ramsey-tétel és az ezzel  kapcsolatos problémák. Ramsey tétele kimondja, hogy bármely k és m természetes számokhoz létezik olyan f egész szám, hogy bármely legalább f-pontú G gráfra igaz a következő állítás:  vagy G tartalmaz k-pontú teljes részgráfot, vagy G komplementere tartalmaz m-pontú teljes részgráfot. A legkisebb ilyen f egész számot jelöljük f(k,m)-mel. f(k,m) kiszámítása már kis k és m számokra is bonyolult. Könnyen belátható, hogy f(1, m)=f(k,1)=1, illetve f(2,m)=m, f(k,2)=k. Eddig sikerült meghatározni a következő értékeket: f(3,3)=6, f(3,4)=9, f(3.5)=14, f(4,4)=18, f(3,6)=18. Erdősnek sikerült a következő becslést adnia  általánosan:

Erdős-Szekeres(György) –tétel

Legyenek k,m  >= 1 egész számok, és legyen G  -pontú gráf. Ekkor vagy G tartalmaz k-pontú teljes részgráfot, vagy G komplementere tartalmaz m-pontú teljes részgráfot.

Mindezek után lássuk az utolsó forduló feladatait, amelyek közül az első Erdős egyik kedvenc feladata volt, de a második is kapcsolódik munkásságához.

1.feladat

Adottak az 1, 2,…, 2n-1, 2n egész számok. Bizonyítsuk be, hogy akárhogyan választunk ki közülük n+1-et, a kiválasztottak között lesz két olyan szám, amelyekre igaz, hogy az egyik osztója a másiknak.

2.feladat

Egy X halmaz bizonyos részhalmazaiból álló H  halmazrendszert szűrőnek nevezünk, ha

1. Az üres halmaz nem eleme H-nak 

2. A, B ϵ H esetén A ∩ B ϵ H

3. Ha A ϵ H ás A része B-nek, akkor B ϵ H

Egy  szűrőt X-en ultraszűrőnek nevezünk, ha nincs másik olyan szűrő, amelyik tartalmazza .

a)      Hány szűrője van X-nek, ha X 5 elemű? Mi a helyzet, ha n eleme van?

b)      Hány ultraszűrő van X-en, ha X 5 elemű? És ha n elemű?