Feladat:	B.4600	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Lajkó Kálmán ,  Mócsy Miklós
Füzet:	2015/január, 17 - 18. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Teljes indukció módszere, Prímszámok, Konstruktív megoldási módszer
Hivatkozás(ok):	Feladatok: 2014/január: B.4600

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.   I. megoldás. $a)$ Jelölje az első $n$ prímszámot $p_1<p_2<\text{...}<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 $n={2013}^{2014}$. Először $p_n$-et betesszük az első részbe, utána $p_{n-1}$-et a második részbe. Ezután minden lépésben a még be nem osztott prímszámok közül a legnagyobbat oda tesszük, ahol a tagok összege kisebb (ha éppen egyenlő a két összeg, akkor tetszés szerint választunk). Vagyis a $k$-adik lépés után a $p_n\mathrm{,}{p}_{n-1}\mathrm{,}\text{...}\mathrm{,}{p}_{n-k+1}$ prímek lesznek szétosztva két részre. Megmutatjuk, hogy a két részben a tagok összege legfeljebb $p_{n-k+1}$-gyel, vagyis az utoljára beosztott prímmel térhet el. Ezt $k$ szerinti teljes indukcióval bizonyítjuk, $k=1$-re az állítás nyilvánvalóan teljesül. Tegyük fel, hogy az állítást már igazoltuk $k$-ra, megmutatjuk, hogy $k+1$-re is igaz. Az indukciós feltevés szerint a $p_n\mathrm{,}{p}_{n-1}\mathrm{,}\text{...}\mathrm{,}{p}_{n-k+1}$ prímeket két részre lehet osztani úgy, hogy a két részben a tagok összege legfeljebb $p_{n-k+1}$-gyel tér el. Ha a soron következő $p_{n-k}$ prím beosztása után abban a részben lesz nagyobb a tagok összege, ahova kerül, akkor legfeljebb $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 $p_{n-k+1}-p_{n-k}$. Ez viszont Csebisev tétele szerint valóban legfeljebb $p_{n-k}$, hiszen ellenkező esetben a $p_{n-k}$ szám és annak kétszerese közé nem esne prím. Ezzel beláttuk, hogy tetszőleges $1\le k\le n$ esetén a $k$-adik lépés után a két részben a tagok összege legfeljebb $p_{n-k+1}$-gyel, vagyis az utoljára beosztott prímmel térhet el. Ez egyben azt is jelenti, hogy az utolsó prím, vagyis a 2 hozzáadása után a két rész különbsége legfeljebb 2 lesz. A különbség nem lehet 1, hiszen $n={2013}^{2014}$ esetén az első $n$ prímszám összege páros, így a két részben a számok összegének ugyanaz a paritása. Ha a különbség 0, akkor készen vagyunk, találtunk egy jó beosztást. Most tegyük fel, hogy a különbség 2. Ekkor a 2 hozzáadása előtt a két részben az összeg éppen egyenlő, ezt a közös értéket jelölje $S$. A szimmetria miatt feltehető, hogy a 3 az első részbe került. Ekkor az 5 nem kerülhetett az első részbe, ugyanis ekkor a 7 beosztása után a két részben $S-8$, illetve $S$ lett volna a prímek összege, és így 7-nél nagyobb lett volna a különbség. Tehát az 5 a második részbe került. Először tegyük fel, hogy a 7 az első részbe került. A 11 nem kerülhetett az első részbe, mert akkor a 13 beosztása utáni különbség $\left(S-5\right)-\left(S-3-7-11\right)=16>13$ lett volna, így a 11 a második részbe került. Ha a 11-et áttesszük az első részbe, a 3-at és a 7-et pedig a másodikba, akkor az elsőben $S+1$, a másodikban $S-1$ lesz az összeg, így a 2-t a másodikba téve egyenlő összegeket kapunk. Végül tegyük fel, hogy a 7 a második részbe került. Az előzőekhez hasonlóan látható, hogy a 11 csak az első részbe kerülhetett. Ekkor viszont a 11-et áttéve a második részbe, az 5-öt és a 7-et pedig az elsőbe, a két kialakuló összeg megint $S+1$ és $S-1$, vagyis a 2-t a második részbe téve ismét egyenlő összegeket kapunk. Ezzel megmutattuk, hogy $n={2013}^{2014}$ esetén a kívánt szétosztás megvalósítható. $b)$ A ${2014}^{2013}$ szám páros, így az első ${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ő ${2014}^{2013}$ prímszámot úgy, hogy azokban a tagok összege megegyezzen.   II. megoldás az $a)$ részre. Az I. megoldásban ismertetett algoritmust használva a következőképpen is okoskodhatunk. Legyen az $n-5$-ödik lépés után kapott két összeg $A$ és $B$, melyek eltérése az előzőek szerint legfeljebb $p_6=13$. Legyen $A\le B$. Mivel $n={2013}^{2014}$ esetén $A+B$ páros (páros sok páratlan prím összege), ezért $B-A$ lehetséges értékei: $\mathrm{0,2,4,6,8,10,12}$. Elég megmutatni, hogy a $\mathrm{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 $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, ami mindegyik esetben megtehető: ${\displaystyle \begin{array}{c}\hfill {\displaystyle 0=2-3+5+7-\mathrm{11,}2=-2+3+5+7-\mathrm{11,}4=-2-3+5-7+\mathrm{11,}}\hfill \\ \hfill {\displaystyle 6=2+3+5+7-\mathrm{11,}8=-2-3-5+7+\mathrm{11,}}\hfill \\ \hfill {\displaystyle 10=-2+3+5-7+\mathrm{11,}12=2-3-5+7+11.}\hfill \end{array}}$