Kezdőlap


Cím:	Olimpia'91 (3.)
Füzet:	1991/május, 213 - 217. 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.

Február 28-án és március 1-jén kétnapos versenyre került sor a nyári Sigtuna-i (Svédország) XXXII: Nemzetközi Matematikai Diákolimpiára történő felkészülés következő állomásaként. A korábbi versenyek eredményei alapján 58 diák vett részt az olimpiai rendszerben ‐ mindkét napon 3‐3 feladat ‐ lezajlott versenyen, amelynek zökkenőmentes lebonyolítására az Állami Biztosító és az Intellrobot szíves támogatásával került sor.

A verseny feladatai a következők voltak:

1. Legyen

P

egy páros oldalú konvex sokszög olyan belső pontja, amelyik nincs rajta a sokszög egyik átlóján sem. Legyen

H

azoknak a háromszögeknek a halmaza, amelyek csúcsai a sokszög csúcsai közül valók és tartalmazzák a

P

pontot.
Bizonyítsuk be, hogy

H

-nak páros sok eleme van.
(7 pont)

2. Van három urnánk, mindegyikükben néhány golyó. Ha az A urnában legalább annyi golyó van, mint a

B

urnában, akkor a

B

urna tartalmát megduplázhatjuk az

A

-ból kivett golyókkal, és ez a lépés bármely két urna között elvégezhető.
Bizonyítsuk be, hogy ilyen lépések alkalmas sorozatával a három urna valamelyike kiüríthető.
(7 pont)

3. Mennyi

x^{2}

y^{2}

z^{2}

v^{2}

x y

z v

minimuma, ha

x, y, z

és

v

olyan valós számok, amelyekre

x v - y z = 1

?
(7pont)

4. Milyen nemnegatív egész

k

számra lehet az

\begin{matrix} 1598,1598 + 1, ...,1598 + k \end{matrix}

számokat két közös elem nélküli halmazba osztani úgy, hogy mindkét halmazban egyenlő legyen a számok összege?
(7 pont)

5. Az

A B C

háromszög

A B, B C

, illetve

C A

oldalán úgy vesszük föl a

C_{1}, A_{1}

illetve

B_{1}

pontokat, hogy az

A B_{1} C_{1}, B C_{1} A_{1}

és

C A_{1} B_{1}

háromszögek beírt körei egyenlő sugarúak. Ha ez a sugár

ϱ

, az

A_{1} B_{1} C_{1}

illetve az

A B C

beírt körének sugara pedig

r_{1}

, illetve

r

akkor bizonyítsuk be, hogy

\begin{matrix} r = r_{1} + ϱ . \end{matrix}

(7 pont)

6. Bizonyítsuk be, hogy ha

n

pozitív egész, akkor létezik három különböző egész, melyek mindegyike nagyobb mint

n^{2}

és kisebb mint

n^{2} + n + 3 \sqrt[]{n}

úgy, hogy egyikük osztója a másik kettő szorzatának.
(7pont)

A verseny első hat helyezettje:

Boncz András IV. o. t. (Zrínyi Gimn., Zalaegerszeg) 34 pont,
Harcos Gergely IV. o. t. (Apáczai Gimn., Budapest) 33 pont,
Turányi Zoltán IV. o. t. (Berzsenyi Gimn., Budapest) 29 pont,
Ujváry-Menyhárt Zoltán III. o. t. (Fazekas Gimn., Budapest) 28 pont,
Pór Attila III. o. t. (Fazekas Gimn., Budapest) 28 pont,
Maróti Miklós IV. o. t. (Radnóti Gimn., Szeged) 27 pont.

Az eddigi eredmények alapján 20-fős keret készül tovább a nyári olimpiára, a verseny első négy helyezettje pedig a négytagú magyar csapatot alkotta a II. magyar-izraeli matematikaversenyen, amelyre március 21. és 28. között került sor, ezúttal Budapesten. (Erről őszi számaink valamelyikében részletes beszámolót közlünk.)
Köszönetet mondunk Benczúr Péter, Drasny Gábor, Hausel Tamás, Keleti Tamás, Kecskés Kornél, Sustik Mátyás volt olimpikon matematikus egyetemi hallgatóknak a verseny lebonyolításában és a dolgozatok gyors értékelésében nyújtott segítségükért.
Az alábbiakban a verseny nehezebbnek bizonyult 2., 3. és 6. feladatainak megoldását közöljük.

2. feladat
I. megoldás. Hívjunk egy urnát párosnak, illetve páratlannak attól függően, hogy a benne lévő golyók száma páros vagy páratlan. Először megmutatjuk, hogy minden eset visszavezethető arra, amikor az urnák közül kettő páros, egy pedig páratlan.
Ha az urnákban összesen páratlan sok golyó van, akkor vagy máris a fenti helyzetben vagyunk, vagy pedig mindhárom urna páratlan. Ekkor két tetszőlegesen kiszemelt urna között egy lépést elvégezve a páros‐páros‐páratlan esethez jutunk.
Ha a golyók összege az urnákban páros, akkor vagy mindhárom urna páros, vagy pontosan kettő páratlan. Utóbbi esetben a két páratlan urna között egy lépést elvégezve mindhárom urna páros lesz. Ragasszuk most össze minden egyes urnában kettesével a golyókat; minden egyes további lépés ezután nyilván úgy is elvégezhető, hogy a golyókat párosával mozgatjuk. A ,,golyók'' száma tehát a felére csökken, ezzel előbb-utóbb eljutunk a páratlan összeghez, így valóban elegendő a páros‐páros‐páratlan esettel foglalkozni.
Jelölje tehát az egyes urnák tartalmát

a

b

és

c

, ahol

a

és

b

páros,

c

pedig páratlan, és az is nyilván föltehető, hogy

a < b

. Megmutatjuk, hogy ebből véges sok lépés után eljuthatunk az

(a, b - a, c + a)

állapotba, ahol tehát két urna továbbra is páros, a páratlan urnában pedig nőtt a golyók száma ‐ és természetesen továbbra is páratlan maradt. Innen a feladat állítása már következik, hiszen a páratlan urna tartalma nem lehet akármilyen nagy, ezért előbb-utóbb egyenlő kell legyen a két páros urna tartalma, és így a következő lépésben egyikük kiüríthető.
A fenti állításhoz bebizonyítjuk, hogy egy páros és egy páratlan urna között megfelelő számú lépést elvégezve a páros urna tartalma megfelezhető. Legyen ugyanis a kezdeti állapot

(u_{0}, v_{0})

‐ ahol tehát

(u_{0}, v_{0})

páratlan ‐ a lépések sorozata pedig

\begin{matrix} (u_{0}, v_{0}) \to (u_{1}, v_{1}) \to ... \to (u_{n}, v_{n}) \to ... \end{matrix}

Mivel

u_{i} + v_{i}

állandó és az ilyen rendezett párok száma véges, előbb-utóbb olyan

(u, v)

állapothoz jutunk, amelyik már korábban is előfordult. Gondoljuk meg azonban, hogy ha

u

és

v

közül pontosan az egyik páros ‐ mondjuk

u

‐, akkor csak az

(\frac{u}{2}, v + \frac{u}{2})

állapotból kaphattuk az

(u; v)

állapotot, hiszen a páratlan

v

értéket nem kaphattuk duplázással. Ez azt jelenti, hogy egy páros‐páratlan

(u, v)

állapot elődje egyértelmű. Ha pedig egy állapot valamikor megismétlődik, akkor mivel egyenlő állapotok elődei is azok, az elsőnek ismétlődő állapot csak az

(u_{0}, v_{0})

lehetett. Az állapotok sorozata tehát ,,tiszta szakaszos'' .
Nézzük most a két urnát a kezdeti

(u_{0}, v_{0})

állapot első ismétlődése előtt. Az előbbiek szerint ha például

u_{0}

páros, akkor

(u_{0}, v_{0})

egyértelmű elődje

(u_{0} / 2, v_{0} + u_{0} / 2),

valóban megfeleztük a páros urna tartalmát. Ha még azt is biztosítjuk, hogy

u_{0} / 2

is páros legyen, akkor a kezdetben páratlan urna a páros megfelezése után is páratlan marad.
Tekintsük e célból a fentiekben említett páros‐páros‐páratlan

(a, b, c)

állapotot, ahol tehát

a

b

a két páros urna tartalma. Köztük egyetlen lépést végrehajtva a

(2 a, b - a, c)

állapothoz jutunk. Ha ezután felezzük meg az első urna tartalmát a páratlan urna segítségével, akkor éppen az igért

(a, b - a, c + a)

állapotot kapjuk, és innen, mint láttuk, a bizonyítandó állítás következik.

Maróti Miklós dolgozata alapján

Megjegyzés. A bizonyításban kulcsszerepet játszott az alábbi, más feladatok megoldása során is jól használható észrevétel. Ha

M

egy véges halmaz,

f

pedig az

M

-nek egy kölcsönösen egyértelmű leképezése önmagára ‐ tehát

f

-nek létezik inverze ‐, akkor tetszőleges

a_{0} \in M

-ből kiindulva az

a_{n} = f (a_{n - 1})

összefüggéssel kapott

a_{0}, a_{1}, ..., a_{k} ...

sorozat ,,tiszta szakaszos''.

II. megoldás. Jelölje az

A

B

C

urnákban a golyók kezdeti mennyiségét

a

b

és

c

, ahol

0

a

b

c

nyilván föltehető. Megadunk egy eljárást, melynek eredményeként az urnák tartalmának a minimuma ‐ ez most

a

‐ csökken. Ez nyilván elegendő, hisz az eljárás véges sokszori alkalmazásával valamelyik urna kiürül.
Osszuk el

b

-t ‐ a középső urna tartalmát ‐ maradékosan

a

-val, legyen

b = a \cdot q + r

, ahol

0 ≦ r < a .

Megmutatjuk, hogyan vehető ki a

B

urnából

q \cdot a

darab golyó.
Írjuk fel a

q

-t a kettes számrendszerben, majd tegyünk az

A

urnába rendre

a

2 a

4 a

...

2^{k}

\cdot a

...

darab golyót úgy, hogy ha

2^{i}

szerepel a

q

kettes számrendszer-beli alakjában, akkor a

B

-ből, ha pedig nem, akkor a

C

-ből rakunk át az

A

-ba

2^{i} \cdot a

darab golyót. Mivel

b < c

, így a

C

-beli golyók erre elegendők, hiszen utoljára a

B

urnából veszünk ki golyót.
Az eljárás végén a

B

urnában

r

darab golyó marad, és így

r < a

miatt a minimum valóban csökken. Ezzel a bizonyítást befejeztük.

Faragó Gergely és Csörnyei Marianna ötlete nyomán
Keleti Tamás ELTE, TTK

3. feladat. A feladatra algebrai és geometriai jellegű megoldások születtek. Lássunk először egy algebrait.
Mivel kifejezésünk ilyen formában nehezen kezelhető, próbálkozzunk meg új változók bevezetésével: legyen

\begin{matrix} x = a + b, y = a - b, v = c + d, z = c - d \end{matrix}

(ilyen

a

b

c

d

nyilván létezik). Ezzel a helyettesítéssel kifejezésünk a következő alakot ölti:

\begin{matrix} {(a + b)}^{2} + {(a - b)}^{2} + {(c + d)}^{2} + {(c - d)}^{2} + (a + b) (a - b) + (c + d) (c - d) = 3 a^{2} + b^{2} + 3 c^{2} + d^{2} . \end{matrix}

Vizsgáljuk meg, mit kapunk a feltételből:

\begin{matrix} (a + b) (c + d) - (a - b) (c - d) = 2 a d + 2 b c = 1. \end{matrix}

A befejezés ezután kézenfekvő; mivel

\begin{matrix} {(\sqrt[]{3} a - d)}^{2} + {(\sqrt[]{3} c - b)}^{2} ≧ 0, ezért 3 a^{2} + b^{2} + 3 c^{2} + d^{2} ≧ \sqrt[]{3} (2 a d + 2 b c) = \sqrt[]{3} . \end{matrix}

Kifejezésünk így mindenesetre legalább

\sqrt[]{3}

. Megmutatjuk, hogy ezt az értéket el is érheti: a

\begin{matrix} d = \sqrt[]{3} a, b = \sqrt[]{3} c és 2 a \sqrt[]{3} a + 2 c \sqrt[]{3} c = 1 -ből a^{2} + c^{2} = \frac{1}{2 \sqrt[]{3}} \end{matrix}

egyenletrendszer bármely megoldására (ilyen nyilván létezik) kifejezésünk értéke, a feltétel teljesülése mellett,

\sqrt[]{3}

lesz. A keresett minimum értéke tehát

\sqrt[]{3} .

─

•

─

Ezután az ,,algebrai'' bizonyítás után talán egy kicsit meglepő, hogy feladatunk lényegében ‐ a háromszög geometriájából jól ismert ‐

\begin{matrix} a^{2} + b^{2} + c^{2} ≧ 4 T \sqrt[]{3} \end{matrix}

(1)

egyenlőtlenség igazolása volt, ahol

a

b

és

c

egy

T

területű háromszög oldalai. Tekintsük ehhez a síkon az

A (0,0)

B (- x, z)

C (y, - v)

pontokat. Ekkor az

A B C

háromszög oldalainak négyzetösszege a következő lesz:

\begin{matrix} A B^{2} + A C^{2} + B C^{2} = x^{2} + z^{2} + y^{2} + v^{2} + {(x + y)}^{2} + {(v + z)}^{2} = 2 (x^{2} + y^{2} + v^{2} + z^{2} + x y + v z), \end{matrix}

míg a háromszög területére az ismert összefüggés szerint:

2 T = | x v - y z |

, ami a feltétel szerint

1

. Az (1) egyenlőtlenségbe ezeket beírva kapjuk, hogy

\begin{matrix} x^{2} + y^{2} + v^{2} + z^{2} + x y + v z ≧ \sqrt[]{3}, \end{matrix}

és az egyenlőség pontosan akkor teljesül, ha az

A B C

háromszög szabályos és területe

1 / 2.

Hausel Tamás, ELTE, TTK

6. feladat

Megoldás. Adott

n > 0

esetén jelölje

k

azt a legnagyobb egész számot, amelyre

k (k + 1) < n .

Erre a

k

-ra nyilván

0 ≦ k < n

, továbbá

\begin{matrix} k (k + 1) < n ≦ (k + 1) (k + 2) . \end{matrix}

Legyen

\begin{matrix} a & = (n + k + 1) (n - k), & (1) \\ b & = (n + k + 2) (n - k), & (2) \\ c & = (n + k + 1) (n - k + 1) . & (3) \end{matrix}

a

b

c

értékek ilyen kiválasztásával nyilván

a | b \cdot c,

továbbá

b = (a + n - k)

c = a + n + k + 1

miatt

a < b < c

, hiszen

0 ≦ k < n .

Így elegendő az

\begin{matrix} n^{2} < a = n^{2} + n - k (k + 1) & (4) \end{matrix}

és az

\begin{matrix} n^{2} + n + 3 \sqrt[]{n} > c = n^{2} + n + n - (k^{2} - 1) & (5) \end{matrix}

egyenlőtlenségeket igazolnunk.
A (4) egyenlőtlenség a

k

kiválasztásából adódó

n - k (k + 1) > 0

egyenlőtlenség nyilvánvaló következménye. Az (5) egyenlőtlenséghez pedig elegendő a rendezés után adódó

\begin{matrix} n - 3 \sqrt[]{n} + 1 < k^{2} & (6) \end{matrix}

egyenlőtlenséget igazolnunk. Ez nyilván teljesül, ha

n = 1

vagy

2

, hiszen ekkor

k = 0

és (6) bal oldala negatív.
Legyen

n ≧ 3

és tegyük fel, hogy (6) mégsem igaz, vagyis

\begin{matrix} k^{2} ≦ n - 3 \sqrt[]{n} + 1 = {(\sqrt[]{n} - \frac{3}{2})}^{2} - \frac{5}{4} . \end{matrix}

Ez azt jelenti, hogy

k < | \sqrt[]{n} - \frac{3}{2} | = \sqrt[]{n} - \frac{3}{2},

ahonnan

\begin{matrix} (k + 1) (k + 2) < (\sqrt[]{n} - \frac{1}{2}) (\sqrt[]{n} + \frac{1}{2}) = n - \frac{1}{4} < n, \end{matrix}

ellentétben a

k

kiválasztásával.

Drasny Gábor, ELTE, TTK