Problem B. 5419. (November 2024)

B. 5419. Let \(\displaystyle q(n)\) denote the greatest odd divisor of positive integer \(\displaystyle n\). Let \(\displaystyle P(n)=q(1)+q(2)+\ldots+q(n)\) and \(\displaystyle S(n)=1+2+\ldots+n\). Prove that the ratio \(\displaystyle P(n)/S(n)\) is smaller than \(\displaystyle 2/3\) for infinitely many values of \(\displaystyle n\), and also greater than \(\displaystyle 2/3\) for infinitely many values of \(\displaystyle n\).

Proposed by Attila Sztranyák, Budapest

(5 pont)

Deadline expired on December 10, 2024.

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

Megoldás. Megvizsgálva \(\displaystyle P(2^n)-P(2^{n-1})\) első néhány értékét: \(\displaystyle P(2)-P(1)=q(2)=1=1^2\), \(\displaystyle P(4)-P(2)=q(3)+q(4)=3+1=2^2\), \(\displaystyle P(8)-P(4)=5+3+7+1=4^2\) az a sejtésünk adódhat, hogy \(\displaystyle P(2^{n})-P(2^{n-1})=(2^{n-1})^2\). Ezt \(\displaystyle n\) szerinti indukcióval bizonyítjuk.

Amint láttuk \(\displaystyle n=1,\;2\;,3\) esetén teljesül az indukció bázisállítása.

Tegyük fel, hogy egy adott \(\displaystyle n\)-re a \(\displaystyle P(2^n)-P(2^{n-1})=(2^{n-1})^2\) indukciós feltevés teljesül.

Megmutatjuk, hogy ekkor \(\displaystyle P(2^{n+1})-P(2^{n})=(2^{n})^2\) is igaz.

\(\displaystyle P(2^{n+1})-P(2^{n})=q(2^n+1)+q(2^n+2)+q(2^n+3)+...+q(2^{n+1})\). A jobb oldalon álló összegben a \(\displaystyle 2^n+(2k+1)\) alakú páratlan számok legnagyobb páratlan osztói sajátmaguk – azaz \(\displaystyle q(2^n+(2k+1))=2^n+(2k+1)\) –, míg egy \(\displaystyle 2^n+(2k)\) alakú páros szám legnagyobb páratlan osztója megegyezik a feleakkora \(\displaystyle 2^{n-1}+k\) szám legnagyobb páratlan osztójával – azaz \(\displaystyle q(2^n+(2k))=q(2^{n-1}+k)\). Ez alapján a fenti összeget két részre osztva: \(\displaystyle P(2^{n+1})-P(2^{n})=\left(q(2^n+1)+q(2^n+3)+q(2^n+5)+...+q(2^{n+1}-1) \right) + \left(q(2^n+2)+q(2^n+4)+q(2^n+6)+...+q(2^{n+1}) \right)= \left( (2^n+1) + (2^n+3) + ... + (2^n + 2^n-1)\right) + \left( q(2^{n-1}+1) + q(2^{n-1}+2) + ... +q(2^{n})\right)\).

Ez utóbbi összeg első zárójelében szerepel egyfelől \(\displaystyle 2^{n-1}\) darab \(\displaystyle 2^n\) tag, amelyek összege \(\displaystyle 2^{2n-1}\), valamint az \(\displaystyle 1\) és \(\displaystyle 2^{n}-1\) közötti páratlan számok (azaz az első \(\displaystyle 2^{n-1}\) darab páratlan szám) összege, amelyről ismert, hogy \(\displaystyle (2^{n-1})^2=2^{2n-2}\). Az összeg második zárójele pedig pontosan \(\displaystyle P(2^n)-P(2^{n-1})\), ami (az indukciós feltevés alapján) megegyezik \(\displaystyle (2^{n-1})^2=2^{2n-2}\)-vel.

Azaz \(\displaystyle P(2^{n+1})-P(2^{n})=(2^{2n-1} + 2^{2n-2}) + 2^{2n-2}=2^{2n}=(2^n)^2\), igazolva állításunk helyességét.

A fentiek alapján \(\displaystyle P(2^n)\)-t teleszkópos összegként felírva, majd felhasználva a mértani sorozat összegképletét adódik: \(\displaystyle P(2^n)=\left( P(2^{n}) - P(2^{n-1}) \right) + \left( P(2^{n-1}) - P(2^{n-2}) \right) + ... + \left( P(2) - P(1) \right) +P(1)= \left(2^{n-1} \right)^2 + \left(2^{n-2} \right)^2 + ...+2^0 + 1=4^{n-1}+4^{n-2} + ... + 4+4^0+1=\dfrac{4^{n}-1}{3}+1=\dfrac{4^{n}+2}{3}\).

Továbbá az első \(\displaystyle k\) pozitív egész összege nyilván \(\displaystyle S(k)=\dfrac{k(k+1)}{2}\), és így \(\displaystyle S(2^n)=\dfrac{2^n(2^n+1)}{2}=\dfrac{4^n+2^n}{2}\).

Innen (\(\displaystyle n>1\) esetén) \(\displaystyle \dfrac{P(2^n)}{S(2^n)} = \dfrac{2}{3} \cdot \dfrac{4^n+2}{4^n + 2^n} < \dfrac{2}{3}\), míg ha ,,eggyel tovább lépünk'', akkor \(\displaystyle P(2^n+1)=P(2^n)+2^n+1=\dfrac{4^n+2}{3} +2^n+1 = \dfrac{4^n+3 \cdot 2^n+5}{3}\) és \(\displaystyle S(2^n+1) = \dfrac{(2^n+1)(2^n+2)}{2} = \dfrac{4^n+3 \cdot 2^n + 2}{2}\) és így \(\displaystyle \dfrac{P(2^n+1)}{S(2^n+1)} = \dfrac{2}{3} \cdot \dfrac{4^n+3 \cdot 2^n+5}{4^n + 3 \cdot 2^n +2} > \dfrac{2}{3} \) .

Azaz a \(\displaystyle P(k)/S(k)\) arány valóban végtelen sok \(\displaystyle k\)-re kisebb, mint \(\displaystyle 2/3\), és végtelen sok \(\displaystyle k\)-re nagyobb, mint \(\displaystyle 2/3\).

Statistics:

51 students sent a solution.
5 points:	Ali Richárd, Aravin Peter, Baran Júlia, Bencze Mátyás, Bodor Ádám, Bolla Donát Andor, Bui Thuy-Trang Nikolett, Csató Hanna Zita , Fajszi Horka, Görömbey Tamás, Gyenes Károly, Hideg János, Hodossy Réka, Holló Martin, Kovács Benedek Noel, Kővágó Edit Gréta, Molnár István Ádám, Ozsváth Botond, Pázmándi József Áron, Péter Hanna, Prohászka Bulcsú, Rajtik Sándor Barnabás, Sajter Klaus, Sánta Gergely Péter, Sha Jingyuan, Szabó Imre Bence, Tamás Gellért, Török Eszter Júlia, Vámosi Bendegúz Péter, Varga 511 Vivien, Vigh 279 Zalán, Wágner Márton, Wiener Marcell, Zhai Yu Fan.
4 points:	Beinschroth Máté, Kerekes András, Li Mingdao, Pletikoszity Martin, Sárdinecz Dóra, Sütő Áron, Szabó 721 Sámuel, Vödrös Dániel László.
3 points:	4 students.
2 points:	2 students.
1 point:	2 students.

Problems in Mathematics of KöMaL, November 2024