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"

(→‎Alternative Solution)
(→‎Alternative Solution)
Line 24: Line 24:
  
 
==Alternative Solution==
 
==Alternative Solution==
−
We will prove by constructing telescoping product of ratios of positive integers:
+
We will construct telescoping product out of positive integers:
 
<cmath>\frac{a_2}{a_1}\cdot\frac{a_3}{a_2}\cdot\frac{a_4}{a_3} \cdot  \frac{a_{k+1}}{a_k} = \frac{a_{k+1}}{a_1} = \frac{\left(a_1+2^{k}-1\right)}{a_1}</cmath>
 
<cmath>\frac{a_2}{a_1}\cdot\frac{a_3}{a_2}\cdot\frac{a_4}{a_3} \cdot  \frac{a_{k+1}}{a_k} = \frac{a_{k+1}}{a_1} = \frac{\left(a_1+2^{k}-1\right)}{a_1}</cmath>
−
where <math>a_1=n</math> and each fraction <math>\frac{a_{i+1}}{a_i}=\frac{a_{i}+\Delta_i}{a_i}</math> can also be written as <math>\frac{m_i+1}{m_i}</math> for some positive integer <math>m_i</math>. All <math>\Delta_i</math> will be different with <math>\Delta_i=2^j</math> for some <math>0\le j \le k-1</math>. As reqiured by telescoping (but not nessesarily in that order) <math>\sum_{i=1}^{k}{\Delta_i}=2^0+2^1+...+2^{k-1}=2^{k}-1</math>.
+
where <math>a_1=n</math> and where each fraction <math>\frac{a_{i+1}}{a_i}=\frac{a_{i}+\Delta_i}{a_i}</math> can also be written as <math>\frac{m_i+1}{m_i}</math> for some positive integer <math>m_i</math>. All <math>\Delta_i</math> will be different with <math>\Delta_i=2^j</math> for some <math>0\le j \le k-1</math>. <math>\sum_{i=1}^{k}{\Delta_i}=\sum_{i=1}^{k}{2^{i-1}}=2^{k}-1</math>.
 +
 
 +
Let's pull out factors of <math>2</math> if there are any:
 +
<math>n=2^j(2z+1)</math>, <math>z+1=2^q(2r+1)</math> etc where <math>j\ge 0</math>, <math>q\ge 0</math>.
 +
Construct telescoping as <math>\frac{2^j(2z+2)}{2^j(2z+1)}\cdot \frac{2^{j+1+q}(2r+2)}{2^{j+1+q}(2r+1)}</math>. Every <math>\Delta_i</math> can be bigger then previous <math>\Delta_{i-1}</math> by at least factor <math>2</math>. The biggest needed <math>\Delta=2^{k-1}</math> can be constructed in at most <math>k</math> steps.
 +
 
 +
<math>z+1=2^q(2r+1)</math> for <math>q\ge 0</math>, the next telescoping fraction is <math>\frac{2^j(2z+2)}{2^j(2z+1)}</math>
  
 
Fractions with <math>\Delta_i</math> of this form can be constructed in the following way. We will start buiding telescoping product by trying to construct the highest remaining required <math>\Delta_j</math> which is <math>2^{k-1}</math> at the beginning. If <math>n</math> is odd use fraction <math>\frac{n+1}{n}</math>, else you can use <math>\frac{\frac{n}{2}+1}{\frac{n}{2}}=\frac{n+2}{n}</math> which constructs <math>\Delta=2</math>.  If <math>{\frac{n}{2}}</math> is even we instead can use <math>\frac{\frac{n}{4}+1}{\frac{n}{4}}=\frac{n+2^2}{n}</math> which constructs <math>\Delta=2^2</math> etc. If finally <math>{\frac{n}{2^j}}</math> is odd and <math>j<k-1</math> then we use fraction <math>\frac{\frac{n}{2^j}+1}{\frac{n}{2^j}}=\frac{n+2^j}{n}</math> that has <math>\Delta=2^j</math>. In that case the next fraction from our telescoping series has denominator <math>\frac{n}{2^j}+1</math> which is even so we can take <math>\frac{\frac{\frac{n}{2^j}+1}{2}+1}{\frac{\frac{n}{2^j}+1}{2}}=\frac{n+3\cdot 2^j}{n+2^j}</math> which has <math>\Delta=2^{j+1}</math>. That is we can use at most one step ( one fraction from the telescoping product) to increase <math>\Delta</math> by factor of <math>2</math> from the <math>\Delta</math> in the previous fraction. In the worst case we will reach the highest <math>\Delta=2^{k-1}</math> using <math>k</math> steps ( <math>k</math> fractions in the telescoping product). All other needed <math>\Delta_i=2^{i-1}</math> would be already constructed by that time. In the best case <math>n= 2^q</math> where <math>q \ge k-1</math> and we can construct the highest needed <math>\Delta</math> using the very 1st fraction.
 
Fractions with <math>\Delta_i</math> of this form can be constructed in the following way. We will start buiding telescoping product by trying to construct the highest remaining required <math>\Delta_j</math> which is <math>2^{k-1}</math> at the beginning. If <math>n</math> is odd use fraction <math>\frac{n+1}{n}</math>, else you can use <math>\frac{\frac{n}{2}+1}{\frac{n}{2}}=\frac{n+2}{n}</math> which constructs <math>\Delta=2</math>.  If <math>{\frac{n}{2}}</math> is even we instead can use <math>\frac{\frac{n}{4}+1}{\frac{n}{4}}=\frac{n+2^2}{n}</math> which constructs <math>\Delta=2^2</math> etc. If finally <math>{\frac{n}{2^j}}</math> is odd and <math>j<k-1</math> then we use fraction <math>\frac{\frac{n}{2^j}+1}{\frac{n}{2^j}}=\frac{n+2^j}{n}</math> that has <math>\Delta=2^j</math>. In that case the next fraction from our telescoping series has denominator <math>\frac{n}{2^j}+1</math> which is even so we can take <math>\frac{\frac{\frac{n}{2^j}+1}{2}+1}{\frac{\frac{n}{2^j}+1}{2}}=\frac{n+3\cdot 2^j}{n+2^j}</math> which has <math>\Delta=2^{j+1}</math>. That is we can use at most one step ( one fraction from the telescoping product) to increase <math>\Delta</math> by factor of <math>2</math> from the <math>\Delta</math> in the previous fraction. In the worst case we will reach the highest <math>\Delta=2^{k-1}</math> using <math>k</math> steps ( <math>k</math> fractions in the telescoping product). All other needed <math>\Delta_i=2^{i-1}</math> would be already constructed by that time. In the best case <math>n= 2^q</math> where <math>q \ge k-1</math> and we can construct the highest needed <math>\Delta</math> using the very 1st fraction.

Revision as of 23:05, 11 July 2023

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} = \left( 1 + \frac{2^{m} - 1}{\frac{n}{2}} \right) \cdot \left( 1 + \frac{1}{n + 2^{m+1} - 2} \right)$

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

In either case, $1 + \frac{2^{m+1} - 1}{n} = \left( 1 + \frac{2^m - 1}{c} \right) \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 $\left( 1 + \frac{2^m - 1}{c} \right) = \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$.

Alternative Solution

We will construct telescoping product out of positive integers: \[\frac{a_2}{a_1}\cdot\frac{a_3}{a_2}\cdot\frac{a_4}{a_3} \cdot \frac{a_{k+1}}{a_k} = \frac{a_{k+1}}{a_1} = \frac{\left(a_1+2^{k}-1\right)}{a_1}\] where $a_1=n$ and where each fraction $\frac{a_{i+1}}{a_i}=\frac{a_{i}+\Delta_i}{a_i}$ can also be written as $\frac{m_i+1}{m_i}$ for some positive integer $m_i$. All $\Delta_i$ will be different with $\Delta_i=2^j$ for some $0\le j \le k-1$. $\sum_{i=1}^{k}{\Delta_i}=\sum_{i=1}^{k}{2^{i-1}}=2^{k}-1$.

Let's pull out factors of $2$ if there are any: $n=2^j(2z+1)$, $z+1=2^q(2r+1)$ etc where $j\ge 0$, $q\ge 0$. Construct telescoping as $\frac{2^j(2z+2)}{2^j(2z+1)}\cdot \frac{2^{j+1+q}(2r+2)}{2^{j+1+q}(2r+1)}$. Every $\Delta_i$ can be bigger then previous $\Delta_{i-1}$ by at least factor $2$. The biggest needed $\Delta=2^{k-1}$ can be constructed in at most $k$ steps.

$z+1=2^q(2r+1)$ for $q\ge 0$, the next telescoping fraction is $\frac{2^j(2z+2)}{2^j(2z+1)}$

Fractions with $\Delta_i$ of this form can be constructed in the following way. We will start buiding telescoping product by trying to construct the highest remaining required $\Delta_j$ which is $2^{k-1}$ at the beginning. If $n$ is odd use fraction $\frac{n+1}{n}$, else you can use $\frac{\frac{n}{2}+1}{\frac{n}{2}}=\frac{n+2}{n}$ which constructs $\Delta=2$. If ${\frac{n}{2}}$ is even we instead can use $\frac{\frac{n}{4}+1}{\frac{n}{4}}=\frac{n+2^2}{n}$ which constructs $\Delta=2^2$ etc. If finally ${\frac{n}{2^j}}$ is odd and $j<k-1$ then we use fraction $\frac{\frac{n}{2^j}+1}{\frac{n}{2^j}}=\frac{n+2^j}{n}$ that has $\Delta=2^j$. In that case the next fraction from our telescoping series has denominator $\frac{n}{2^j}+1$ which is even so we can take $\frac{\frac{\frac{n}{2^j}+1}{2}+1}{\frac{\frac{n}{2^j}+1}{2}}=\frac{n+3\cdot 2^j}{n+2^j}$ which has $\Delta=2^{j+1}$. That is we can use at most one step ( one fraction from the telescoping product) to increase $\Delta$ by factor of $2$ from the $\Delta$ in the previous fraction. In the worst case we will reach the highest $\Delta=2^{k-1}$ using $k$ steps ( $k$ fractions in the telescoping product). All other needed $\Delta_i=2^{i-1}$ would be already constructed by that time. In the best case $n= 2^q$ where $q \ge k-1$ and we can construct the highest needed $\Delta$ using the very 1st fraction.

--alexander_skabelin 9:24, 11 July 2023 (EST)

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

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