54-я Международная Математическая OлимпиадаКолумбия, Санта Марта, 2013 год

Докажите, что для любой пары натуральных чисел $k$ и $n$ существуют $k$ (не обязательно различных) натуральных чисел ${{m}_{1}},{{m}_{2}},\ldots ,{{m}_{k}}$, удовлетворяющих равенству $$1+\dfrac{{{2}^{k}}-1}{n}=\left( 1+\dfrac{1}{{{m}_{1}}} \right)\left( 1+\dfrac{1}{{{m}_{2}}} \right)\ldots \left( 1+\dfrac{1}{{{m}_{k}}} \right).$$

Комментарий/решение

Будем делать индукцию по $k$:

$k=1$: берем $m_1 = n$ и получаем всё что надо для всех $n$

Далее пусть для $k=x$ мы можем выбрать такие $m_1, m_2 \cdots , m_x$, что для любого натурального $n$ будет выполняться равенство, которое надо доказать.

Теперь посмотрим на $k=x+1$:

1 случай: Выберем $m_{x+1} = 2n-1$, тогда:$$(1+\dfrac{1}{m_{x+1}})(\dfrac{n+2^x-1}{n})=(\dfrac{2n}{2n-1})(\dfrac{n+2^x-1}{n})=(\dfrac{2n-1+2^{x+1}-1}{2n-1})$$

Из выше описанного, мы можем сказать, что для пары чисел $(x+1;2n-1)$, где $2n-1$ - любое нечетное натуральное число, мы сможем найти такие $m_1, m_2 \cdots , m_{x+1}$ чтобы равенство из условия выполнялось.

2 случай: Выберем $m_{x+1} = 2n+2^{x+1}-2$, тогда $$(1+\dfrac{1}{m_{x+1}})(\dfrac{n+2^x-1}{n})=(\dfrac{2n+2^{x+1}-1}{2n+2^{x+1}-2})(\dfrac{n+2^x-1}{n})=(\dfrac{2n+2^{x+1}-1}{2n})$$

Из выше описанного, мы можем сказать, что для пары чисел $(x+1;2n)$, где $2n$ - любое четное натуральное число, мы сможем найти такие $m_1, m_2 \cdots , m_{x+1}$ чтобы равенство из условия выполнялось.

Сл-но, для всех $n$ при $k=x+1$ мы можем найти такие $m_1, m_2 \cdots , m_{x+1}$ чтобы равенство из условия выполнялось. А зн-т мы доказали индукцию по $k$.

Задача доказана.