Kezdőlap


Feladat:	2000. évi Nemzetközi Matematika Diákolimpia 13. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Pálvölgyi Dömötör
Füzet:	2000/október, 388 - 389. oldal		PDF \| MathML
Témakör(ök):	Konstruktív megoldási módszer, Szöveges feladatok, Algebrai egyenlőtlenségek, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 2000/szeptember: 2000. évi Nemzetközi Matematika Diákolimpia 13. feladata

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.

Az egyszerűség kedvéért nevezzük a bolhákat pontoknak. Először azt mutatjuk meg, hogy $λ \geq \frac{1}{n - 1}$ -re az állítás mindig igaz. Azt mutatjuk meg, hogy akármilyen messzire eljuthatnak a pontok, ha mindig a legbalra esővel átugorjuk a legjobbra esőt. Ebben az esetben egy mohó algoritmus eljuttatja a pontokat $M$ -en túlra. Az első $n - 1$ lépésben minden pont különböző helyre kerül, ezt tekinthetjük a továbbiakban kiindulóhelyzetnek. Jelölje itt a szomszédos pontok közötti távolságot rendre $d_{1}$ , $d_{2}$ , $...$ , $d_{n - 1}$ . Egy ugrás után az új távolságok: $d_{2}$ , $d_{3}$ , $...$ , $d_{n - 1}$ , $(d_{1} + d_{2} + ... + d_{n - 1}) \cdot λ$ . Mivel

\begin{matrix} (d_{1} + d_{2} + ... + d_{n - 1}) \cdot λ \geq \frac{d_{1} + d_{2} + ... + d_{n - 1}}{n - 1} \geq {min}_{}^{} (d_{1}, ..., d_{n - 1}), \end{matrix}

azért a legkisebb távolság változatlan marad. Jelölje ezt

d

. A legjobbra fekvő pont így minden lépésben legalább

d

-vel jobbra kerül. Mivel

d > 0

, azért egy idő után akármilyen messzire eljut. Ezután

n - 1

lépésben a többi pont is

M

-en túlra jut, és ezt akartuk bizonyítani.
Most megmutatjuk, hogy ha

λ < \frac{1}{n - 1}

, akkor semelyik kiindulóhelyzetből sem lehet akármilyen messzire eljutni. Minden ponthoz rendeljünk hozzá ugyanis egy számot úgy, hogy az egyenest a számegyenesnek tekintjük. Legyen

s_{k}

k

-adik lépés után a pontoknak megfelelő számok összege,

w_{k}

pedig a számok legnagyobbika. Nyilván

s_{k} \leq n \cdot w_{k}

. Ha bebizonyítanánk, hogy

w_{k}

korlátos, akkor készen lennénk, mert így egy pont sem juthatna át egy bizonyos

M

-en (a korláton) túlra. Ugorja át

A

(k + 1)

-edik lépésben

B

-t és ezzel kerüljön

C

-be. Az értelemszerű jelölésekkel ebből:

\begin{matrix} s_{k + 1} = s_{k} + c - a, c - b = λ (b - a), \end{matrix}

ezt átrendezve

λ (c - a) = (1 + λ) (c - b)

. Tehát

s_{k + 1} = s_{k} + \frac{1 + λ}{λ} (c - b)

.
Most igazoljuk, hogy

\begin{matrix} s_{k + 1} - s_{k} = \frac{1 + λ}{λ} (c - b) \geq \frac{1 + λ}{λ} (w_{k + 1} - w_{k}) . \end{matrix}

b \leq w_{k}

, tehát ha

c \geq w_{k + 1}

, akkor ez valóban igaz. Ha pedig

c < w_{k + 1}

, akkor

w_{k + 1} = w_{k}

, hiszen a legjobbra eső pont nem változhatott másra, mint

c

-re. Ekkor az egyenlőtlenség nyilvánvaló.
Tehát

s_{k + 1} - s_{k} \geq \frac{1 + λ}{λ} (w_{k + 1} - w_{k})

. Vagyis

\frac{1 + λ}{λ} \cdot w_{k} - s_{k} \geq \frac{1 + λ}{λ} w_{k + 1} - s_{k + 1}

.
Mivel

λ < \frac{1}{n - 1}

, azért

1 + λ > n λ

, amiből

\frac{1 + λ}{λ} - n > 0

. Legyen

μ = \frac{1 + λ}{λ} - n

. Ekkor

\begin{matrix} \frac{1 + λ}{λ} \cdot w_{k} - s_{k} = μ \cdot w_{k} + (n \cdot w_{k} - s_{k}) \geq μ \cdot w_{k}, \end{matrix}

Ezek szerint

w_{k} \leq \frac{\frac{1 + λ}{λ} \cdot w_{1} - s_{1}}{μ}

, tehát

w_{k}

korlátos, készen vagyunk.
Így a megoldás:

λ \geq \frac{1}{n - 1}

Pálvölgyi Dömötör (Fazekas M. Főv. Gyak. Gimn., 12. o.t.)