Problem B. 4600. (January 2014)

B. 4600. Is it possible to divide the first n prime numbers into two sets such that the sum of elements in each set is the same if

a) n=2013²⁰¹⁴;

b) n=2014²⁰¹³?

(6 pont)

Deadline expired on February 10, 2014.

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

Megoldás. a) Jelölje az első \(\displaystyle n\) prímszámot \(\displaystyle p_1\leq p_2\leq\dots \leq p_n\). Megadunk egy algoritmust, amellyel két részre lehet őket osztani úgy, hogy a két részben a tagok összege megegyezzen, ha \(\displaystyle n=2013^{2014}\). Először \(\displaystyle p_n\)-et betesszük az első részbe, utána \(\displaystyle p_{n-1}\)-et a második részbe. Ezután minden lépésben a még nem beosztott prímszámok közül a legnagyobbat oda tesszük, ahol a tagok összege kisebb (ha éppen egyenlő az összeg, akkor tetszés szerint választunk). Vagyis a \(\displaystyle k\)-adik lépés után a \(\displaystyle p_n,p_{n-1},\dots,p_{n-k+1}\) prímek lesznek szétosztva két részre. Megmutatjuk, hogy a két részben a tagok összege legfeljebb \(\displaystyle p_{n-k+1}\)-gyel, vagyis az utoljára beosztott prímmel térhet el. Ezt \(\displaystyle k\) szerinti teljes indukcióval bizonyítjuk, \(\displaystyle k=1\)-re az állítás nyilvánvalóan teljesül. Tegyük fel, hogy az állítást már igazoltuk \(\displaystyle k\)-ra, megmutatjuk, hogy \(\displaystyle k+1\)-re is igaz. Az indukciós feltevés szerint a \(\displaystyle p_n,p_{n-1},\dots,p_{n-k+1}\) prímeket két részre lehet osztani úgy, hogy a két részben a tagok összege legfeljebb \(\displaystyle p_{n-k+1}\)-gyel tér el. Ha a soron következő \(\displaystyle p_{n-k}\) prím beosztása után abban a részben lesz nagyobb a tagok összege, ahova kerül, akkor legfeljebb \(\displaystyle p_{n-k}\)-val lehet nagyobb, mint a másik részben, hiszen eddig a másik részben nagyobb (vagy éppen ugyanannyi) volt a tagok összege. Ha pedig továbbra is a másik részben marad nagyobb az összeg, akkor az eltérés az indukciós feltevést is használva legfeljebb \(\displaystyle p_{n-k+1}-p_{n-k}\). Ez viszont Csebisev tétele szerint valóban legfeljebb \(\displaystyle p_{n-k}\), hiszen ellenkező esetben a \(\displaystyle p_{n-k}\) szám és annak kétszerese közé nem esne prím. Ezzel beláttuk, hogy tetszőleges \(\displaystyle 1\leq k\leq n\) esetén a \(\displaystyle k\)-adik lépés után a két részben a tagok összege legfeljebb \(\displaystyle p_{n-k+1}\)-gyel, vagyis az utoljára beosztott prímmel térhet el. Legyen az \(\displaystyle n-5\)-ödik lépés után kapott két összeg \(\displaystyle A\) és \(\displaystyle B\), melyek eltérése az előzőek szerint legfeljebb \(\displaystyle p_6=13\). Legyen \(\displaystyle A\leq B\). Mivel \(\displaystyle n=2013^{2014}\) esetén \(\displaystyle A+B\) páros (páros sok páratlan prím összege), ezért \(\displaystyle B-A\) lehetséges értékei: \(\displaystyle 0,2,4,6,8,10,12\). Elég megmutatni, hogy a \(\displaystyle 2,3,5,7,11\) prímeket mindegyik esetben szét lehet úgy osztani két részre, hogy a két rész különbsége éppen \(\displaystyle B-A\) legyen. Ehhez a 12-nél nem nagyobb páros nemnegatív egészeket kell felírnunk az első 5 prímszám előjeles összegeként:

\(\displaystyle 0=2-3+5+7-11,\quad 2=-2+3+5+7-11,\quad 4=-2-3+5-7+11,\quad 6=2+3+5+7-11,\)

\(\displaystyle 8=-2-3-5+7+11, \quad 10=-2+3+5-7+11,\quad 12=2-3-5+7+11.\)

Ezzel megmutattuk, hogy \(\displaystyle n=2013^{2014}\) esetén a kívánt szétosztás megvalósítható.

b) A \(\displaystyle 2014^{2013}\) szám páros, így az első \(\displaystyle 2014^{2013}\) prímszám összege páratlan, hiszen egy darab páros szám (2) és páratlan sok páratlan szám összege. Ebből azonnal következik, hogy nem lehet két részre osztani az első \(\displaystyle 2014^{2013}\) prímszámot úgy, hogy azokban a tagok összege megegyezzen.

Statistics:

57 students sent a solution.
6 points:	Ágoston Péter, Csernák Tamás, Kúsz Ágnes, Lajkó Kálmán, Maga Balázs, Mócsy Miklós, Nagy-György Pál, Szabó 789 Barnabás, Williams Kada.
5 points:	Di Giovanni Márk, Győrfi-Bátori András, Nagy Gergely, Nagy Kartal.
4 points:	1 student.
3 points:	1 student.
1 point:	41 students.
0 point:	1 student.

Problems in Mathematics of KöMaL, January 2014