Kezdőlap


Feladat:	F.3221	Korcsoport: 14-15	Nehézségi fok: nehéz
Megoldó(k):	Babos Attila , Bárány Kristóf , Csizmadia László , Dancsó Zsuzsanna , Devecsery András , Gyenes Zoltán , Hangya Balázs , Harangi Viktor , Juhász András , Keszegh Balázs , Kiss András Péter , Máthé András , Naszódi Gergely , Pap Júlia , Patakfalvi Zsolt , Szabadka Zoltán , Terpai Tamás , Végh A. László
Füzet:	1998/december, 538 - 539. oldal		PDF \| MathML
Témakör(ök):	Számelrendezések, Szélsőérték-feladatok, Természetes számok, Feladat
Hivatkozás(ok):	Feladatok: 1998/március: F.3221

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.

a) Legyen az $A_{j}$ csúcshoz írt szám $a_{j}$ , továbbá $b_{j} = {max}_{}^{} (a_{j + 1}, a_{j})$ és $c_{j} = {min}_{}^{} (a_{j + 1}, a_{j})$ . Ekkor ( $a_{n + 1} = a_{1}$ megállapodással):

\begin{matrix} \sum_{j = 1}^{n} | a_{j + 1} - a_{j} | = \sum_{j = 1}^{n} b_{j} - \sum_{j = 1}^{n} c_{j} . \end{matrix}

b_{1}

b_{2}

...

b_{n}

c_{1}

c_{2}

...

c_{n}

számok között az 1, 2,

...

n

számok mindegyike pontosan kétszer fordul elő.
Ezért páros

n

esetén:

\begin{matrix} \begin{matrix} \sum_{j = 1}^{n} b_{j} \leq 2 [(\frac{n}{2} + 1) + (\frac{n}{2} + 2) + ... + n] \\ és \\ \sum_{j = 1}^{n} c_{j} \geq 2 [1 + 2 + ... + \frac{n}{2}] . \end{matrix} \end{matrix}

Tehát

\begin{matrix} \begin{matrix} \sum_{j = 1}^{n} b_{j} - \sum_{j = 1}^{n} c_{j} \leq 2 [(\frac{n}{2} + 1) + (\frac{n}{2} + 2) + ... + n] - 2 [1 + 2 + ... + \frac{n}{2}] = \\ = 2 \cdot \frac{1}{2} \cdot \frac{n}{2} \cdot (\frac{n}{2} + 1 + n) - 2 \cdot \frac{1}{2} \cdot \frac{n}{2} \cdot (1 + \frac{n}{2}) = \frac{n^{2}}{2} . \end{matrix} \end{matrix}

Hasonlóan páratlan

n

-re:

\begin{matrix} \begin{matrix} \sum_{j = 1}^{n} b_{j} - \sum_{j = 1}^{n} c_{j} \leq (2 [\frac{n + 1}{2} + 1 + \frac{n + 1}{2} + 2 + ... + n] + \frac{n + 1}{2}) - \\ - (2 [1 + 2 + ... + \frac{n + 1}{2} - 1] + \frac{n + 1}{2}) = \frac{n^{2} - 1}{2} \end{matrix} \end{matrix}

Megmutatjuk, hogy mindkét esetben állhat egyenlőség.
Az első esetben megfelel, ha a körre felírjuk a számokat az 1,

\frac{n}{2} + 1

, 2,

\frac{n}{2} + 2

...

\frac{n}{2}

n

sorrendben, a második esetben pedig az 1,

\frac{n + 3}{2}

, 2,

\frac{n + 5}{2}

...

\frac{n - 1}{2}

n

\frac{n + 1}{2}

sorrend megfelelő.
b) Ha

n

páros, úgy maximális összeget kapunk, ha az

\frac{n}{2}

-nél nem nagyobb és az

\frac{n}{2}

-nél nagyobb számok váltogatják egymást: a

\sum_{j = 1}^{n} b_{j} - \sum_{j = 1}^{n} c_{j}

összegben ugyanis csak ekkor szerepel minden

\frac{n}{2}

-nél nagyobb szám

+ 2

, és minden

\frac{n}{2}

-nél nem nagyobb szám

- 2

együtthatóval. A lehetőségek száma tehát:

\begin{matrix} n \cdot \frac{n}{2} (\frac{n}{2} - 1) (\frac{n}{2} - 1) (\frac{n}{2} - 2) (\frac{n}{2} - 2) ... 1 \cdot 1 = 2 {((\frac{n}{2})!)}^{2}; \end{matrix}

ugyanis az

A_{1}

-nél lévő számra

n

lehetőség van, ezek után az

A_{2}

-nél levőre

\frac{n}{2}

, az

A_{3}

-nál levőre

\frac{n}{2} - 1

és így tovább.
Ha

n

páratlan, egy kicsit másképpen számolunk. A

\sum_{j = 1}^{n} b_{j} - \sum_{j = 1}^{n} c_{j} = \frac{n^{2} - 1}{n}

egyenlőség akkor áll fenn, ha az elrendezésben minden

\frac{n + 1}{2}

-nél kisebb számnak

\frac{n + 1}{2}

-nél nagyobb szomszédja van és fordítva, továbbá

\frac{n + 1}{2}

egyik szomszédja nagyobb, a másik kisebb, mint

\frac{n + 1}{2}

. Így a megfelelő elhelyezések száma

2 n {[(\frac{n - 1}{2})!]}^{2}

; ugyanis az

\frac{n + 1}{2}

elhelyezésre

n

lehetőségünk van, ezután pozitív irányban körüljárva a kört, a szomszédjára

n - 1

lehetőség van, majd pedig rendre

\frac{n - 1}{2}

\frac{n - 1}{2} - 1

\frac{n - 1}{2} - 1

\frac{n - 1}{2} - 2

\frac{n - 1}{2} - 2

...

, 1, 1 a lehetőségek száma.

Gyenes Zoltán (Budapest, ELTE Apáczai Csere J. Gimn., 10. o.t.) dolgozata alapján