Problem B. 4854. (February 2017)

B. 4854. Let \(\displaystyle a_1,a_2,\dots,a_n\) be real numbers. Consider the \(\displaystyle 2^n-1\) (nonempty) sums composed out of these numbers. How many of these may be positive?

(5 pont)

Deadline expired on March 10, 2017.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

63 students sent a solution.
5 points:	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 points:	5 students.
3 points:	3 students.
2 points:	6 students.
1 point:	2 students.
0 point:	1 student.

Problems in Mathematics of KöMaL, February 2017