Problem B. 5030. (May 2019)

B. 5030. Prove that every integer greater than \(\displaystyle 1\) can be represented as a sum of numbers of the form \(\displaystyle 2^p\cdot 3^q\) greater than \(\displaystyle 1\) such that no term of the sum is a divisor of another term. (For example, \(\displaystyle 23=9+8+6\), \(\displaystyle 11=9+2\) or \(\displaystyle 12=12\).)

A problem of Paul Erdős

(4 pont)

Deadline expired on June 11, 2019.

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

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.

Statistics:

35 students sent a solution.
4 points:	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 points:	Nagy Nándor, Velich Nóra.
1 point:	1 student.
0 point:	3 students.

Problems in Mathematics of KöMaL, May 2019