Kezdőlap


Feladat:	1986. évi Nemzetközi Matematika Diákolimpia 13. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Kós Géza
Füzet:	1986/november, 356 - 357. oldal		PDF \| MathML
Témakör(ök):	Konstruktív megoldási módszer, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1986/szeptember: 1986. é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.

3. feladat. Egy szabályos ötszög csúcsaihoz egy-egy egész számot rendelünk úgy, hogy összegük pozitív legyen. Megengedett a következő művelet: ha három szomszédos csúcs $X$ , $Y$ , $Z$ és a hozzájuk rendelt számok $x$ , $y$ , $z$ , és $y < 0$ , akkor az $x$ , $y$ , $z$ számok helyére ugyanilyen sorrendben az $x + y$ , $- y$ , $z + y$ számokat írjuk. Ezt a műveletet ismételgetjük addig, amíg csak található negatív $y$ . Döntsük el, vajon minden esetben véget ér-e az eljárás véges sok lépés után!

Megoldás. Az eljárás véges sok lépés után minden esetben véget ér, függetlenül attól, hogy milyen sorrendben végezzük el a lépéseket. Legyen az ötszög csúcsaihoz rendelt öt szám kezdetben

a_{0}

b_{0}

c_{0}

d_{0}

e_{0}

, az

n

-edik "művelet'' elvégzése után pedig

a_{n}

b_{n}

c_{n}

d_{n}

e_{n}

. Világos, hogy bármely lépés után a számok egészek maradnak, és összegük nem változik, tehát pozitív marad. Definiáljuk az

S_{n}

nem-negatív egész számot így:

\begin{matrix} S_{n} = {(a_{n} - c_{n})}^{2} + {(b_{n} - d_{n})}^{2} + {(c_{n} - e_{n})}^{2} + {(d_{n} - a_{n})}^{+} {(e_{n} - b_{n})}^{2} . \end{matrix}

Ha valamely

k

természetes számra az

a_{k}

b_{k}

c_{k}

d_{k}

e_{k}

számok között van negatív (mondjuk

c_{k} < 0

), akkor a következő lépés után nyert

a_{k + 1} = a_{k}

b_{k + 1} = b_{k} + c_{k}

c_{k + 1} = - c_{k}

d_{k + 1} = d_{k} + c_{k}

e_{k + 1} = e_{k}

számokra

S_{k + 1} < S_{k}

. Ugyanis behelyettesítéssel

\begin{matrix} S_{k + 1} - S_{k} = 2 c_{k} (a_{k} + b_{k} + c_{k} + d_{k} + e_{k}), \end{matrix}

és itt

c_{k} < 0

a_{k} + b_{k} + c_{k} + d_{k} + e_{k} > 0

, mint azt már említettük. Ez pedig azt jelenti, hogy

S_{0}

S_{1}

S_{2}

...

szigorúan csökkenő nem negatív egész számok. Így sorozatuk csak véges hosszúságú lehet, vagyis az eljárás véges sok lépésben mindig véget ér.