BdMO Online Forum

Problem $11$
For a positive integer $n$, let $f(n)$ denote the greatest odd divisor of $n$. Prove that for any integer $x$, $f(x+1)+f(x+2)+........f(2x) = x^2$.

$\text{Solution to Problem 11}$

Lemma 1: $f(k)=f(2k)$
Proof: Trivial

Lemma 2: $f(2k+1)=2k+1$
Proof: Trivial

We will use induction. For $n=1$, it is true.

Now for $g(m)=f(m+1)+f(m+2)+\cdots+f(2m)=m^2$

We will be done if we can proof

$g(m+1)=f(m+2)+f(m+3)+\cdots+f(2m)+f(2m+1)+f(2m+2)=(m+1)^2$

Now,$f(m+1)+f(m+2)+\cdots +f(2m)=m^2$

$\Rightarrow f(m+2)+\cdots +f(2m)+f(2m+2)=m^2$ [Lemma 1 on $f(m+1)$]

$\Rightarrow f(m+2)+\cdots +f(2m)+f(2m+1)+f(2m+2)=m^2+2m+1$ [Lemma 2]

That means $g(m+1)=m^2+2m+1=(m+1)^2$

$[DONE]$

$\text{Problem 12}$

For every positive integer $k$ let $f(k)$ be the largest integer such that $2^{f(k)} \mid k$. For every positive integer $n$ determine : $f(1) + f(2) +f(3)+f(4)+f(5)+\cdots+ f(2^n)$.

Or, $\displaystyle\sum_{i=1}^{2^n} f(i)=?$

Mod note: This solution was for a wrong version of problem 12, asking for sum of $f(n)$ where $n=2^k$ only. The correct solution is below.

$\text{SOLUTION TO PROBLEM 12}$

$f(1) + f(2) +..... f(2^n) = 2^0 + 2^1+...... 2^{n-1}$

PROOF: lemma 1:$ f(2k +1) = 0$
proof: trivial

Lemma : $f(2^m + 1) + f(2^m + 2) +........f(2^{m+1}) = 2^m$

Proof : We use induction. Base case m = 1 is true.

Now, let $g(m) = f(2^m + 1) + f(2^m + 2) +........f(2^{m+1}) = 2^m$

For $f(2\times 2^m + 1) + f(2\times2^m + 2) +........f(2\times2^m + 2^m) = f(2(2^m + 1)) + f(2(2^m + 2)) +........f(2(2^{m+1})) = 2^m + 2^m$

Here, we multiply 2 with every even number from $2^{m+1}$ to $2^{m+2}$, As there as $2^m$ even numbers between them, we get $f(2^{m + 1} + 1) + f(2^{m + 1} + 2) +........f(2^{m+2}) = 2^{m+1}$

Therefore, our result follows.

$\text{PROBLEM 13 :}$

Let $AD, BE, CF$ be concurrent cevians in a triangle, meeting at $P$. Prove that $\dfrac{PD}{AD} + \dfrac{PE}{BE} + \dfrac{PF}{CF} =1$.

Let us denote by $ABC$,the area of $\bigtriangleup ABC$. From geometric proportion,$\frac{PD}{AD} = \frac{PBC}{ABC}$ as the bases of $\bigtriangleup ABC$ and $\bigtriangleup PBC$ are the same.This case works for $\bigtriangleup PAC$ and $\bigtriangleup PAB$ as well.So,we concurr that $\frac{PD}{AS} + \frac{PE}{BE} + \frac{PF}{CF} = \frac{PBC}{ABC} + \frac{PAC}{ABC} + \frac{PAB}{ABC} = 1$.

Problem 14:Let the incircle of triangle ABC touch BC at D. Let,DT be a diameter of the circle.If AT meets BC at M,prove that BD=CM.

$\text{Solution to 14}$

Consider the dilation with center $A$ that carries the incircle to an excircle. The diameter $DT$ of the incircle must be mapped to the diameter of the excircle that is perpendicular to $BC$. It follows that $T$ must get mapped to the point of tangency between the excircle and $BC$. Since the image of $T$ must lie on the line $AT$, it must be $M$. That is, the excircle is tangent to $BC$ at $M$. Then, it follows easily that $BD = CM$.

$\text{Problem 15}$

Let n be an integer greater than $2$. Prove that among the fractions

$$\frac{1}{n},\frac{2}{n}\cdots ,\frac{n-1}{n}$$

an even number are irreducible.