Kezdőlap


Cím:	5. magyar-izraeli matematikaverseny
Szerző(k):	Pelikán József
Füzet:	1994/május, 255 - 257. 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.

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.

Pelikán József

Az egyéni verseny feladatai

1. Legyen

m

és

n

két különböző pozitív egész szám. Bizonyítsuk be, hogy létezik olyan

x

valós szám, amire

\begin{matrix} \frac{1}{3} \leq {x n} \leq \frac{2}{3} és \frac{1}{2} \leq {x m} \leq \frac{2}{3} . \end{matrix}

(Itt

{a}

a

valós szám törtrészét jelenti, vagyis

{a} = a - [a]

.)
2. Legyenek

a_{1}, a_{2}, ..., a_{k}; a_{k + 1}, ..., a_{n}

pozitív számok

(k < n)

. Rögzítsük az

a_{k + 1}, ..., a_{n}

értékeket. Hogyan kell megválasztanunk az

a_{1}, a_{2}, ..., a_{k}

számokat, hogy az

\begin{matrix} S = \sum \frac{a_{i}}{a_{j}} \end{matrix}

összeg minimális legyen

(i, j \in {1,2, ..., n}, i \neq j)

?
3. Három egyenlő sugarú kör egy közös

P

ponton megy át, további, páronként vett metszéspontjaik

A, B, C

. A három kört magába foglalja az

A' B' C'

háromszög, amelynek oldalai rendre érintenek kettőt-kettőt az adott körök közül. Bizonyítsuk be, hogy

\begin{matrix} t_{A' B' C'} \geq 9 \cdot t_{A B C} . \end{matrix}

4. Nevezzünk ,,

n

‐

m

-társaság''-nak egy

n

lányból és

m

fiúból álló társaságot. Bizonyítsuk be, hogy léteznek olyan

n_{0}, m_{0}

számok, hogy minden

n_{0}

‐

m_{0}

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

G = (V, E)

egy irányítatlan gráf;

V

a csúcsok,

E

az élek halmaza. Legyen

w : E \to R

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

G

összefüggő. Keressünk

O (m)

lépésben

(m = | E |)

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.

G = (V, E)

összefüggő, irányítatlan gráf,

w : E \to R

egy súlyfüggvény,

e = (x, y)

pedig

G

egy rögzített éle. Döntsük el

O (m)

lépésben

(m = | E |)

, hogy létezik-e minimális súlyösszegű feszítőfa, amely

e

-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

G = (V, E)

irányított gráf, egy kitüntetett

s \in V

csúcs (a ,,forrás''), egy

w : E \to R

függvény, amely minden élhez egy pozitív súlyt rendel és egy

d : V \to R

függvény. Valaki azt állítja, hogy minden

x \in V

csúcsra

d (x)

s \to x

irányított utak súlyösszegeinek minimuma.
Döntsük el

O (n + m)

lépésben, igaz-e ez az állítás. (

n = | V |, m = | E |

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

k

-reguláris gráfon olyan (irányítatlan) gráfot értünk, amelyben minden pont foka

k

.
a) Mutassuk meg, hogy minden 3-reguláris

G = (V, E)

gráf élhalmaza két

E_{1}

E_{2}

részre bontható úgy, hogy a

(V, E_{1})

és

(V, E_{2})

gráfok mindegyikében minden pont foka legfeljebb 2.
b) Határozzunk meg ilyen

E_{1}

E_{2}

-t,

O (m)

időben

(m = | E |)

.
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

O (m)

idejű algoritmust egy 3-reguláris

G

gráf éleinek 4 színnel való jó színezésére.
5. Legyenek

x_{1}, ..., x_{n} \in {+ 1, - 1}

ismeretlen számok. Meg akarjuk határozni

\prod x_{i}

-t (vagyis az

x_{i}

-k között a

(- 1)

-ek számának paritását).
,,Lineáris kérdés''-eket tehetünk fel. Egy lineáris kérdés

n + 1

valós szám:

a_{1}, ..., a_{n}, b

megadásából áll. A válasz egy ilyen kérdésre ,,IGEN'', ha

\begin{matrix} a_{1} x_{1} + ... + a_{n} x_{n} > b, \end{matrix}

egyébként ,,NEM''.
Bizonyítsuk be, hogy ha van olyan stratégiánk, ami biztosan megállapítja

\prod x_{i}

-t legfeljebb

k

db lineáris kérdés segítségével (bármi volt is

x_{1}, ..., x_{n}

), akkor

k > log n

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