Kezdőlap


Cím:	Egy olimpiai feladat általánosítása (1987. november)
Szerző(k):	Kós Géza
Füzet:	1987/november, 358 - 360. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

Varsóban, a XXVII. Nemzetközi Matematikai Diákolimpián szerepelt a következő 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

, 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ételjü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!''

A feladatot megfogalmazhatjuk általánosabban is úgy, hogy a szabályos ötszög helyett szabályos

n

-szöget tekintünk (

n ≧ 3

).
A továbbiakban bizonyítást adunk arra, hogy az eljárás ‐ bármely

n

esetén ‐ véges sok lépés után véget ér.
Gondolatmenetünk a következő lesz: minden szám

n

-eshez egy-egy nem negatív egész számot rendelünk úgy, hogy ez a szám minden egyes "művelet'' során csökkenjen. Ha tehát a kezdeti szám

n

-eshez rendelt érték

S_{0}

, az első "művelet'' során keletkező szám

n

-eshez rendelt szám

S_{1}

, és általában (ha a műveletet

k

-szor végre tudjuk hajtani), a

k

-adik "művelet'' során keletkező szám

n

-eshez rendelt szám

S_{k}

, akkor

S_{0} > S_{1} > S_{2} > ... > S_{k} ≧ 0

legyen.

S_{1}, S_{2}, ..., S_{k}

így csupa különböző,

S_{0}

-nál kisebb nem negatív egész, ennélfogva

k ≦ S_{0}

, ami azt jelenti, hogy az eljárás véges sok ‐ legfeljebb

S_{0}

darab lépés után véget ér.
Vezessük be a következő függvényeket:

\begin{matrix} p_{1} (x_{1}, x_{2}, ..., x_{n}) & = x_{1}^{2} + x_{1}^{2} + ... + x_{n}^{2} \\ p_{2} (x_{1}, x_{2}, ..., x_{n}) & = {(x_{1} + x_{2})}^{2} + {(x_{2} + x_{3})}^{2} + ... + {(x_{n} + x_{1})}^{2} \\ p_{3} (x_{1}, x_{2}, ..., x_{n}) & = {(x_{1} + x_{2} + x_{3})}^{2} + {(x_{2} + x_{3} + x_{4})}^{2} + ... + {(x_{n} + x_{1} + x_{2})}^{2} \\ ⋮ \\ p_{n - 2} (x_{1}, x_{2}, ..., x_{n}) & = {(x_{1} + x_{2} + ... + x_{n - 2})}^{2} + {(x_{2} + x_{3} + ... + x_{n - 1})}^{2} + \\ + ... + {(x_{n} + x_{2} + ... + x_{n - 3})}^{2} . \end{matrix}

Legyen (

a_{1}, a_{2}, ..., a_{n}

) egy szám

n

-es, amelyben

a_{1} + a_{2} + ... + a_{n} > 0

(egy "művelet'' során a számok összege nem változik) és legyen például

a_{1} < 0

.
Legyen továbbá

b_{1} = - a_{1}

b_{2} = a_{2} + a_{1}

b_{3} = a_{3}

b_{4} = a_{4}, ..., b_{n - 1} = a_{n - 1}, b_{n} = a_{n} + a_{1}

az a szám

n

-es, amely úgy keletkezik, hogy a "műveletet'' az

(a_{n}, a_{1}, a_{2})

számokra végrehajtjuk.
Megmutatjuk, hogy

\begin{matrix} p_{1} (b_{1}, b_{2}, ..., b_{n}) - p_{1} (a_{1}, a_{2}, ..., a_{n}) = 2 a_{1} (a_{1} + a_{2} + a_{n}), \end{matrix}

és minden

2 ≦ i ≦ (n - 2)

-re

\begin{matrix} p_{i} (b_{1}, b_{2}, ..., b_{n}) - p_{i} (a_{1}, a_{2}, ..., a_{n}) = 2 a_{1} (a_{i + 1} + a_{n - i + 1}) . \end{matrix}

Mivel minden

3 ≦ j ≦ (- 1)

-re

b_{j} = a_{j}

, ezért

p_{1}

megváltozása valóban

\begin{matrix} p_{1} (b_{1}, b_{2}, ..., b_{n}) - p_{1} (a_{1}, a_{2}, ..., a_{n}) = b_{1}^{2} - a_{1}^{2} + b_{2}^{2} - a_{2}^{2} + b_{n}^{2} - a_{n}^{2} = \\ = ({(- a_{1})}^{2} - a_{1}^{2}) + ({(a_{2} + a_{1})}^{2} - a_{2}^{2}) + ({(a_{n} + a_{1})}^{2} - a_{n}^{2}) = 2 a_{1} (a_{1} + a_{2} + a_{n}) . \end{matrix}

Legyen most

2 ≦ i ≦ n - 2

(természetesen csak ha

n ≧ 4

). Ekkor

\begin{matrix} p_{i} (b_{1}, b_{2}, ..., b_{n}) - p_{i} (a_{1}, a_{2}, ..., a_{n}) = \sum_{j = 1}^{n} [{(b_{j} + b_{j + 1} + ... + b_{j + i - 1})}^{2} - \\ - {(a_{j} + a_{j + 1} + ... + a_{j + i - 1})}^{2}] . \end{matrix}

Mivel

b_{1} + b_{2} + b_{n} = a_{1} + a_{2} + a_{n}

b_{3} = a_{3}

b_{4} = a_{4}, ..., b_{n - 1} = a_{n - 1}

, elég azokat a

j

-ket vizsgálni, amelyekre

a_{1}

a_{2}

a_{n}

közül egy vagy kettő szerepel az

a_{j}

a_{j + 1}

...

a_{j + i - 1}

számok között; a többire nyilván

\begin{matrix} b_{j} + b_{j + 1} + ... + b_{j + i - 1} = a_{j} + a_{j + 1} + ... + a_{j + i - 1}, \end{matrix}

és így

\begin{matrix} {(b_{j} + b_{j + 1} + ... + b_{j + i - 1})}^{2} - {(a_{j} + a_{j + 1} + ... + a_{j + i - 1})}^{2} = 0. \end{matrix}

Könnyű ellenőrizni, hogy csak négy ilyen

j

van:

\begin{matrix} j = 1, j = 2, j = n - i + 1, j = n - i + 2, \end{matrix}

és így

\begin{matrix} p_{i} (b_{1}, b_{2}, ..., b_{n}) - p_{1} (a_{1}, a_{2}, ..., a_{n}) = {(b_{1} + b_{2} + ... + b_{i})}^{2} - {(a_{1} + a_{2} + ... + a_{i})}^{2} + \\ + {(b_{2} + b_{3} + ... + b_{i + 1})}^{2} - {(a_{2} + a_{3} + ... + a_{i + 1})}^{2} + {(b_{n - i + 1} + b_{n - i + 2} + ... + b_{n})}^{2} - \\ - {(a_{n - i + 1} + a_{n - i + 2} + ... + a_{n})}^{2} + {(b_{n - i + 2} + b_{n - i + 3} + ... + b_{n} + b_{1})}^{2} - \\ - {(a_{n - i + 2} + a_{n - i + 3} + ... + a_{n} + a_{1})}^{2} . \end{matrix}

Mivel

\begin{matrix} b_{1} + b_{2} + ... + b_{i} = (a_{1} + a_{2} + ... + a_{i}) - a_{1}, \\ b_{2} + b_{3} + ... + b_{i + 1} = (a_{2} + a_{3} + ... + a_{i + 1}) + a_{1}, \\ b_{n - i + 1} + b_{n - i + 2} + ... + b_{n} = (a_{n - i + 1} + a_{n - i + 2} + ... + a_{n}) + a_{1} \end{matrix}

és

\begin{matrix} b_{n - i + 2} + b_{n - i + 3} + ... + b_{1} = (a_{n - i + 2} + a_{n - i + 3} + ... + a_{1}) - a_{1}, \end{matrix}

ezért

\begin{matrix} {(b_{1} + b_{2} + ... + b_{i})}^{2} - {(a_{1} + a_{2} + ... + a_{i})}^{2} = a_{1}^{2} - 2 a_{1} (a_{1} + a_{2} + ... + a_{i}) = \\ = - a_{1}^{2} - 2 a_{1} (a_{2} + a_{3} + ... + a_{i}), \\ {(b_{2} + b_{3} + ... + b_{i + 1})}^{2} - {(a_{2} + a_{3} + ... + a_{i + 1})}^{2} = a_{1}^{2} + 2 a_{1} (a_{2} + a_{3} + ... + a_{i + 1}) = \\ = a_{1}^{2} + 2 a_{1} (a_{2} + a_{3} + ... + a_{i}) + 2 a_{i} a_{i + 1}, \\ {(b_{n - i + 1} + b_{n - i + 2} + ... + b_{n})}^{2} - {(a_{n - i + 1} + a_{n - i + 2} + ... + a_{n})}^{2} = \\ a_{1}^{2} + 2 a_{1} (a_{n - i + 1} + a_{n - i + 2} + ... + a_{n}) = \\ = a_{1}^{2} + 2 a_{1} (a_{n - i + 2} + a_{n - i + 3} + ... + a_{n}) + 2 a_{1} a_{n - i + 1}, \\ {(b_{n - i + 2} + b_{n - i + 3} + ... + b_{1})}^{2} - {(a_{n - i + 2} + a_{n - i + 3} + ... + a_{1})}^{2} = \\ = a_{1}^{2} - 2 a_{1} (a_{n - i + 2} + a_{n - i + 3} + ... + a_{1}) = - a_{1}^{2} - 2 a_{1} (a_{n - i + 2} + a_{n - i + 3} + ... + a_{n}), \end{matrix}

és így valóban

\begin{matrix} p_{i} (b_{1}, b_{2}, ..., b_{n}) - p_{i} (a_{1}, a_{2}, ..., a_{n}) = 2 a_{1} a_{i + 1} + 2 a_{1} a_{n - i + 1} = 2 a_{1} (a_{i + 1} + a_{n - i + 1}) . \end{matrix}

Ezzel a

p_{i}

polinomokra vonatkozó állításunkat bebizonyítottuk.

Legyen ezután

f (x_{1}, x_{2}, ..., x_{n}) = 2 p_{1} (x_{1}, x_{2}, ..., x_{n}) + \sum_{i = 2}^{n - 2} p_{i} (x_{1}, x_{2}, ..., x_{n})

(ha

n = 3

, akkor

\sum_{i = 2}^{n - 2} p_{i} (x_{1}, x_{2}, ..., x_{n}) = 0

).
Mivel

p_{i} (x_{1}, x_{2}, ..., x_{n}) ≧ 0

, hisz négyzetek összege, ezért nyilván

\begin{matrix} f (x_{1}, x_{2}, ..., x_{n}) ≧ 0. \end{matrix}

Az eddigiek alapján

\begin{matrix} f (b_{1}, b_{2}, ..., b_{n}) - f (a_{1}, a_{2}, ..., a_{n}) = 2 [p_{1} (b_{1}, b_{2}, ..., b_{n}) - p_{1} (a_{1}, a_{2}, ..., a_{n})] + \\ + \sum_{i = 2}^{n - 2} [p_{i} (b_{1}, b_{2}, ..., b_{n}) - p_{i} (a_{1}, a_{2}, ..., a_{n})] = 4 a_{1} (a_{1} + a_{2} + a_{n}) + \\ + \sum_{i = 2}^{n - 2} 2 a_{1} (a_{i + 1} + a_{n - i + 1}) = 2 a_{1} (2 a_{1} + 2 a_{2} + 2 a_{n} + (a_{3} + a_{4} + ... + a_{n - 1}) + \\ + (a_{n - 1} + a_{n - 2} + ... + a_{3})) = 4 a_{1} (a_{1} + a_{2} + ... + a_{n}) . \end{matrix}

Mivel

a_{1} < 0

és

a_{1} + a_{2} + ... + a_{n} > 0

f (b_{1}, b_{2}, ..., b_{n}) - f (a_{1}, a_{2}, ..., a_{n}) < 0

, azaz

f (a_{1}, a_{2}, ..., a_{n}) > (b_{1}, b_{2}, ..., b_{n})

.
Az

f

polinom tehát a szám

n

-esekhez úgy rendel természetes számokat, hogy ezek a számok minden "művelet'' során csökkennek (ezt az

x = a_{n}

y = a_{1}

z = a_{2}

esetben láttuk be; az indexelés ciklikus cseréjével azonban a többi esetben is hasonlóan mutatható meg).
Sikerült tehát a szám

n

-esekhez megfelelő nem negatív egészeket rendelnünk és ezzel igazoltuk állításunkat.