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 sorozatot blokkokra: a nulladik blokk álljon -ből, az első legyen , a másodikhoz tartozzon . Általában az -dik blokk az elemtől tartalmazza a sorozat elemeit az elemmel bezárólag. (Ha , akkor a blokk értelemszerűen csak -ig tartalmazza a sorozat elemeit.) Tegyük fel, hogy blokkból áll az sorozat, vagyis az utolsó blokk a -adik. Legyen -ra az -edik blokk legkisebb eleme, és legyen . A blokkok és az -k megválasztása miatt , ezért | | ahol az utolsó egyenlőtlenség definíciójából és abból következik, hogy az -edik blokk éppen db elemet tartalmaz. Azt kaptuk tehát, hogy az szorzat legfeljebb -szerese az -edik blokkban álló elemek összegének, tehát e szorzatok összege is legfeljebb -szerese az első blokk összegének: | |
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 -nél, az garantálná, hogy létezik a feltételt teljesítő sorozat. Másképpen fogalmazva: állítsuk elő az sorozatot véletlenszerűen úgy, hogy az indexek mindegyikét (egymástól függetlenül) valószínűséggel választjuk ki (a -t és az -et mindenképpen ki kell választanunk), és vizsgáljuk meg az így előállított véletlen összeg várható értékét. Ha a várható érték -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 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 sorozatot véletlenszerűen úgy, hogy az indexet tetszőleges eseté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: | | Megjegyezzük, hogy az és az indexeket biztosan ki kell választanunk, ennek megfelelően . Vizsgáljuk meg, hogy valamely esetén az 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 és indexeket kiválasszuk, a közbülső indexek közül viszont egyet sem. Az tag előfordulásának valószínűsége tehát | | a teljes összeg várható értéke pedig
Ha , akkor
Ha pedig , akkor
Ezeket a becsléseket beírva (2)-be,
és | |
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 -nél kisebb. |