KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 15 April 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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley