 |
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:
A B. 5419. feladat értékelése még nem fejeződött be.
A KöMaL 2024. novemberi matematika feladatai