Kezdőlap


Feladat:	Gy.3185	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Kunszenti-Kovács Dávid , Máthé András , Mecz Balázs , Pozsár Balázs , Székelyhidi Gábor
Füzet:	1998/december, 526. oldal		PDF \| MathML
Témakör(ök):	Kombinatorikai leszámolási problémák, Szélsőérték-feladatok, Számelrendezések, Gyakorlat
Hivatkozás(ok):	Feladatok: 1998/február: Gy.3185

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) A csúcsokra felírt számokat jelöljük $a_{1}$ , $a_{2}$ , $...$ , $a_{n}$ -nel. Ekkor a bizonyítandó állítás:

\begin{matrix} | a_{1} - a_{2} | + | a_{2} - a_{3} | + ... + | a_{n - 1} - a_{n} | + | a_{n} - a_{1} | \geq 2 n - 2. \end{matrix}

Legyen

a_{1} = 1

és

a_{j} = n

. Ekkor az ismert

| a + b | \leq | a | + | b |

alapján

\begin{matrix} \begin{matrix} | a_{1} - a_{2} | + | a_{2} - a_{3} | + ... + | a_{j - 1} - a_{j} | & \geq | a_{1} - a_{j} | = n - 1 & (1) \\ | a_{j} - a_{j + 1} | + | a_{j + 1} - a_{j + 2} | + ... + | a_{n} - a_{1} | & \geq | a_{j} - a_{1} | = n - 1. & (2) \end{matrix} \end{matrix}

Ezt a két egyenlőtlenséget összeadva kapjuk a bizonyítandó állítást.
b) A bizonyítandó egyenlőtlenségben pontosan akkor van egyenlőség, amikor (1)-ben és (2)-ben egyaránt egyenlőség van. Ehhez az kell, hogy (1)-ben (és (2)-ben is) az abszolútértéken belüli különbségek mindegyikének ugyanaz legyen az előjele. Mivel

a_{1} = 1

(tehát a legkisebb szám), azért ebből következik, hogy

a_{1} < a_{2} < a_{3} < ... < a_{j}

, és mivel

a_{j} = n

(a legnagyobb), azért

a_{j} > a_{j + 1} > ... > a_{n}

. Tehát

\begin{matrix} a_{1} < a_{2} < ... < a_{j}, a_{j} > a_{j + 1} > a_{j + 1} > ... > a_{n} . \end{matrix}

Ha azt eldöntjük, hogy mely számok kerülnek

a_{1} = 1

és

a_{j} = n

közé, akkor az egyenlőtlenségek miatt a számokat már csak egyféleképpen helyezhetjük el. Ez

2^{n - 2}

lehetőség.

Székelyhidi Gábor (Kuwait, New English School, 11. o.t.)

Megjegyzés. A b) kérdésre

2^{n - 3}

2^{n - 2}

vagy

n \cdot 2^{n - 2}

a válasz attól függően, hogy a tükrözéssel, illetve elforgatással egymásba vihető elrendezéseket megkülönböztetjük-e. Mind a három variációt elfogadtuk.
Megjegyzés. A példát Hajnal Péter: Elemi kombinatorikai feladatok (Polygon) c. könyvéből vettük!