Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 3810. (March 2005)

B. 3810. Denote the greatest odd divisor of the positive integer n by k(n). Let

A(n)=k(1)+k(2)+...+k(n),   B(n)=1+2+...+n.

Prove that there are infinitely many values of n such that 3 A(n) = 2B(n).

(5 pont)

Deadline expired on April 15, 2005.


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

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.


Statistics:

67 students sent a solution.
5 points:55 students.
4 points:5 students.
3 points:1 student.
2 points:1 student.
1 point:4 students.
0 point:1 student.

Problems in Mathematics of KöMaL, March 2005