Kezdőlap


Feladat:	2010. évi Nemzetközi Matematika Diákolimpia 23. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Éles András
Füzet:	2010/október, 392 - 393. oldal		PDF \| MathML
Témakör(ök):	Számsorozatok, Teljes indukció módszere
Hivatkozás(ok):	Feladatok: 2010/szeptember: 2010. évi Nemzetközi Matematika Diákolimpia 23. 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.

Éles András megoldása. Legyen $m \geq 2$ , és $1 \leq i_{1}, i_{2}, ..., i_{k} \leq s$ tetszőleges $m$ darab pozitív egész, melyek összege $n$ . Ha ezek teljesítenek egy plusz feltételt, akkor az

\begin{matrix} a_{i_{1}} + a_{i_{2}} + ... + a_{i_{m}} \end{matrix}

összeget

n

-re képzett összegnek nevezzük. A plusz feltétel az, hogy az

i_{j}

számok közül valamelyik kettő összege nagyobb, mint

s

(például

i_{1} + i_{2} > s

, viszont

i_{1} + i_{1} > s

még nem elégséges feltétel). Ezt a definíciót és a plusz feltétel eredetét a most következő kulcsfontosságú lemma és annak bizonyítása fogja megmagyarázni.

Lemma. Az

n

-re képzett összegek maximuma

a_{n}

minden

n > s

esetén.

Ezt

n

-re indukcióval igazoljuk. Ha

k > s

, akkor

n > k

és az indukciós feltevés értelmében

a_{k}

helyébe beírhatunk egy

k

-ra képzett összeget. Ugyanígy járunk el

a_{n - k}

-val. Az indexek összege

n

lesz, a plusz feltétel pedig teljesül, hiszen

a_{k}

vagy

a_{n - k}

felírásából származik két megfelelő indexű tag, ha

k > s

vagy

n - k > s

(különben pedig ők maguk a két tag). Tehát

a_{n}

felírható egy

n

-re képzett összegként.
Már csak azt kell igazolni, hogy

a_{n}

fölső becslés minden

n

-re képzett összegre. Feltehető a plusz feltétel miatt, hogy

i_{1} + i_{2} > s

. Alkalmazva a sorozat képzési szabályát mindig a legelső tagra (amelynek indexe mindenütt nagyobb, mint

s

\begin{matrix} a_{n} & = a_{i_{1} + i_{2} + ... + i_{k}} \geq a_{i_{1} + i_{2} + ... + i_{k - 1}} + a_{k} \geq a_{i_{1} + ... + i_{k - 2}} + a_{k - 1} + a_{k} \geq ... \geq \\ \geq a_{i_{1} + i_{2}} + a_{i_{3}} + ... + a_{k} \geq a_{i_{1}} + a_{i_{2}} + ... + a_{i_{k}} . \end{matrix}

Ezzel a lemmát igazoltuk.
Legyen

l

olyan pozitív egész, melyre

1 \leq l \leq s

és ezen belül

\frac{a_{l}}{l}

maximális! A megoldás azon észrevételen alapszik, hogy elég nagy

n

-re felírva

a_{n}

-et egy

n

-re képzett összegként, az

a_{l}

-től különböző tagok száma egy bizonyos határ alá szorítható. Ha ugyanis

t \neq l

és van

l + 2

darab

a_{t}

az összegben, akkor

l

darab

a_{t}

lecserélhető

t

darab

a_{l}

-re, az összeg ekkor nem csökken, hiszen

\begin{matrix} l \cdot a_{t} = l t \cdot \frac{a_{t}}{t} \leq l t \cdot \frac{a_{l}}{l} = t \cdot a_{l} . \end{matrix}

Így egy legalább akkora, tehát ismét

a_{n}

-nel egyenlő

n

-re képzett összeget kaptunk. (azért a

+ 2

darab

a_{t}

, hogy az eltűnő indexből maradjon legalább kettő, így ne sérüljön a plusz feltétel). Ezt az eljárást addig végezzük, míg lehet, ily módon

a_{n}

már olyan

n

-re képzett összegként áll majd elő, ahol minden

t

1 \leq t \leq s

t \neq l

esetén

a_{t}

az összegben legfeljebb

(l + 1)

-szer szerepel.
Következő választásunk

\begin{matrix} N = (1 + 2 + ... + s) (l + 1) + 2 l + 1, \end{matrix}

ugyanis

n \geq N

esetén

a_{n}

fenti felírásában legalább 3 darab

a_{l}

lesz jelen, hiszen a többi index összege maximum

N - 2 l - 1

. Az egyik

a_{l}

-t törölve marad legalább kettő (így a plusz feltétel megint nem sérül), az indexek összege

n - l

lesz, tehát egy

(n - l)

-re képzett összeg,

S_{n - l}

marad hátra. De akkor, a lemma és a sorozat képzése alapján

\begin{matrix} a_{n} = a_{l} + S_{n - l} \leq a_{l} + a_{n - l} \leq a_{n} . \end{matrix}

Ez végig egyenlőség. Tehát

l

-nek és

N

-nek a fenti választásaival

a_{n} = a_{l} + a_{n - l}

minden

n \geq N

esetén. (A gondolatmenet finomításával

N

javítható.)