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

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 $2^{n-1}\mathrm{,}{2}^{n-2}\mathrm{,}\text{...}\mathrm{,}{2}^0=1$ számokat. Ezeket alkalmasan előjelezve megmutatjuk, hogy $0$-tól $2^{n-1}$-ig bármennyi lehet a nemüres összegek közül pozitív. Először vegyük az $a_1=-2^{n-1}$, $a_2=-2^{n-2}$, $\text{...}$, $a_n=-2^0$ 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 $2^{n-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=2^{k_1}+2^{k_2}+\text{...}+2^{k_p}$ alakú (ahol $k_1>k_2>\text{...}>k_p$), akkor $a_{k_1}\mathrm{,}{a}_{k_2}\mathrm{,}\text{...}\mathrm{,}{a}_{k_p}$ 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 $k_j$. Adott $j$-re az ilyen összegek száma $2^{k_j}$, összesen tehát $2^{k_1}+2^{k_2}+\text{...}+2^{k_p}=M$ darab ilyen összeg van.