Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?
A régi honlapot akarom!!! :-)

A B. 3810. feladat (2005. március)

B. 3810. Jelölje k(n) az n pozitív egész szám legnagyobb páratlan osztóját, és legyen A(n)=k(1)+k(2)+...+k(n),  B(n)=1+2+...+n. Igazoljuk, hogy végtelen sok n-re teljesül, hogy 3 A(n) = 2B(n).

(5 pont)

A beküldési határidő 2005. április 15-én LEJÁRT.


Megoldás. Mivel A(2)=2, B(2)=3, A(6)=14, B(6)=21, A(14)=70 és B(14)=105, megsejthetjük, hogy 3A(n)=2B(n) teljesül, ha n=2a-2, ahol a\ge2. Ezt a sejtést a szerinti teljes indukcióval legegyszerűbben úgy igazolhatjuk, ha a

3\bigl(A(2^{a+1}-2)-A(2^a-2)\bigr)=2\bigl(B(2^{a+1}-2)-B(2^a-2)\bigr)

összefüggést igazoljuk a szerinti teljes indukcióval a\ge2 esetén. Ez teljesül, ha a=2, az indukciós lépéshez tegyük fel tehát, hogy a\ge3, és az állítást a-1 esetén már beláttuk. Azt kell igazolnunk, hogy

3\sum_{2^a-1}^{2^{a+1}-2}k(i)=2\sum_{2^a-1}^{2^{a+1}-2}i.

A jobboldalon szerplő összeg értéke

\sum_{2^a-1}^{2^{a+1}-2}i={2^a\bigl(2^a-1)+(2^{a+1}-2)\bigr)\over 2}=
{3\over 2}(2^a-1)2^a,

vagyis azt kell megmutatnunk, hogy a baloldalon szereplő összeg értéke (2a-1)2a-val egyenlő. Felhasználva, hogy k(2i)=k(i) és k(2i+1)=2i+1, az összeg

\sum_{2^{a-1}-1}^{2^{a}-2}k(2i+1)+
\sum_{2^{a-1}}^{2^{a}-1}k(2i)=\sum_{2^{a-1}-1}^{2^{a}-2}(2i+1)+
\sum_{2^{a-1}-1}^{2^{a}-2}k(i)-k(2^{a-1}-1)+k(2^a-1)

alakban is felírható, amit az indukciós feltevés alapján tovább alakítva kapjuk, hogy

\sum_{2^a-1}^{2^{a+1}-2}k(i)={2^{a-1}\bigl((2^a-1)+(2^{a+1}-3)\bigr)\over 2}+
{2\over 3}\sum_{2^{a-1}-1}^{2^{a}-2}i+2^{a-1}=

=2a-1(3.2a-1-2)+(2a-1-1)2a-1+2a-1=2a-1(4.2a-1-2)=2a(2a-1),

amint azt bizonyítani kívántuk.


Statisztika:

67 dolgozat érkezett.
5 pontot kapott:55 versenyző.
4 pontot kapott:5 versenyző.
3 pontot kapott:1 versenyző.
2 pontot kapott:1 versenyző.
1 pontot kapott:4 versenyző.
0 pontot kapott:1 versenyző.

A KöMaL 2005. márciusi matematika feladatai