A B. 5378. feladat (2024. március)

B. 5378. Legyenek \(\displaystyle n\) és \(\displaystyle k\) pozitív egész számok. Bizonyítsuk be, hogy ha \(\displaystyle n \leq k^{11}\), akkor \(\displaystyle n\) felírható tíz olyan pozitív egész szám szorzataként, melyek közt nincs \(\displaystyle k^2\)-nél nagyobb összetett szám.

Javasolta: Pach Péter Pál (Budapest)

(5 pont)

A beküldési határidő 2024. április 10-én LEJÁRT.

1. megoldás. Írjuk fel az \(\displaystyle n\leq k^{11}\) számot prímszámok szorzataként: \(\displaystyle n=p_1p_2\dots p_r\), ahol \(\displaystyle r\geq 0\) és feltehetjük, hogy \(\displaystyle p_1\geq p_2\geq \dots \geq p_r\). Azt szeretnénk belátni, hogy \(\displaystyle n\) felírható tíz olyan pozitív egész szám szorzataként, melyek mindegyike vagy prímszám, vagy legfeljebb \(\displaystyle k^2\) (speciálisan az 1-et is használhatjuk). A tíz tényezőt úgy alakítjuk ki, hogy kezdetben mindegyiket 1-nek vesszük, majd \(\displaystyle p_1\)-től kezdve mindegyik prímtényezőt ahhoz a szorzathoz vesszük hozzá, amelyik éppen a(z egyik) legkisebb. Vagyis \(\displaystyle p_1,\dots,p_{10}\) tíz külön tényezőbe fog kerülni, majd \(\displaystyle p_{11}\) bekerül \(\displaystyle p_{10}\) mellé, és innen folytatódik a beosztás (ha egyáltalán van ennyi prímtényező). Miután \(\displaystyle p_r\)-et is beosztottuk, kapunk tíz pozitív egész számot, melyek szorzata \(\displaystyle n\), azt szeretnénk belátni, hogy nincs köztük \(\displaystyle k^2\)-nél nagyobb összetett szám. Elég tehát belátnunk, hogy egyik \(\displaystyle p_i\) prím beosztásakor sem hozunk létre \(\displaystyle k^2\)-nél nagyobb összetett szorzatot. Világos, hogy \(\displaystyle p_1,\dots,p_{10}\) esetében ez valóban így van, hiszen a létrejövő szorzatok között eddig nincs is összetett szám. Legyen most \(\displaystyle q=p_i\) egy olyan prímtényező, amelyre \(\displaystyle i\geq 11\). Ekkor \(\displaystyle q\leq k\), hiszen \(\displaystyle q^{11}\leq p_1\dots p_{10}q\leq n\leq k^{11}\). Tegyük fel, hogy \(\displaystyle q\)-t az \(\displaystyle A\) szorzathoz vettük hozzá, azt szeretnénk belátni, hogy \(\displaystyle Aq\leq k^2\). Mivel \(\displaystyle q\)-t ide osztottuk be, ezért mind a kilenc másik (aktuális) szorzat értéke legalább \(\displaystyle A\). A tíz tényező szorzata legfeljebb \(\displaystyle n\), így biztosan \(\displaystyle A^{10}q\leq n\leq k^{11}\). Mivel \(\displaystyle q\leq k\) és \(\displaystyle A^{10}q\leq k^{11}\), ezért \(\displaystyle A^{10}q^{10}\leq k^{11}k^9=k^{20}\), amiből a kívánt \(\displaystyle Aq\leq k^2\) egyenlőtlenség adódik. Ezzel igazoltuk a feladat állítását, egyben egy eljárást is megadtunk megfelelő szorzat megkonstruálására.

2. megoldás. Általánosabban, azt igazoljuk, hogy ha a \(\displaystyle k\) és \(\displaystyle t\) pozitív egészekre teljesül, hogy \(\displaystyle n\leq k^{t+1}\), akkor \(\displaystyle n\) felírható \(\displaystyle t\) olyan pozitív egész szám szorzataként, amelyek között nincsen \(\displaystyle k^2\)-nél nagyobb összetett szám: \(\displaystyle n=a_1\cdot\ldots\cdot a_t\). Ez \(\displaystyle t=10\) esetén éppen a feladat állítása.

Az állítást \(\displaystyle t\)-re vonatkozó teljes indukcióval igazoljuk. A kezdőlépés világos: ha \(\displaystyle t=1\), akkor \(\displaystyle n=a_1\) megfelelő, hiszen \(\displaystyle n\leq k^2\).

Az indukciós lépés igazolásához tegyük fel, hogy valamely \(\displaystyle t\geq 1\) esetén már igazoltuk az állítást, célunk belátni, hogy \(\displaystyle (t+1)\)-re is teljesül. Legyen tehát \(\displaystyle n\leq k^{t+2}\). Ha az \(\displaystyle n\) számnak van olyan prímosztója, ami legalább \(\displaystyle k\), vagy van olyan osztója, ami legalább \(\displaystyle k\), de legfeljebb \(\displaystyle k^2\), akkor \(\displaystyle a_{t+1}\) legyen egy ilyen osztó. Mivel \(\displaystyle k\leq a_{t+1}\), ezért \(\displaystyle n':=n/a_{t+1}\leq k^{t+1}\), így az indukciós feltevés alapján \(\displaystyle n'\)-nek van megfelelő \(\displaystyle n'=a_1a_2\dots a_t\) előállítása. Ekkor \(\displaystyle n=a_1a_2\dots a_ta_{t+1}\) megfelelő előállítás, készen vagyunk. Ha viszont \(\displaystyle n\)-nek nincs ilyen osztója, akkor speciálisan minden prímosztója kisebb, mint \(\displaystyle k\). Ha \(\displaystyle k< n\) lenne, akkor \(\displaystyle n\)-nek van \(\displaystyle k\)-nál nagyobb osztója, vegyük a legkisebb ilyet, legyen ez \(\displaystyle d\). Ha ennek egy prímosztóját elhagynánk, akkor már \(\displaystyle k\)-nál kisebb osztót kapnánk, viszont minden prímosztó legfeljebb \(\displaystyle k\), így \(\displaystyle d\leq k^2\), viszont már feltettük, hogy nincs ilyen osztó. Tehát ebben az esetben csak az lehetséges, ha \(\displaystyle n\leq k\), ekkor viszont például \(\displaystyle a_1=n, a_2=\dots=a_{t+1}=1\) megfelelő választás.

Statisztika:

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

A KöMaL 2024. márciusi matematika feladatai