Az A. 394. feladat (2006. február)

A. 394. Bizonyítsuk be, hogy ha a₁,a₂,...,a_N nemnegatív valós számok, és nem mindegyikük 0, akkor létezik olyan k pozitív egész szám, és léteznek olyan $1=n_0<n_1<\ldots<n_k=N+1$ egészek, amelyekre

$n_1a_{n_0}+n_2a_{n_1}+\ldots+n_ka_{n_{k-1}}<3(a_1+a_2+\dots+a_N).$

A 2005. évi Kürschák-verseny 1. feladata nyomán

(5 pont)

A beküldési határidő 2006. március 16-án LEJÁRT.

1. megoldás. Módosítsuk a feltételt úgy, hogy az n_k=N+1 feltétel helyett azt írjuk, hogy n_k-1 $\le$ N<a_k. Ha ilyen tulajdonságú sorozatot találunk, az is elég, mert az utolsó elemet (N+1)-re csökkenthetjük.

Az n₀,n₁,... sorozatot válasszuk a következőképpen. Legyen n₀=1. Az n₁ indexet válasszuk a 2 és a 3 közül azonos, 1/2-1/2 valószínűséggel. Az n₂ indexet válasszuk véletlenszerűen a 4,5,6,7 számok közül. Általában válasszuk n_i-t a 2ⁱ,2ⁱ+1,...,2ⁱ⁺¹-1 számok közül úgy, hogy a valószínűségek egyenlők legyenek. A sorozatot addig folytassuk, amíg egy N-nél nagyob számot nem kapunk; ez az elem legyen n_k.

Most tekintsük az n₁a_n₀+...+n_ka_{n_k-1} összeget. Ez ma_n alakú tagokból áll, ahol 2ⁱ $\le$ n<2ⁱ⁺¹ és 2ⁱ⁺¹ $\le$ m<2ⁱ⁺² valamilyen i-re. Egy ilyen tag kiválasztásának valószínűsége $\frac{1}{2^i}\cdot\frac{1}{2^{i+1}}$ . Ezért a teljes összeg várható értéke:

$E( n_1a_{n_0}+\dots+n_ka_{n_{k-1}} ) = \sum_{i=0}^{[\log_2N]}\sum_{n=2^i}^{\min(2^i-1,N)}\sum_{m=2^{i+1}}^{2^{i+2}-1} \frac{1}{2^i}\cdot\frac{1}{2^{i+1}}\cdot ma_n =$

$= \sum_{i=0}^{[\log_2N]}\sum_{n=2^i}^{\min(2^i-1,N)} \frac{a_n}{2^{2i+1}}\sum_{m=2^{i+1}}^{2^{i+2}-1}m = \sum_{i=0}^{[\log_2N]}\sum_{n=2^i}^{\min(2^i-1,N)} \frac{a_n}{2^{2i+1}}\cdot2^{i+1}\frac{2^{i+1}+(2^{i+2}-1)}{2}<$

$< \sum_{i=0}^{[\log_2N]}\sum_{n=2^i}^{\min(2^i-1,N)} \frac{a_n}{2^{2i+1}}\cdot3\cdot2^{2i+1}=3\sum_{n=1}^Na_n.$

Mivel a várható érték kisebb, mint $3\sum a_n$ , létezik olyan eset, amikor a kapott összeg elegendően kicsi.

2. megoldás. Ismét véletlenszerűen választunk indexsorozatot.

Az egyszerűbb számolás kedvéért definiáljuk a következő függvényt. Legyen f(x)=a_n, ha n $\le$ x<n+1, és legyen f(x)=0, ha x $\ge$ N+1.

Válasszunk egy t $\in$ [0,1] véletlen valós számot, egyenletes valószínűséggel. Legyen n₀=1, és i $\ge$ 1 esetén $n_i=\left[2\cdot e^{i-1+t}\right]$ . A sorozat ismét az első, N-nél nagyobb elemig tartson. Azt is mondhatjuk, hogy az a_n sorzoatot kiegészítjük végtelen sok 0-val, és az indexelés végtelenig megy.

$E\left(\sum_{i=1}^\infty n_ia_{n_{i-1}}\right) \le E(n_1)\cdot a_0 + E \left(\sum_{i=2}^\infty2\cdot e^{i-1+t}f(2\cdot e^{i-2+t})\right)=$

$= E(n_1)\cdot a_0 + \sum_{i=2}^\infty\int_0^1 \big(2\cdot e^{i-1+t}f(2\cdot e^{i-2+t})\big)dt=$

$= E(n_1)\cdot a_0 + \int_0^\infty 2\cdot e^{u+1}f(2\cdot e^u)du = E(n_1)\cdot a_0 + e\int_2^\infty f(x)dx =$

$= E(n_1)\cdot a_0 + e\sum_{n=2}^Na_n.$

Az n₁ értéke 2, ha $t<\ln\frac32$ ; n₁=3, ha $\ln\frac32\le t<\ln\frac42$ ; n₁=4, ha $\ln\frac42\le t<\ln\frac52$ ; végül n₁=5, ha $\ln\frac52\le t<1$ . Ezért n-1 várható értéke:

$E(n_1)= \left(\ln\frac32\right)\cdot2 + \left(\ln\frac42-\ln\frac32\right)\cdot3 + \left(\ln\frac52-\ln\frac42\right)\cdot4 + \left(1-\ln\frac52\right)\cdot5 \approx 2,985<3.$

Tehát

$E\left(\sum_{i=1}^\infty n_ia_{n_{i-1}}\right) < 3a_1 + e(a_2+\dots+a_N),$

és mindig létezik olyan 1=n₀<n₁<...<n_k=N+1 indexsorozat, amire

n₁a_n₀+n₂a_n₁+...+n_ka_{n_k-1}<3a₁+e(a₂+a₃+...+a_N).

Statisztika:

3 dolgozat érkezett.

5 pontot kapott: Erdélyi Márton, Paulin Roland.

0 pontot kapott: 1 versenyző.

A KöMaL 2006. februári matematika feladatai

3 dolgozat érkezett.
5 pontot kapott:	Erdélyi Márton, Paulin Roland.
0 pontot kapott:	1 versenyző.

Már regisztráltál?
Új vendég vagy?