Kezdőlap


Feladat:	F.3048	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Farkas Illés , Pap Gyula , Rozmán András , Szádeczky-Kardoss Szabolcs , Tóth Gábor Zsolt , Valkó Benedek , Várkonyi Péter , Zubcsek Péter Pál
Füzet:	1995/október, 420. oldal		PDF \| MathML
Témakör(ök):	Konstruktív megoldási módszer, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1995/január: F.3048

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.

Mutatunk egy algoritmust, amelyet követve a bolhát biztosan el tudjuk pusztítani. A módszer azon múlik, hogy a bolha útvonalát ,,elő lehet írni'': minden pillanatban háromfelé ugorhat, de mi a három lehetséges hely közül kettőt megmérgezhetünk. Tehát ha a bolha ugrása után nem kiáltotta, hogy ,,NYEKK'', biztos, hogy ezen az útvonalon van. Az útvonalat pedig úgy választjuk, hogy visszatérjen az origóba.
Jelöljük a három vektort, amellyel a bolha elmozdulhat, $u_{1}$ , $u_{2}$ , $u_{3}$ -mal. Könnyű ellenőrizni, hogy

\begin{matrix} 2 u_{1} + 99 u_{2} + 99 u_{3} = 0. \end{matrix}

(1)

Ha tehát két ugrás az

u_{1}

vektorral történik, 99 ugrás pedig az

u_{2}

, illetve

u_{3}

vektorral, akkor a bolha visszatér az origóba.
Definiáljuk az

A_{0}

...

A_{200}

pontokat úgy, hogy

A_{0}

az origó legyen,

\begin{matrix} \begin{matrix} \vec{A_{0} A_{1}} = \vec{A_{1} A_{2}} = u_{1}, \vec{A_{2} A_{3}} = \vec{A_{3} A_{4}} = ... = \vec{A_{100} A_{101}} = u_{2}, \\ \vec{A_{101} A_{102}} = \vec{A_{102} A_{103}} = ... = \vec{A_{199} A_{200}} = u_{3} \end{matrix} \end{matrix}

legyen. Ezeket a pontokat írjuk elő a bolha útvonalának. Az (1) egyenlőség alapján

A_{200} = A_{0}

, az útvonal körbeér.
Az

A_{i}

pontból a

u_{1}

u_{2}

u_{3}

vektorok három különböző pontba mutatnak, ezek közül az egyik az

A_{i + 1}

pont. A másik két pontot jelöljük

B_{i}

-vel és

C_{i}

-vel.
Az első 200 lépésben mérgezzük meg sorban a

B_{0}

és

C_{0}

B_{1}

és

C_{1}

...

B_{199}

és

C_{199}

pontokat. Azt állítjuk, hogy

k

perc eltelte után (

0 \leq k \leq 200

) a bolha vagy már elpusztult, vagy az

A_{0}

...

A_{k}

pontok valamelyikén tartózkodik. Ezt

k

szerinti indukcióval bizonyítjuk. Ha

k = 0

, akkor állításunk igaz, mert a bolha

A_{0}

-ból indul. Ha pedig

k = m

lépés után az

A_{0}

...

A_{m}

pontok valamelyikén tartózkodik, akkor a következő percben vagy nem ugrik (és akkor ugyanezeken a pontokon marad), vagy pedig továbbugrik az

A_{1}

...

A_{m + 1}

B_{0}

...

B_{m}

C_{0}

...

C_{m}

pontok közül valamelyikre. Viszont az

(m + 1)

-edik perc végére megmérgeztük a

B_{0}

...

B_{m}

C_{0}

...

C_{m}

pontokat. Ha tehát a bolha életben marad, akkor az

A_{0}

...

A_{m + 1}

pontok valamelyikén van.
A 200-adik perc letelte után a bolha már csak az

A_{0} \to A_{1} \to A_{2} \to ... \to A_{199} \to A_{0}

körpályán ugrálhat, mert mind megmérgeztük a

B_{0}

...

B_{199}

C_{0}

...

C_{199}

pontokat. Ha a következő 100 percben sorra megmérgezzük a körpálya pontjait, biztosan elpusztítjuk a bolhát.

Rozmán András (Szombathely, Nagy Lajos Gimn., III. o.t.) dolgozata alapján

Megjegyzés. A feladat általánosítása az N. 56., amelynek megoldása a 422. oldalon található.