A B. 5030. feladat (2019. május)

B. 5030. Mutassuk meg, hogy minden \(\displaystyle 1\)-nél nagyobb egész felírható \(\displaystyle 1\)-nél nagyobb, \(\displaystyle 2^p\cdot 3^q\) alakú számok összegeként úgy, hogy az összegnek nincs két olyan tagja, melyek egyike a másiknak osztója. (Például \(\displaystyle 23=9+8+6\), \(\displaystyle 11=9+2\) vagy \(\displaystyle 12=12\).)

Erdős Pál feladata

(4 pont)

A beküldési határidő 2019. június 11-én LEJÁRT.

Megoldás. Az állítást \(\displaystyle n\)-re vonatkozó teljes indukcióval bizonyítjuk. Ha \(\displaystyle n=2,3,4\), akkor az egytagú előállítás megfelelő, most tegyük fel, hogy \(\displaystyle n\geq 5\) és az \(\displaystyle n\)-nél kisebb (de 1-nél nagyobb) számokra már igazoltuk megfelelő előállítás létezését. Két esetet különböztetünk meg \(\displaystyle n\) paritása szerint.

1. eset: \(\displaystyle n\) páros.
Ekkor \(\displaystyle n=2N\) valamely \(\displaystyle (n>)N>1\) egész számra, így \(\displaystyle N\)-nek van megfelelő előállítása: \(\displaystyle N=a_1+a_2+\dots+a_k\). Ekkor \(\displaystyle n\)-nek egy megfelelő előállítása \(\displaystyle n=(2a_1)+(2a_2)+\dots+(2a_k)\), hiszen ha \(\displaystyle a_1,\dots,a_k\) mind \(\displaystyle 2^p3^q\) alakúak, akkor \(\displaystyle 2a_1,\dots,2a_k\) is azok, és \(\displaystyle 2a_i\mid 2a_j\) csak akkor teljesülhetne, ha \(\displaystyle a_i\mid a_j\) lenne.

2. eset: \(\displaystyle n\) páratlan.
Ha \(\displaystyle n\) egy 3-hatvány, akkor az egytagú előállítás megfelelő. Ha \(\displaystyle n\) nem 3-hatvány, akkor legyen \(\displaystyle 3^m<n<3^{m+1}\). Legyen \(\displaystyle N:=n-3^m\), ez egy pozitív páros szám. Ekkor \(\displaystyle N/2(<n)\) egy olyan pozitív egész szám, amelyről \(\displaystyle N/2>1\) esetén az indukció alapján már tudjuk, hogy létezik megfelelő előállítása, egy ilyen legyen \(\displaystyle N/2=a_1+a_2+\dots+a_k\). Ha \(\displaystyle N/2=1\), akkor vegyük az \(\displaystyle N/2=1\) előállítást. Ekkor \(\displaystyle n\)-nek egy megfelelő előállítása: \(\displaystyle n=3^m+(2a_1)+\dots+(2a_k)\). Világos, hogy az összeadandók \(\displaystyle 2^p3^q\) alakúak, és \(\displaystyle 2a_1,\dots,2a_k\) közül egyik sem osztja valamelyik másikat. Mivel \(\displaystyle 3^m\) páratlan, ezért \(\displaystyle 2a_1,\dots,2a_k\) nem oszthatják. Végül, mivel bármely \(\displaystyle 1\leq j\leq k\) esetén \(\displaystyle 2a_j\leq N/2=\frac{n-3^m}{2}<3^m\), ezért \(\displaystyle 3^m\) sem osztja a többi összeadandót. Tehát megfelelő előállítást mutattunk.

Így teljes indukcióval következik, hogy bármely \(\displaystyle n>1\) egész számnak létezik ilyen előállítása.

Statisztika:

35 dolgozat érkezett.
4 pontot kapott:	Argay Zsolt, Baski Bence, Beke Csongor, Bencsik Ádám, Farkas 512 Izabella, Fülöp Csilla, Füredi Erik Benjámin, Geretovszky Anna, Győrffi Ádám György, Győrffy Ágoston, Hegedűs Dániel, Jánosik Áron, Kovács 129 Tamás, Lovas Márton, Nagy 551 Levente, Nguyen Bich Diep, Nyitrai Boglárka, Rareș Polenciuc, Sebestyén Pál Botond, Soós 314 Máté, Stomfai Gergely, Szabó 991 Kornél, Telek Zsigmond , Terjék András József, Tiderenczl Dániel, Tóth 057 Bálint, Tóth Ábel, Várkonyi Zsombor, Weisz Máté.
3 pontot kapott:	Nagy Nándor, Velich Nóra.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2019. májusi matematika feladatai