IMO 2013, Day 1-P1

Discussion on International Mathematical Olympiad (IMO)
User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh
IMO 2013, Day 1-P1

Unread post by Masum » Mon Jul 29, 2013 1:02 pm

Prove that for all positive integers $n,k$, there are positive integers $m_1,m_2,...,m_k$ such that,
\[1+\dfrac{2^k-1}n=\left(1+\dfrac1{m_1}\right)\left(1+\dfrac1{m_2}\right)\cdots\left(1+\dfrac1{m_k}\right)\]
One one thing is neutral in the universe, that is $0$.

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: IMO 2013, Day 1-P1

Unread post by SANZEED » Tue Jul 30, 2013 2:39 pm

We will use induction on $k$.
Note that if $k=1$, then $\forall n\in \mathbb{N}$, we have $\displaystyle 1+\frac{2^{1}-1}{n}=1+\frac{1}{n}$ and it satisfies the given condition for $k=1$. This our base case.
Next,let us assume thatwe can find an expression for $\displaystyle 1+\frac{2^{k}-1}{n}$ for $k=i$ and any $n\in \mathbb{N}$. Notice that this expression consists of $i$ terms. Now we have two cases for $k=i+1$ and $n\in \mathbb{N}$ :
:arrow: When $n$ is even, $\displaystyle\frac{n}{2}\in \mathbb{N}$ and so we can take,
$\displaystyle 1+\frac{2^{i+1}-1}{n}=(1+\frac{1}{n+2^{i}-2})(1+\frac{2^{i}-1}{\frac{n}{2}})$ ,and since $\displaystyle (1+\frac{2^{i}-1}{\frac{n}{2}})$ is expressible into the desired form consisting of $i$ terms according to our induction assumption, $\displaystyle 1+\frac{2^{i+1}-1}{n}$ is also expressible into the desired form consisting of $(i+1)$ terms when $n$ is even.

:arrow: If $n$ is odd, then $\frac{n+1}{2}\in \mathbb{N}$. So this time we just take
$\displaystyle 1+\frac{2^{i+1}-1}{n}=(1+\frac{1}{n})(1+\frac{2^{i}-1}{\frac{n+1}{2}})$ and like our previous argument,we can say that $\displaystyle 1+\frac{2^{i+1}-1}{n}$ is expressible in our desired form consisting of $(i+1)$ terms.

So,by induction, we can find $m_{i}\in \mathbb{N}$ for all $k,n\in \mathbb{N}$ such that
$\displaystyle 1+\frac{2^{k}-1}{n}=(1+\frac{1}{m_{1}})(1+\frac{1}{m_{2}})...(1+\frac{1}{m_{k}})$
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

Post Reply