Республиканская олимпиада по математике, 2015 год, 10 класс

Даны натуральные числа $k$, $\ell$ и ${{a}_{1}},{{a}_{2}},\ldots ,{{a}_{k}}$ $\left( \ell \ge 2 \right)$. Докажите, что для любого натурального $M$ существует натуральное число $x$, такое, что каждое из чисел $x$, $x+1$, $\dots$, $x+M-1$ не представимо в виде $a_i^n+m^{\ell}$, где $n$ и $m$ — целые неотрицательные числа $\left( 1\le i\le k \right)$. ( Сатылханов К. )

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

Здравствуйте, добрые люди!

Пожалуйста помогите с решением этой чудо-задачи.

Решение: Допустим для некоторого $M$ на любом отрезке $[x, x+M-1]$ есть число иского вида, $x\in \mathbb N.$

Оценим количество чисел искомого вида на отрезке $x=[1 ; X],$ где $X$ достаточно большое число. Рассмотрим 2 вида искомых чисел:

Случай 1. $(a_i^n=1)$ Если $a_i=1$ или $n=0.$ Заметим, что тогда

$$1+m^l\in x \iff 0\le m< X^{\frac{1}{l}}.$$

То есть на отрезке $x$ таких чисел не более $X^{\frac{1}{l}}+1.$

Случай 2. $(a_i^n > 1)$ Если $a_i>1, n>0.$ В этом случае если

$$a_i^n+m^l\in x \implies 2^{n}\le a_i^{n}\le X\implies 1\le n\le \log_2 X,$$

а так же $0\le m < X^{\frac{1}{l}}.$ Таких чисел не более $k\cdot \log_2 X \cdot (X^{\frac{1}{l}} + 1).$ (Поскольку для выбора $i$ сущ. не более $k$ вариантов)

$\\$

В общем чисел вида $a_i^n + m^l \in x$ не более $(X^{\frac{1}{l}}+1)\cdot(k\cdot\log_2 X + 1)<2X^{\frac{1}{l}}\cdot 2k\cdot \log_2 X=f(X).$

Но на отрезке $x$ их хотя бы $\dfrac{X}{M}-1>\dfrac{X}{2M}=g(X).$

Тогда $f(X)\ge g(X)\implies 8Mk \ge \dfrac{X^\varepsilon}{\log_2 X},$ где $\varepsilon=1-\frac 1 l>0.$ Но легко понять, что

$$\lim_{X\to +\infty} \dfrac{X^{\varepsilon}}{\log_2 X}= +\infty.$$

Противоречие.

MaTeX ждал это решение 4 года

Вам эта идея пришла после того как вы увидели решение 5-задачи на жауте? Кстати, сожалею что вам не хватило 1 балл до серебра.

Нет, я ее год назад решил. Написал сегодня

Рассмотрим числа от $1 $ до $N$. Если условие задачи неверно, то для всех $ N$ следует неравенство $N/M -1 \le log_m N \cdot \sqrt[n]{N}$. Что неверно.

Решение. Предположим обратное. Пусть $x_j$ - упорядоченная последовательность чисел вида $a_i^n+m^l, i=1,\dots,k$.

Утверждение. $x_j<s\Rightarrow j<k\sqrt{s}\log_2(s)$

Оценим количество чисел вида $a^n+m^l$, меньших $s$, для фиксированных $a,l$. При $a=1$ их количество не более $\sqrt[l]{s}<\sqrt{s}\log_2(s)$. В ином случае $a^n+m^l\ge2^n+m^l$. Всего есть не более $\log_2(s), \sqrt[l]{s}$ значений $n,m$, соответственно, значит таких чисел не более, чем $\sqrt{s}\log_2(s)$. Используем эту оценку для $a=a_1,\dots,a_k$, чтобы получить требуемое.$\square$

Теперь из условия $x_{i+1}-x_i\le M$, поскольку иначе между ними найдется $M$ целых чисел. Значит $$x_n\le C\cdot n\Rightarrow n<k\sqrt{Cn}\log_2(Cn)\Rightarrow \sqrt{n}<\text{const}\cdot \log_2(n)$$что очевидно неверно при достаточно больших $n$