Kezdőlap


Feladat:	N.117	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Bérczi Gergely , Braun Gábor , Frenkel Péter , Gerbicz Róbert , Juhász András , Kun Gábor , Lippner Gábor , Mátrai Tamás , Pap Gyula , Szabó Jácint
Füzet:	1997/május, 289 - 290. oldal		PDF \| MathML
Témakör(ök):	Számsorozatok, Indirekt bizonyítási mód, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1996/november: N.117

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.

Az állítást $n$ szerinti teljes indukcióval bizonyítjuk.
Az $n = 1$ esetben az állítás igaz, mert $a_{1} = 1$ és $1 \leq a_{2} \leq 2$ .
Tegyük fel, hogy $n < m$ esetén igaz az állítás, és tegyük fel indirekt, hogy $n = m$ esetén nem, azaz léteznek olyan $a_{1}$ , $...$ , $a_{2^{m}}$ pozitív egészek, amelyekre $a_{k} \leq k$ , de közülük csak legfeljebb $m$ hosszúságú monoton növő részsorozat választható ki.
Legyen $1 \leq x \leq 2^{m}$ , és jelentse $h (x)$ azt, hogy az $x$ szám hányszor szerepel az
$a_{1}$ , $...$ , $a_{2^{m}}$ számok között. Nyilván $h (1) \leq m$ , mert ellenkező esetben lenne $m + 1$ darab 1-es a sorozatban.
Legyen most $2^{l} < x \leq 2^{l + 1}$ . Az $a_{1}$ , $...$ , $a_{2^{m}}$ számok mind kisebbek $x$ -nél, és közülük az indukciós feltevés szerint kiválasztható $l + 1$ hosszúságú, monoton növő részsorozat. Ezekhez hozzávéve $h (x)$ darab $x$ -et, egy $l + 1 + h (x)$ hosszúságú monoton növő sorozatot kapunk; ezért az indirekt feltevés szerint $l + 1 + h (x) \leq m$ , tehát $h (x) \leq m - l - 1$ .
Ha összeszámoljuk, hogy az $a_{1}$ , $...$ , $a_{2^{l}}$ sorozatban hány 1-es, 2-es stb. elem szerepel, akkor mindegyik $a_{k}$ -t egyszer számoljuk, ezért a $h (x)$ -ek összege éppen $2^{m}$ . Ez és az előbbi becslések alapján

\begin{matrix} \begin{matrix} 2^{m} = \sum_{x = 1}^{2^{m}} h (x) = h (1) + \sum_{l = 0}^{m - 1} \sum_{2^{l} < x \leq 2^{l + 1}}^{} h (x) \leq m + \sum_{l = 0}^{m - 1} (2^{l + 1} - 2^{l}) (m - l - 1) = \\ = m - 2^{0} \cdot (m - 1) + 2^{m} \cdot 0 + \sum_{l = 1}^{m - 1} 2^{l} \cdot ((m - l) - (m - l - 1)) = 1 + \sum_{l = 1}^{m - 1} 2^{l} = 2^{m} - 1, \end{matrix} \end{matrix}

ami ellentmondás.

Megjegyzés. A feladat állítása éles; létezik olyan

a_{1}

a_{2}

...

pozitív egész számokból álló sorozat, hogy

a_{k} \leq k

, és tetszőleges

n

pozitív egészre az

a_{1}

...

a_{2^{n} - 1}

számok közül nem választható ki

n + 1

hosszúságú monoton növő részsorozat.
Legyen

a_{n} = 2^{l + 1} - n

, ha

2^{l} \leq n < 2^{l + 1}

\begin{matrix} a_{1} = 1, a_{2} = 2, a_{3} = 1, a_{4} = 4, a_{5} = 3, a_{6} = 2, a_{7} = 1, ... \end{matrix}

Ekkor az

(a_{1})

(a_{2}, a_{3})

(a_{4}, a_{5}, a_{6} a_{7})

...

(a_{2^{n - 1}}, a_{2^{n - 1} + 1}, ..., a_{2^{n} - 1})

részsorozatok szigorúan monoton fogynak, emiatt egy monoton növő részsorozat mindegyikből legfeljebb egy elemet, összesen legfeljebb

n

elemet tartalmazhat.
A megoldás kis módosításával igazolható, hogy ez az egyetlen ilyen példa.

Több dolgozat alapján