A B. 5419. feladat (2024. november)

B. 5419. Adott \(\displaystyle n\) pozitív egészre jelölje \(\displaystyle q(n)\) az \(\displaystyle n\) szám legnagyobb páratlan osztóját. Legyen \(\displaystyle P(n)=q(1)+q(2)+\ldots+q(n)\) és \(\displaystyle S(n)=1+2+\ldots+n\). Igazoljuk, hogy a \(\displaystyle P(n)/S(n)\) arány végtelen sok \(\displaystyle n\)-re kisebb, mint \(\displaystyle 2/3\), és végtelen sok \(\displaystyle n\)-re nagyobb, mint \(\displaystyle 2/3\).

Javasolta: Sztranyák Attila (Budapest)

(5 pont)

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

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\).

Statisztika:

51 dolgozat érkezett.
5 pontot kapott:	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 pontot kapott:	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 pontot kapott:	4 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	2 versenyző.

A KöMaL 2024. novemberi matematika feladatai