Feladat: N.120 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bérczi Gergely ,  Braun Gábor ,  Frenkel Péter ,  Gyenes Zoltán ,  Kun Gábor ,  Lippner Gábor ,  Lukács László ,  Nagy István ,  Pap Gyula ,  Szabó Jácint 
Füzet: 1997/április, 231. oldal  PDF file
Témakör(ök): Oszthatósági feladatok, Számsorozatok, Konstruktív megoldási módszer, Nehéz feladat
Hivatkozás(ok):Feladatok: 1996/december: N.120

Jelöljük f(n)-nel azt, hogy egy n pozitív egész hányféleképpen írható fel 2a5b alakú számok összegeként (a tagok sorrendje nem számít) úgy, hogy egyik sem osztója a másiknak (a és b nemnegatív egészek). Bizonyítsuk be, hogy f(n) nem korlátos.

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.

A következőket fogjuk bebizonyítani:

(1) Van olyan n, amelyre f(n)2.

(2) Tetszőleges  n  pozitív egészhez létezik olyan  m  pozitív egész, amelyre
f(m)(f(n))2. Ezekből az állítás következik.
(1) bizonyításához elég egy példát mutatni, ilyen pl. 133=27+5=53+23 vagy 129=53+22=52+523+26.
(2) bizonyításához legyen k olyan nagy pozitív egész, amelyre 2k>n, és legyen m=2kn+5kn. Azt állítjuk, hogy ez a szám megfelelő.
Legyen n két tetszőleges felbontása n=a1+...+ap és n=b1+...+bq; k választása miatt ezekben a tagokban a 2 és az 5 kitevője kisebb k-nál.
A két felbontásból elkészíthetjük m egy felbontását úgy, hogy az egyik összeg tagjait 2k-nal, a másikat 5k-nal megszorozzuk: m=2ka1+...+2kap+5kb1+...+5kbq. Megmutatjuk, hogy az ilyen módon kapható (f(n))2 felbontás mind különböző, és teljesíti azt a feltételt, hogy egyik tag sem osztója a másiknak.
Mivel az ai-k, illetve a bi-k közül egyik sem osztója a másiknak, továbbá 2k nem osztója 5kbi-nek, és 5k nem osztója 2kai-nek, m felbontásában egyik tag sem osztója a másiknak.
Az egyértelműség azért igaz, mert m felbontásában a 2kai alakú tagok oszthatók 2k-nal de 5k-nal nem, illetve az 5kbi alakú tagok oszthatók 5k-nal de 2k-nal nem; emiatt m felbontása egyértelműen meghatározza, hogy n melyik két felbontásából készült.

 Több dolgozat alapján