Problem B. 5443. (February 2025)
B. 5443. For an arbitrary positive integer \(\displaystyle n\) let \(\displaystyle a_n\) denote the number of positive perfect powers that are at most \(\displaystyle n\) (for example, \(\displaystyle a_9=4\)). We call \(\displaystyle n\) `interesting', if \(\displaystyle a_n \mid n\). Prove that there exists infinitely many interesting positive integers.
Proposed by: Attila Sztranyák, Budapest
(6 pont)
Deadline expired on March 10, 2025.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Először adjunk felső becslést \(\displaystyle a_{4^n}\)-re (azaz arra, hogy \(\displaystyle 4^n\)-ig hány teljes hatvány lehet). A \(\displaystyle 4^n\)-nél nem nagyobb teljes hatványok alapjai a \(\displaystyle 2;3;...;2^n\) számok közül kerülhetnek csak ki, és mindegyik ilyen alap esetén a kitevő legfeljebb \(\displaystyle 2n\) lehet (az is csak a 2-es alap esetén). Egy csomó teljes hatványhoz (pl. \(\displaystyle 16=2^4=4^2\)) több alap is tartozik, de mivel felülről becsülünk, ez nem okoz gondot. Azaz az eddigiek szerint \(\displaystyle a_{4^n} \leq 2 n \cdot 2^n\).
Másodszor: legyen \(\displaystyle k\) tetszőleges pozitív egész, és \(\displaystyle x_n=ka_n-n\) (\(\displaystyle n=1,2,\ldots\)). Azt fogjuk megmutatni, hogy az \(\displaystyle \lbrace x_n \rbrace\) sorozat tartalmazza a \(\displaystyle 0\)-t, mivel ekkor például \(\displaystyle x_m=0\) esetén \(\displaystyle k a_m - m = 0 \Rightarrow k a_m=m\) és \(\displaystyle a_m\) (a ,,\(\displaystyle k\) pozitív egészhez tartozó'') izgalmas szám.
\(\displaystyle x_n\)-t vizsgálva \(\displaystyle x_1= k \cdot a_1 -1=k-1 \geq 0\), míg minden további \(\displaystyle (n+1)\) indexre \(\displaystyle x_{n+1}=x_n - 1\) (ha \(\displaystyle n+1\) nem teljes hatvány), vagy \(\displaystyle x_{n+1}=x_n+(k-1) \geq x_n\) (ha \(\displaystyle n+1\) teljes hatvány).
A megoldás elején bizonyított \(\displaystyle a_{4^n} \leq 2 n \cdot 2^n\) egyenlőtlenséget felhasználva \(\displaystyle x_{4^n} \leq 2k n \cdot 2^n -4^n = -2^n\big(2^n-2kn\big)\to-\infty\) miatt az \(\displaystyle \lbrace x_n \rbrace\) sorozat tartalmaz negatív elemet. Ha \(\displaystyle x_{n+1}\) az első negatív elem a sorozatban, akkor \(\displaystyle x_n=0\), vagyis \(\displaystyle k\cdot a_n=n\).
Azaz tetszőleges \(\displaystyle k\) pozitív egész esetén van olyan \(\displaystyle n\), amelyre \(\displaystyle k\cdot a_n=n\), és így persze \(\displaystyle n\) izgalmas szám. Mivel különböző \(\displaystyle k\) (pozitív egész) számokhoz nyilván csak különböző \(\displaystyle n\)-ek tartozhatnak, ezért valóban végtelen sok izgalmas szám van (és ezt akartuk igazolni).
Statistics:
17 students sent a solution. 6 points: Ali Richárd, Gyenes Károly, Holló Martin, Kovács Benedek Noel, Molnár István Ádám, Pázmándi József Áron, Tamás Gellért, Vámosi Bendegúz Péter. 5 points: Wágner Márton. 4 points: 1 student. 1 point: 1 student. 0 point: 6 students.
Problems in Mathematics of KöMaL, February 2025