 |
A B. 4600. feladat (2014. január) |
B. 4600. Szét lehet-e osztani az első n prímszámot két részre úgy, hogy azokban a tagok összege megegyezzen, ha
a) n=20132014;
b) n=20142013?
(6 pont)
A beküldési határidő 2014. február 10-én LEJÁRT.
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.
Statisztika:
57 dolgozat érkezett. 6 pontot kapott: Á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 pontot kapott: Di Giovanni Márk, Győrfi-Bátori András, Nagy Gergely, Nagy Kartal. 4 pontot kapott: 1 versenyző. 3 pontot kapott: 1 versenyző. 1 pontot kapott: 41 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2014. januári matematika feladatai