Kezdőlap


Feladat:	2005. évi Kürschák matematikaverseny 1. feladata	Korcsoport: -	Nehézségi fok: -
Füzet:	2006/február, 68 - 70. oldal		PDF \| MathML
Témakör(ök):	Kürschák József (korábban Eötvös Loránd), Matematika, Számsorozatok
Hivatkozás(ok):	Feladatok: 2006/február: 2005. évi Kürschák matematikaverseny 1. 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.

I. megoldás. Osszuk az $(a_{n})$ sorozatot blokkokra: a nulladik blokk álljon $a_{1}$ -ből, az első legyen $a_{2}, a_{3}$ , a másodikhoz tartozzon $a_{4}, ..., a_{7}$ . Általában az $i$ -dik blokk az $a_{2^{i}}$ elemtől tartalmazza a sorozat elemeit az $a_{2^{i + 1} - 1}$ elemmel bezárólag.

(Ha

2^{i + 1} - 1 > N

, akkor a blokk értelemszerűen csak

a_{N}

-ig tartalmazza a sorozat elemeit.) Tegyük fel, hogy

k + 1

blokkból áll az

(a_{n})

sorozat, vagyis az utolsó blokk a

k

-adik. Legyen

i < k

-ra

a_{n_{i}}

i

-edik blokk legkisebb eleme, és legyen

n_{k} = N

. A blokkok és az

n_{i}

-k megválasztása miatt

n_{i} < 2^{i + 1}

, ezért

\begin{matrix} n_{i} a_{n_{i - 1}} \leq 2^{i + 1} \cdot a_{n_{i - 1}} = 4 \cdot 2^{i - 1} a_{n_{i - 1}} \leq 4 \cdot (a_{2^{i - 1}} + ... + a_{2^{i} - 1}), \end{matrix}

ahol az utolsó egyenlőtlenség

a_{n_{i - 1}}

definíciójából és abból következik, hogy az

(i - 1)

-edik blokk éppen

2^{i - 1}

db elemet tartalmaz. Azt kaptuk tehát, hogy az

n_{i} a_{n_{i - 1}}

szorzat legfeljebb

4

-szerese az

(i - 1)

-edik blokkban álló elemek összegének, tehát e szorzatok összege is legfeljebb

4

-szerese az első

k

blokk összegének:

\begin{matrix} \sum_{i = 1}^{k} n_{i} a_{n_{i - 1}} < 4 \cdot \sum_{i = 1}^{2^{k} - 1} a_{i} \leq 4 \cdot \sum_{i = 1}^{N} a_{i} \leq 4 \cdot 500 < 2005. □ \end{matrix}

Több versenyző is próbálkozott a feladatban szereplő összeg lehetséges értékeinek átlagolásával. Ha ugyanis ez az átlag kisebb lenne

2005

-nél, az garantálná, hogy létezik a feltételt teljesítő sorozat. Másképpen fogalmazva: állítsuk elő az

n_{0}, ..., n_{k}

sorozatot véletlenszerűen úgy, hogy az

2,3, ..., N - 1

indexek mindegyikét (egymástól függetlenül)

\frac{1}{2}

valószínűséggel választjuk ki (a

0

-t és az

N

-et mindenképpen ki kell választanunk), és vizsgáljuk meg az így előállított

\sum n_{i} a_{n_{i - 1}}

véletlen összeg várható értékét. Ha a várható érték

2005

-nél kisebb, akkor ez biztosítja, hogy az állítás igaz.
Ez az ötlet ‐ ebben a formában ‐ nem vezethet eredményre, mert

\sum n_{i} a_{n_{i - 1}}

várható értéke tetszőlegesen nagy lehet. Az egyes indexek kiválasztási valószínűségének szerencsésebb megválasztásával azonban a feladat megoldható.

II. megoldás. Készítsük el az

n_{0}, ..., n_{k}

sorozatot véletlenszerűen úgy, hogy az

n

indexet tetszőleges

1 \leq n \leq N

esetén

p_{n}

valószínűséggel választjuk ki, és legyen az egyes indexek kiválasztása egymástól független.
A valószínűségeket a következőképpen válasszuk meg:

\begin{matrix} p_{n} = {\begin{matrix} \frac{2}{n + 1}, & ha 1 \leq n < N; \\ 1, & ha n = N . \end{matrix} \end{matrix}

Megjegyezzük, hogy az

1

és az

N

indexeket biztosan ki kell választanunk, ennek megfelelően

p_{1} = p_{N} = 1

.
Vizsgáljuk meg, hogy valamely

1 \leq n < m \leq N

esetén az

m a_{n}

kifejezés milyen valószínűséggel szerepel az (1) bal oldalán álló összeg tagjai között. Ennek szükséges és elégséges feltétele, hogy az

n

és

m

indexeket kiválasszuk, a közbülső indexek közül viszont egyet sem. Az

m a_{n}

tag előfordulásának valószínűsége tehát

\begin{matrix} p_{n} (1 - p_{n + 1}) \cdot ... \cdot (1 - p_{m - 1}) p_{m}, \end{matrix}

a teljes összeg várható értéke pedig

\begin{matrix} E (\sum_{i = 1}^{k} n_{i} a_{n_{i - 1}}) & = \sum_{1 \leq n < m \leq N} p_{n} (1 - p_{n + 1}) \cdot ... \cdot (1 - p_{m - 1}) p_{m} \cdot m a_{n} = & (2) \\ = \sum_{n = 1}^{N - 1} (\sum_{m = n + 1}^{N} p_{n} (1 - p_{n + 1}) \cdot ... \cdot (1 - p_{m - 1}) p_{m} \cdot m) a_{n} . \end{matrix}

m < N

, akkor

\begin{matrix} p_{n} (1 - p_{n + 1}) \cdot ... \cdot (1 - p_{m - 1}) p_{m} \cdot m = \\ = \frac{2}{n + 1} \cdot \frac{n}{n + 2} \cdot \frac{n + 1}{n + 3} \cdot ... \cdot \frac{m - 2}{m} \cdot \frac{2}{m + 1} \cdot m = \\ = \frac{4 n}{(m - 1) (m + 1)} < \frac{4 n}{(m - 1) m} = \frac{4 n}{m - 1} - \frac{4 n}{m} . \end{matrix}

Ha pedig

m = N

, akkor

\begin{matrix} p_{n} (1 - p_{n + 1}) \cdot ... \cdot (1 - p_{m - 1}) p_{m} \cdot m = \\ = \frac{2}{n + 1} \cdot \frac{n}{n + 2} \cdot \frac{n + 1}{n + 3} \cdot ... \cdot \frac{N - 2}{N} \cdot 1 \cdot N = \frac{2 n}{N - 1} . \end{matrix}

Ezeket a becsléseket beírva (2)-be,

\begin{matrix} \sum_{m = n + 1}^{N} p_{n} (1 - p_{n + 1}) \cdot ... \cdot (1 - p_{m - 1}) p_{m} \cdot m \leq \\ \leq \sum_{m = n + 1}^{N - 1} (\frac{4 n}{m - 1} - \frac{4 n}{m}) + \frac{2 n}{N - 1} = (\frac{4 n}{n} - \frac{4 n}{N - 1}) + \frac{2 n}{N - 1} < 4, \end{matrix}

és

\begin{matrix} E (\sum_{i = 1}^{k} n_{i} a_{n_{i - 1}}) < \sum_{n = 1}^{N - 1} 4 a_{n} \leq 4 \sum_{n = 1}^{N} a_{n} \leq 2000. \end{matrix}

Mivel a várható érték a lehetséges összegeknek a ‐ valószínűségük szerint ‐ súlyozott átlaga, a lehetséges összegek között biztosan létezik

2000

-nél kisebb.

□