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"
(Second solution)
Line 38: Line 38:
  
 
--[[User:alexander_skabelin|alexander_skabelin]] 9:24, 11 July 2023 (EST)
 
--[[User:alexander_skabelin|alexander_skabelin]] 9:24, 11 July 2023 (EST)
 +
 +
==Solution 2==
 +
Our solution is similar in spirit to the alternative solution. We will find <math>m_1,...,m_k</math> such that
 +
<cmath>
 +
n+2^k-1 = n\Big(1+\frac{1}{m_1}\Big)\cdots\Big(1+\frac{1}{m_k}\Big).
 +
</cmath>
 +
Write
 +
<cmath>
 +
S_j = n\Big(1+\frac{1}{m_1}\Big) \cdots \Big(1+\frac{1}{m_j}\Big)
 +
</cmath>
 +
and <math>S_0 = n</math>. Note if <math>l|r</math> then <math>r\Big(1+\frac{1}{r/l} \Big) = r+l</math>. Therefore if <math>S_j, j<k</math>, is an integer, if <math>l|S_j</math> then <math>m_{j+1}</math> can be chosen such that <math>S_{j+1} = S_j + l</math>. Thus one way to solve the problem is by finding a sequence <math>S_0,S_1,...,S_k = n+2^k-1</math> such that <math>S_{j+1} = S_j + l_j</math> where <math>l_j | S_j</math> for all <math>j < m</math>.
 +
 +
We claim by induction that one can choose <math>S_0,...,S_k=n+2^k-1</math> such that <math>\{l_0,...,l_{k-1}\} = \{1,2,...,2^{k-1}\}</math>.
 +
 +
Base case <math>k=1</math>: We may choose <math>l_0 = 1 | S_0</math> so that <math>S_0 = n, S_1 = n+1 = n + 2^1 - 1</math>.
 +
 +
Induction case: Suppose <math>S_0,...,S_{k-1} = n + 2^{k-1} - 1</math> and <math>\{l_0,...,l_{k-2}\} = \{1,2,...,2^{k-2}\}</math>. Say <math>l_j = 2^{k-2}</math>. Then either <math>S_j</math> or <math>S_{j+1}=S_j+2^{k-2}</math> will be divisible by <math>2^{k-1}</math>. Therefore our new sequence <math>S_0',...,S_k' = n+2^k-1</math> can be the same sequence as
 +
<cmath>
 +
S_0,...,S_j,S_j+2^{k-1},S_{j+1}+2^{k-1},...,S_{k-1} + 2^{k-1}
 +
</cmath>
 +
or
 +
<cmath>
 +
S_0,...,S_{j+1},S_{j+1}+2^{k-1},S_{j+2}+2^{k-1},...,S_{k-1} + 2^{k-1}
 +
</cmath>
 +
accordingly to which term is divisible by <math>2^{k-1}</math>. Of course if <math>l_p = 2^q</math> where <math>q<{k-1}</math> then <math>l_p | S_p + 2^{k-1}</math> so that the sequences will be valid.
 +
 +
~not_detriti
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Revision as of 23:27, 2 August 2025

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})$.

Video Solution(In Chinese, subtitled in English

https://youtu.be/QBF-_qrMBFI

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 prove the claim by constructing telescoping product out of positive integers: \[\frac{a_2}{a_1}\cdot\frac{a_3}{a_2}\cdot\frac{a_4}{a_3}\cdot \cdot \frac{a_{k+1}}{a_k} = \frac{a_{k+1}}{a_1} = \frac{\left(n+2^{k}-1\right)}{n}\] 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$, $0\le j \le (k-1)$. $\sum_{i=1}^{k}{\Delta_i}=\sum_{i=1}^{k}{2^{i-1}}=2^{k}-1$.

Ascend: make telescoping product of fractions with a sequence of $\Delta_i$ that increases in magnitude up to the maximum $2^{k-1}$. If the maximum $\Delta=2^{k-1}$ is reached go to the descend phase. Pull out factors of $2$ (up to the maximum $2^{k-1}$). $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+q+1}(2r+2)}{2^{j+q+1}(2r+1)} ...\]. The corresponding differences $\Delta$ are $2^j, 2^{j+q+1}$ ... Every $\Delta_i$ is bigger then the previous $\Delta_{i-1}$ by at least factor $2$. Therefore, the biggest needed $\Delta=2^{k-1}$ can be created telescoping at most $k$ fractions. After we constructed the fraction $\frac{2^{k-1}(h+1)}{2^{k-1}h}$ with the biggest needed $\Delta=2^{k-1}$ we can construct any remaining needed $\Delta_i$ as described below.

Descend: If we need $\Delta=2^{d}$ where $d<k-1$ we can use as the next telescoping fraction $\frac{2^{d}(2^{k-1-d}(h+1)+1)}{2^{d}(2^{k-1-d}(h+1))}$. We can construct all the remaining nedded $\Delta_i$ in the decreasing order of their magnitude by repeating the same step.

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

Solution 2

Our solution is similar in spirit to the alternative solution. We will find $m_1,...,m_k$ such that \[n+2^k-1 = n\Big(1+\frac{1}{m_1}\Big)\cdots\Big(1+\frac{1}{m_k}\Big).\] Write \[S_j = n\Big(1+\frac{1}{m_1}\Big) \cdots \Big(1+\frac{1}{m_j}\Big)\] and $S_0 = n$. Note if $l|r$ then $r\Big(1+\frac{1}{r/l} \Big) = r+l$. Therefore if $S_j, j<k$, is an integer, if $l|S_j$ then $m_{j+1}$ can be chosen such that $S_{j+1} = S_j + l$. Thus one way to solve the problem is by finding a sequence $S_0,S_1,...,S_k = n+2^k-1$ such that $S_{j+1} = S_j + l_j$ where $l_j | S_j$ for all $j < m$.

We claim by induction that one can choose $S_0,...,S_k=n+2^k-1$ such that $\{l_0,...,l_{k-1}\} = \{1,2,...,2^{k-1}\}$.

Base case $k=1$: We may choose $l_0 = 1 | S_0$ so that $S_0 = n, S_1 = n+1 = n + 2^1 - 1$.

Induction case: Suppose $S_0,...,S_{k-1} = n + 2^{k-1} - 1$ and $\{l_0,...,l_{k-2}\} = \{1,2,...,2^{k-2}\}$. Say $l_j = 2^{k-2}$. Then either $S_j$ or $S_{j+1}=S_j+2^{k-2}$ will be divisible by $2^{k-1}$. Therefore our new sequence $S_0',...,S_k' = n+2^k-1$ can be the same sequence as \[S_0,...,S_j,S_j+2^{k-1},S_{j+1}+2^{k-1},...,S_{k-1} + 2^{k-1}\] or \[S_0,...,S_{j+1},S_{j+1}+2^{k-1},S_{j+2}+2^{k-1},...,S_{k-1} + 2^{k-1}\] accordingly to which term is divisible by $2^{k-1}$. Of course if $l_p = 2^q$ where $q<{k-1}$ then $l_p | S_p + 2^{k-1}$ so that the sequences will be valid.

~not_detriti

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

See Also

2013 IMO (Problems) • Resources
Preceded by
First Problem 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_IMO_Problems/Problem_1&oldid=256404"