Kezdőlap


Cím:	Beszámoló a 12. Gillis-Turán matematikaversenyről
Füzet:	2001/május, 274 - 281. oldal	PDF \| MathML
Témakör(ök):	Egyéb (KöMaL pontverseny is)

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

x

y

z

számokat, amelyekre

\begin{matrix} 2000 x^{2} + y^{2} = 2001 z^{2}, \end{matrix}

továbbá, amelyekre teljesül, hogy

x > z > 1999 \cdot 2000 \cdot 2001 > y

2. Adottak az

e

egyenesen az

A

B

C

és

D

pontok ebben a sorrendben. Mi azon

P

pontok mértani helye a síkban, amelyekre az

A P B

és a

C P D

szögek egyenlők?

3. Határozzuk meg azokat a folytonos

f

függvényeket, amelyekre minden

x

valós számra

\begin{matrix} f (f (x)) = x + f (x) . \end{matrix}

Második nap

p (x) = x^{3} - 3 x + 1

. Adjunk meg olyan harmadfokú polinomot, amelynek a gyökei a

p (x)

gyökeinek az ötödik hatványai.

5. Az

A B C

háromszög beírt körének középpontja

I

B_{1}

és

C_{1}

A C

, illetve az

A B

oldalak felezőpontjai. A

C_{1} I

és

B_{1} I

egyenesek

B_{2}

-ben és

C_{2}

-ben metszik

A C

-t, illetve

A B

-t. Tudjuk, hogy az

A B C

és az

A B_{2} C_{2}

háromszögek területe egyenlő. Mekkora a

C A B

szög?

6. Adott

32

pozitív egész úgy, hogy egyikük sem nagyobb

60

-nál, az összegük pedig

120

. Bizonyítsuk be, hogy két egyenlő összegű csoportba rendezhetők.

Csapatverseny

Az alábbi feladatokban

G_{n}

mindig

n

-pontú egyszerű (többszörös élek nélküli, hurokél mentes) gráf,

K_{n}

pedig az

n

-pontú teljes gráf.

e (G_{n})

G_{n}

éleinek a számát jelöli.

A feladatok

1. Bizonyítsuk be, hogy ha

K_{n}

éleit

n

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

\begin{matrix} e (G_{n}) \geq \frac{n^{2}}{4} + 2, \end{matrix}

akkor

G_{n}

tartalmaz két olyan háromszöget, amelyeknek egyetlen közös csúcsa van.

3. Bizonyítsuk be, hogy ha

\begin{matrix} e (G_{n}) > \frac{1}{2} n \sqrt[]{n} + \frac{n}{4}, \end{matrix}

akkor

G_{n}

tartalmaz

4

hosszúságú kört.

4. a) Jelölje

K (2, 3)

azt a teljes páros gráfot, amelynek

3

fekete és

2

fehér csúcsa van. Bizonyítsuk be, hogy ha

G_{n}

nem tartalmazza

K (2, 3)

-at, akkor

\begin{matrix} e (G_{n}) \leq \frac{1}{\sqrt[]{2}} n \sqrt[]{n} + n . \end{matrix}

b) Bizonyítsuk be, hogy ha adott

n \geq 16

pont a síkon, akkor a köztük fellépő távolságok közül legfeljebb

n \sqrt[]{n}

lehet egységnyi hosszú.

5. Legyen

p

adott prím és tekintsük az

(x, y)

egész számpárokat

mod p

. Készítsük el azt a gráfot, amelynek csúcsai ezek a párok, és két csúcs,

(x, y)

és

(x', y')

között pontosan akkor halad él, ha

\begin{matrix} x x' + y y' \equiv 1 (mod p) . \end{matrix}

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

4

hosszúságú kört.
b) Bizonyítsuk be, hogy az

n

végtelen sok értékére létezik olyan

G_{n}

gráf, amelyiknek legalább

\begin{matrix} \frac{1}{2} n \sqrt[]{n} - n \end{matrix}

éle van és nem tartalmaz

4

hosszúságú kört.

⋆

Az alábbiakban közöljük a verseny legnehezebb feladatának a megoldását.

6. Adott

32

pozitív egész úgy, hogy egyikük sem nagyobb

60

-nál, az összegük pedig

120

. 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,

a_{1}

a_{2}

...

a_{32}

nagyság szerint növekvő sorba vannak rendezve.

1. Lemma. Ha a pozitív egész számokból álló

a_{i}

sorozatra teljesül, hogy

\begin{matrix} a_{i} \leq 1 + \sum_{j < i}^{} a_{j} \end{matrix}

minden

1 \leq i \leq n

esetén, akkor a sorozat ,,univerzális", azaz minden 1 és

\sum_{i = 1}^{n} a_{i}

közötti pozitív egész előáll az

a_{i}

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

a_{i} \leq i

teljesül minden

1 \leq i \leq n

esetén, akkor az

a_{i}

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

m

darab növekvően elrendezett pozitív egész szám, amelyek

S

összegére

S < 4 m - 6

(ez most nyilván teljesül, hiszen

S = 120 < 4 \cdot 32 - 6

) akkor a sorozatra teljesül

a_{i} \leq i

, ha

3 \leq i \leq m - 2

.
(Az adott intervallum akkor nem üres, ha

m > 4

, 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ó:

\begin{matrix} S = \sum_{j < i}^{} a_{j} + \sum_{j \geq i}^{} a_{j} \geq \sum_{j < i}^{} 1 + \sum_{j \geq i}^{} a_{i} = (i - 1) + a_{i} (m + 1 - i), \end{matrix}

(1)

és így

\begin{matrix} a_{i} \leq \frac{S + 1 - i}{m + 1 - i} = 1 + \frac{S - m}{m + 1 - i} . \end{matrix}

(*)

Eszerint az

\frac{S - m}{m + 1 - i} < i

egyenlőtlenségből következik az

a_{i} \leq i

feltétel. Ez utóbbi pedig egyenértékű a másodfokú

\begin{matrix} f (i) = i^{2} - (m + 1) i + S - m < 0 \end{matrix}

(2)

egyenlőtlenséggel. Mivel

f (3) = f (m - 2) = 6 - 4 m + S

, ami a feltétel (

S < 4 m - 6

) 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

a_{i}

sorozatban az

\frac{m + 1}{2}

-dik, középső tagra szimmetrikusan sérülhet az

a_{i} \leq i

feltétel.

3. Lemma. Ha (a korábbi jelölésekkel)

a_{1} \leq a_{2} \leq ... a_{m} \leq S / 2

, és az első

m - 2

tag univerzális sorozatot alkot, akkor

S / 2

előáll a sorozat néhány elemének az összegeként.

Bizonyítás. Mivel

a_{m} \leq S / 2

és

S - a_{m - 1} = a_{m} + \sum_{i = 1}^{m - 2} a_{i} \geq S / 2

, 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

a_{1} \leq 1

és

a_{2} \leq 2

, akkor a 2. lemma szerint az első

m - 2 = 30

szám univerzális sorozatot alkot, és így a 3. lemma szerint készen vagyunk.
Ha nem ez a helyzet, akkor

a_{1} + a_{2} \geq 4

. Mivel láttuk, hogy

a_{i} \leq i

, ha

m - 2 = 30 \geq i \geq 3

, mindenképpen teljesül, hogy

a_{3} \leq 3

. Az elemek rendezése miatt így

a_{2} \leq 3

. Két esetet különböztetünk meg aszerint, hogy

a_{2}

értéke 2 vagy pedig 3.
1. eset:

a_{2} = 2

.
Az

a_{1} + a_{2} \geq 4

feltételből most

a_{1} \leq a_{2}

miatt következik, hogy

a_{1} = a_{2} = 2

. 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

m - 2 \geq 15 = ⌈ \frac{32 - 2}{2} ⌉

páros számot kapunk. Most

a_{31} + a_{32} \leq 120 - (a_{1} + a_{2}) - 28 \cdot 2 = 60

, 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

m \geq 17

darab páros számot! Így az

\begin{matrix} 1 = b_{1} = b_{2} \leq b_{3} \leq b_{4} \leq ... \leq b_{m} \leq 30 \end{matrix}

sorozatot kapjuk, amelyre

\sum_{j = 1}^{m} b_{j} = 60

.
Erre a ,,felezett'' sorozatra még mindig teljesül, hogy

4 m - 6 \geq 4 \cdot 17 - 6 > 60

, tehát a 2. lemma szerint

b_{j} \leq j

, ha

3 \leq j \leq m - 2

, és mivel

b_{1} = b_{2} = 1

, a 3. lemma felhasználásával következik, hogy a

b_{j}

sorozat elemeiből előállítható a 30. Ez pedig, 2-vel szorozva, a 60 előállítását adja az

a_{i}

sorozat elemeiből.
2. eset:

a_{2} = 3

.
Láttuk, hogy

a_{3} \leq 3

, ezért most

a_{3} = 3

. 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

a_{30} + a_{31} + a_{32} \leq 120 - (a_{1} + a_{2}) - 27 \cdot 3 < 60

, 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

m - 2 \geq ⌈ \frac{32 - 2}{3} ⌉ = 10

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ó

m \geq 12

darab számot (a két darab félretett 3-assal együtt) 3-mal elosztva az alábbi sorozatot kapjuk:

\begin{matrix} 1 = b_{1} = b_{2} \leq b_{3} \leq ... \leq b_{m} \leq 20, \sum_{j = 1}^{m} b_{j} = 40. \end{matrix}

Készen vagyunk, hiszen most is

4 m - 6 \geq 4 \cdot 12 - 6 > 40

, így a

b_{1}

b_{2}

...

b_{m - 2}

univerzális, tehát a 3. lemma szerint

S / 2 = 20

előállítható az elemeiből.

Megjegyzések. 1. Szó szerint ugyanígy igazolható, hogy ha adott

m = 3 k + 2

darab szám, amelyek összege

S = 12 k

és egyikük sem nagyobb, mint

S / 2

, akkor ezek a számok két egyenlő összegű csoportra oszthatók. (A feladatban

k = 10

m = 32

S = 120

.) Az is látható, hogy az állítás éles, két példa is mutatja, hogy

3 k + 1

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.

\begin{matrix} \begin{matrix} {{\underset{︸}{1, 1, ..., 1}}_{3 k - 2 db}^{}, 3 k, 3 k + 1, 3 k + 1}, illetve {{\underset{︸}{2, 2, ..., 2}}_{3 k - 1 db}^{}, 3 k + 1, 3 k + 1} . \end{matrix} \end{matrix}

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

S

összegű

m

elemű halmaz két egyenlő összegű csoportra legyen felbontható (a nyilvánvalóan szükséges

a_{i} \leq S / 2

feltételen kívül.) Azonnal adódik, hogy ha az

S

páratlan, akkor ez soha nem tehető meg. Ha

S

páros, de nem osztható 4-gyel, akkor azt kapjuk, hogy a kritikus elemszám

\frac{S}{2} + 1

. Ha

S

osztható 4-gyel, de nem osztható 3-mal, akkor ez

⌈ \frac{S}{3} ⌉ + 1

, a versenyen kitűzött feladat pedig lényegében annak az esetnek a vizsgálata volt, amikor

S

osztható 3-mal is és 4-gyel is. Ilyenkor a legalacsonyabb a kritikus elemszám,

\frac{S}{4} + 2

. 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ő

a_{1} + a_{2} \geq 4

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

S / 2

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

a_{i}

-nél nem könnyebb súlyokat. Ha a két tartály tartalmát ebben az állapotban

S_{1}

és

S_{2}

jelöli (

S_{1} \leq S_{2}

nyilván föltehető), akkor nyilván

S_{1} + S_{2} = S - \sum_{j > i}^{} a_{j}

. Ha most

a_{i} \leq S / 2 - S_{2} (\leq S / 2 - S_{1})

, akkor az

a_{i}

súly is elfér, az eljárás tehát nem akad el. Ez biztosan teljesül, ha

2 a_{i} \leq 1 + (S / 2 - S_{1}) + (S / 2 - S_{2})

. 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

\begin{matrix} 2 a_{i} \leq 1 + S - \sum_{j > i}^{} a_{j} = 1 + \sum_{j \leq i}^{} a_{j} \end{matrix}

‐ ismerős? ‐ így ha

\begin{matrix} a_{k} \leq 1 + \sum_{j < k}^{} a_{j}, ha k = m, m - 1, ..., i, \end{matrix}

akkor a kiegyensúlyozó algoritmus lépéseivel akadálytalanul elhelyezhetők az

\begin{matrix} a_{m} \geq a_{m - 1} \geq ... \geq a_{i} \end{matrix}

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

S / 2

-nél, az algoritmust el tudjuk indítani. Ezzel becsatlakoztunk a fenti megoldásba, hiszen ott láttuk, hogy

f (i) < 0

-ból következik

a_{i} \leq i

, ami most elégséges ahhoz, hogy sikeresen lefusson az algoritmus. Az kis kezdőértékek most azt jelentik, hogy amikor elértünk

a_{3}

-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.