Beginner's Marathon
- ahmedittihad
- Posts:181
- Joined:Mon Mar 28, 2016 6:21 pm
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$.
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$.
Frankly, my dear, I don't give a damn.
- Thamim Zahin
- Posts:98
- Joined:Wed Aug 03, 2016 5:42 pm
Re: Beginner's Marathon
$\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]$
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]$
Last edited by Thamim Zahin on Mon Apr 10, 2017 7:15 pm, edited 1 time in total.
I think we judge talent wrong. What do we see as talent? I think I have made the same mistake myself. We judge talent by the trophies on their showcases, the flamboyance the supremacy. We don't see things like determination, courage, discipline, temperament.
- Thamim Zahin
- Posts:98
- Joined:Wed Aug 03, 2016 5:42 pm
Re: Beginner's Marathon
$\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)=?$
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)=?$
Last edited by Thamim Zahin on Tue Apr 11, 2017 10:49 pm, edited 3 times in total.
I think we judge talent wrong. What do we see as talent? I think I have made the same mistake myself. We judge talent by the trophies on their showcases, the flamboyance the supremacy. We don't see things like determination, courage, discipline, temperament.
Re: Beginner's Marathon
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.
Last edited by Zawadx on Tue Apr 18, 2017 7:11 pm, edited 2 times in total.
Reason: Fixed LaTeX issues
Reason: Fixed LaTeX issues
Re: Beginner's Marathon
$\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.
$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.
Last edited by dshasan on Sat Apr 15, 2017 12:51 am, edited 1 time in total.
The study of mathematics, like the Nile, begins in minuteness but ends in magnificence.
- Charles Caleb Colton
- Charles Caleb Colton
Re: Beginner's Marathon
$\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 $AD, BE, CF$ be concurrent cevians in a triangle, meeting at $P$. Prove that $\dfrac{PD}{AD} + \dfrac{PE}{BE} + \dfrac{PF}{CF} =1$.
The study of mathematics, like the Nile, begins in minuteness but ends in magnificence.
- Charles Caleb Colton
- Charles Caleb Colton
-
- Posts:57
- Joined:Sun Dec 11, 2016 2:01 pm
Re: Beginner's Marathon
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$.
Last edited by Zawadx on Tue Apr 18, 2017 7:06 pm, edited 2 times in total.
Reason: Fixed LaTex
Reason: Fixed LaTex
-
- Posts:57
- Joined:Sun Dec 11, 2016 2:01 pm
Re: Beginner's Marathon
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.
- Thamim Zahin
- Posts:98
- Joined:Wed Aug 03, 2016 5:42 pm
Re: Beginner's Marathon
$\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$.
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$.
I think we judge talent wrong. What do we see as talent? I think I have made the same mistake myself. We judge talent by the trophies on their showcases, the flamboyance the supremacy. We don't see things like determination, courage, discipline, temperament.
- Thamim Zahin
- Posts:98
- Joined:Wed Aug 03, 2016 5:42 pm
Re: Beginner's Marathon
$\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.
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.
I think we judge talent wrong. What do we see as talent? I think I have made the same mistake myself. We judge talent by the trophies on their showcases, the flamboyance the supremacy. We don't see things like determination, courage, discipline, temperament.