Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2013 IMO Problems/Problem 1"

(Created page with "==Problem== Prove that for any pair of positive integers <math>k</math> and <math>n</math>, there exist <math>k</math> positive integers <math>m_1,m_2,...,m_k</math> (not necessa...")
 
(Added solution.)
Line 5: Line 5:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
We prove the claim by induction on <math>k</math>.
 +
 
 +
'''Base case:''' If <math>k = 1</math> then <math>1 +\frac{2^1-1}{n} = 1 + \frac{1}{n}</math>, so the claim is true for all positive integers <math>n</math>.
 +
 
 +
'''Inductive hypothesis:''' Suppose that for some <math>m \in \mathbb{Z}^{+}</math> the claim is true for <math>k = m</math>, for all <math>n \in \mathbb{Z}^{+}</math>.
 +
 
 +
'''Inductive step:''' Let <math>n</math> be arbitrary and fixed. Case on the parity of <math>n</math>:
 +
 
 +
[Case 1: <math>n</math> is even] <math>1 + \frac{2^{m+1} - 1}{n} = \frac{\frac{n}{2} + 2^{m} - 1}{\frac{n}{2}} \cdot \left( 1 + \frac{1}{n + 2^{m+1} - 2} \right)</math>
 +
 
 +
[Case 2: <math>n</math> is odd] <math>1 + \frac{2^{m+1} - 1}{n} = \frac{\frac{n-1}{2} + 2^{m}}{\frac{n-1}{2} + 1} \cdot \left( 1 + \frac{1}{n} \right)</math>
 +
 
 +
In either case, <math>1 + \frac{2^{m+1} - 1}{n} = \frac{c + 2^m - 1}{c} \cdot \left( 1 + \frac{1}{a_{m+1}} \right)</math> for some <math>c, a_{m+1} \in \mathbb{Z}^+</math>.
 +
 
 +
By the induction hypothesis we can choose <math>a_1, ..., a_m</math> such that <math>\frac{c + 2^m - 1}{c} = \prod_{i=1}^{m} (1 + \frac{1}{a_i})</math>.
 +
 
 +
Therefore, since <math>n</math> was arbitrary, the claim is true for <math>k = m+1</math>, for all <math>n</math>. Our induction is complete and the claim is true for all positive integers <math>n</math>, <math>k</math>.
  
 
==See Also==
 
==See Also==
 
*[[2013 IMO]]
 
*[[2013 IMO]]

Revision as of 13:01, 6 January 2014

Problem

Prove that for any pair of positive integers $k$ and $n$, there exist $k$ positive integers $m_1,m_2,...,m_k$ (not necessarily different) such that

$1+\frac{2^k-1}{n}=(1+\frac{1}{m_1})(1+\frac{1}{m_2})...(1+\frac{1}{m_k})$.

Solution

We prove the claim by induction on $k$.

Base case: If $k = 1$ then $1 +\frac{2^1-1}{n} = 1 + \frac{1}{n}$, so the claim is true for all positive integers $n$.

Inductive hypothesis: Suppose that for some $m \in \mathbb{Z}^{+}$ the claim is true for $k = m$, for all $n \in \mathbb{Z}^{+}$.

Inductive step: Let $n$ be arbitrary and fixed. Case on the parity of $n$:

[Case 1: $n$ is even] $1 + \frac{2^{m+1} - 1}{n} = \frac{\frac{n}{2} + 2^{m} - 1}{\frac{n}{2}} \cdot \left( 1 + \frac{1}{n + 2^{m+1} - 2} \right)$

[Case 2: $n$ is odd] $1 + \frac{2^{m+1} - 1}{n} = \frac{\frac{n-1}{2} + 2^{m}}{\frac{n-1}{2} + 1} \cdot \left( 1 + \frac{1}{n} \right)$

In either case, $1 + \frac{2^{m+1} - 1}{n} = \frac{c + 2^m - 1}{c} \cdot \left( 1 + \frac{1}{a_{m+1}} \right)$ for some $c, a_{m+1} \in \mathbb{Z}^+$.

By the induction hypothesis we can choose $a_1, ..., a_m$ such that $\frac{c + 2^m - 1}{c} = \prod_{i=1}^{m} (1 + \frac{1}{a_i})$.

Therefore, since $n$ was arbitrary, the claim is true for $k = m+1$, for all $n$. Our induction is complete and the claim is true for all positive integers $n$, $k$.

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_IMO_Problems/Problem_1&oldid=58659"