Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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:

A B. 5030. feladat értékelése még nem fejeződött be.


A KöMaL 2019. májusi matematika feladatai