Problem B. 5378. (March 2024)

B. 5378. Let \(\displaystyle n\) and \(\displaystyle k\) be positive integers. Prove that if \(\displaystyle n \leq k^{11}\), then \(\displaystyle n\) can be obtained as the product of ten positive integers, among which no composite number greater than \(\displaystyle k^2\) appears.

Proposed by Péter Pál Pach, Budapest

(5 pont)

Deadline expired on April 10, 2024.

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

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.

Statistics:

52 students sent a solution.
5 points:	Ali Richárd, Aravin Peter, Bencze Mátyás, Bodor Mátyás, Bui Thuy-Trang Nikolett, Csató Hanna Zita , Csonka Illés, Farkas 005 Bendegúz, Görömbey Tamás, Gyenes Károly, Hodossy Réka, Holló Martin, Horák Zsófia, Juhász-Molnár Erik, Keresztély Zsófia, Kovács Benedek Noel, Kővágó Edit Gréta, Maróti Bálint, Molnár István Ádám, Morvai Várkony Albert, Op Den Kelder Ábel, Prohászka Bulcsú, Sági Mihály, Sánta Gergely Péter, Sárdinecz Dóra, Sütő Áron, Szabó 721 Sámuel, Tamás Gellért, Török Eszter Júlia, Vigh 279 Zalán, Virág Tóbiás, Zhai Yu Fan.
4 points:	Baranyi Ernő, Forrai Boldizsár, Wágner Márton.
3 points:	2 students.
2 points:	2 students.
1 point:	2 students.
0 point:	9 students.

Problems in Mathematics of KöMaL, March 2024