Feladat: B.4854 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Sulan Ádám 
Füzet: 2017/november, 472. oldal  PDF file
Témakör(ök): Feladat, Teljes indukció módszere, Számhalmazok
Hivatkozás(ok):Feladatok: 2017/február: B.4854

Legyenek a1,a2,...,an valós számok. Tekintsük az ezekből képezett 2n-1 (nemüres) összeget. Hány lehet ezek közül pozitív?

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.

 
Megoldás. Kiindulási pontként tekintsük a 2n-1,2n-2,...,20=1 számokat. Ezeket alkalmasan előjelezve megmutatjuk, hogy 0-tól 2n-1-ig bármennyi lehet a nemüres összegek közül pozitív.
Először vegyük az a1=-2n-1, a2=-2n-2, ..., an=-20 sorozatot, amelyben a sorozat tagjai mind negatívak, vagyis közülük választva egyetlen pozitív nemüres összeg sincs.
Ha ezután bármely más előjelezés mellett nézzük a nemüres összegeket, akkor egy ilyennek az előjele csak a legnagyobb abszolút értékű tag előjelétől függ, mivel az összes nála kisebb abszolút értékű tag összegének az abszolút értéke kisebb, mint ennek az egynek az abszolút értéke.
Bármely 0 és 2n-1 közötti pozitív egész szám egyértelműen felírható kettes számrendszerben legfeljebb n darab jeggyel. Ha a kettes számrendszerben felírt szám M=2k1+2k2+...+2kp alakú (ahol k1>k2>...>kp), akkor ak1,ak2,...,akp előjelét pozitívnak, az összes többit pedig negatívnak választva pontosan azok az összegek lesznek pozitívak, amelyek tagjainak legnagyobb indexe valamelyik kj. Adott j-re az ilyen összegek száma 2kj, összesen tehát 2k1+2k2+...+2kp=M darab ilyen összeg van.