Feladat: 2005. évi Kürschák matematikaverseny 1. feladata Korcsoport: - Nehézségi fok: -
Füzet: 2006/február, 68 - 70. oldal  PDF file
Témakör(ök): Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 2006/február: 2005. évi Kürschák matematikaverseny 1. feladata

Legyen N>1 és legyenek a1,a2,...,aN olyan nemnegatív valós számok, amelyek összege legfeljebb 500. Bizonyítandó, hogy létezik olyan k1 egész szám és léteznek olyan 1=n0<n1<...<nk=N egészek, amelyekre teljesül, hogy
i=1kniani-1<2005.

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 (an) sorozatot blokkokra: a nulladik blokk álljon a1-ből, az első legyen a2,a3, a másodikhoz tartozzon a4,...,a7. Általában az i-dik blokk az a2i elemtől tartalmazza a sorozat elemeit az a2i+1-1 elemmel bezárólag.

 
 
(Ha 2i+1-1>N, akkor a blokk értelemszerűen csak aN-ig tartalmazza a sorozat elemeit.) Tegyük fel, hogy k+1 blokkból áll az (an) sorozat, vagyis az utolsó blokk a k-adik. Legyen i<k-ra ani az i-edik blokk legkisebb eleme, és legyen nk=N. A blokkok és az ni-k megválasztása miatt ni<2i+1, ezért
niani-12i+1ani-1=42i-1ani-14(a2i-1+...+a2i-1),
ahol az utolsó egyenlőtlenség ani-1 definíciójából és abból következik, hogy az (i-1)-edik blokk éppen 2i-1 db elemet tartalmaz. Azt kaptuk tehát, hogy az niani-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:
i=1kniani-1<4i=12k-1ai4i=1Nai4500<2005.

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 n0,...,nk sorozatot véletlenszerűen úgy, hogy az 2,3,...,N-1 indexek mindegyikét (egymástól függetlenül) 12 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 niani-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 niani-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 n0,...,nk sorozatot véletlenszerűen úgy, hogy az n indexet tetszőleges 1nN esetén pn 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:
pn={2n+1,ha  1n<N;1,ha  n=N.
Megjegyezzük, hogy az 1 és az N indexeket biztosan ki kell választanunk, ennek megfelelően p1=pN=1.
Vizsgáljuk meg, hogy valamely 1n<mN esetén az man 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 man tag előfordulásának valószínűsége tehát
pn(1-pn+1)...(1-pm-1)pm,
a teljes összeg várható értéke pedig
E(i=1kniani-1)=1n<mNpn(1-pn+1)...(1-pm-1)pmman=(2)=n=1N-1(m=n+1Npn(1-pn+1)...(1-pm-1)pmm)an.

Ha m<N, akkor
pn(1-pn+1)...(1-pm-1)pmm==2n+1nn+2n+1n+3...m-2m2m+1m==4n(m-1)(m+1)<4n(m-1)m=4nm-1-4nm.
Ha pedig m=N, akkor
pn(1-pn+1)...(1-pm-1)pmm==2n+1nn+2n+1n+3...N-2N1N=2nN-1.


Ezeket a becsléseket beírva (2)-be,
m=n+1Npn(1-pn+1)...(1-pm-1)pmmm=n+1N-1(4nm-1-4nm)+2nN-1=(4nn-4nN-1)+2nN-1<4,


és
E(i=1kniani-1)<n=1N-14an4n=1Nan2000.

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.