A B. 4854. feladat (2017. február)

B. 4854. Legyenek $\displaystyle a_1,a_2,\dots,a_n$ valós számok. Tekintsük az ezekből képezett $\displaystyle 2^n-1$ (nemüres) összeget. Hány lehet ezek közül pozitív?

(5 pont)

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

Megoldás. Megmutatjuk, hogy a pozitív összegek száma bármi lehet 0 és $\displaystyle 2^n-1$ között. Ezt az állítást $\displaystyle n$-re vonatkozó teljes indukcióval bizonyítjuk. Ha $\displaystyle n=1$, akkor $\displaystyle a_1=0$ esetén nincs pozitív összeg, $\displaystyle a_1=1$ esetén pedig 1 pozitív összeg van. Tegyük most fel, hogy az állítást $\displaystyle n$-re már igazoltuk, ezt felhasználva be fogjuk látni, hogy $\displaystyle (n+1)$-re is igaz. Legyen tehát $\displaystyle 0\leq k\leq 2^{n+1}-1$. Ha $\displaystyle 0\leq k\leq 2^n-1$, akkor az indukciós feltevés szerint vannak olyan $\displaystyle a_1,a_2,\dots,a_n$ számok, hogy a belőlük képezhető összegek közül pontosan $\displaystyle k$ pozitív. Legyen $\displaystyle a_{n+1}=-(|a_1|+|a_2|+\dots+|a_{n}|)$, ekkor az $\displaystyle a_{n+1}$-et tartalmazó összegek egyike sem lesz pozitív, így továbbra is $\displaystyle k$ pozitív összeg lesz. Ha pedig $\displaystyle 2^n\leq k\leq 2^{n+1}-1$, akkor az indukciós feltevés szerint vannak olyan $\displaystyle a_1, a_2, \dots, a_n$ számok, hogy a belőlük képezhető összegek közül pontosan $\displaystyle k-2^n$ pozitív, hiszen $\displaystyle 0\leq k-2^n\leq 2^n-1$. Legyen $\displaystyle a_{n+1}=|a_1|+|a_2|+\dots+|a_n|+1$, ekkor mind a $\displaystyle 2^n$ darab $\displaystyle a_{n+1}$-et tartalmazó összeg pozitív lesz. Így a pozitív összegek száma összesen $\displaystyle k-2^n+2^n=k$ lesz. Ezzel az állítást igazoltuk.

Statisztika:

63 dolgozat érkezett.
5 pontot kapott:	Alexy Milán, Andó Angelika, Asztalos Ádám, Bán Dániel, Baran Zsuzsanna, Beke Csongor, Borbényi Márton, Bötkös Benedek, Busa 423 Máté, Csahók Tímea, Csiszár Zoltán, Döbröntei Dávid Bence, Fraknói Ádám, Fuisz Gábor, Fülöp Anna Tácia, Füredi Erik Benjámin, Gáspár Attila, Győrffy Ágoston, György Levente, Harsányi Benedek, Imolay András, Janzer Orsolya Lili, Kerekes Anna, Kiss Gergely, Kocsis Júlia, Kovács 246 Benedek, Kovács 526 Tamás, Kővári Péter Viktor, Lakatos Ádám, Nagy Nándor, Németh 123 Balázs, Pap Benedek, Saár Patrik, Schrettner Jakab, Simon Dániel Gábor, Soós 314 Máté, Sulán Ádám, Szabó 417 Dávid, Szabó Kristóf, Tiderenczl Dániel, Tóth 827 Balázs, Tóth Viktor, Török Tímea, Vári-Kakas Andor, Weisz Máté, Zólomy Kristóf.
4 pontot kapott:	5 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	6 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2017. februári matematika feladatai