Республиканская олимпиада по математике, 2015 год, 10 класс
Комментарий/решение:
Решение: Допустим для некоторого $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.$$
Противоречие.
Решение. Предположим обратное. Пусть $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$
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.