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=2^a-2, ahol a $\ge$ 2. 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 $\ge$ 2 esetén. Ez teljesül, ha a=2, az indukciós lépéshez tegyük fel tehát, hogy a $\ge$ 3, é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 (2^a-1)2^a-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}=$

=2^a-1(3^.2^a-1-2)+(2^a-1-1)2^a-1+2^a-1=2^a-1(4^.2^a-1-2)=2^a(2^a-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

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ő.

Már regisztráltál?
Új vendég vagy?