Processing math: 62%

Математикадан республикалық олимпиада, 2014-2015 оқу жылы, 10 сынып


Натурал k, және a1,a2,,ak (2) сандары берілген. Кез келген натурал M саны үшін, x, x+1, , x+M1 сандарының әрқайсысы ani+m (1ik) түрінде келмейтіндей натурал x саны табылатынын дәлелдеңіздер. Бұл жерде n және m теріс емес бүтін сандар. ( Сатылханов К. )
посмотреть в олимпиаде

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

  1
7 года 2 месяца назад #

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

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

  7
3 года 2 месяца назад #

Решение: Допустим для некоторого M на любом отрезке [x,x+M1] есть число иского вида, xN.

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

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

1+mlx0m<X1l.

То есть на отрезке x таких чисел не более X1l+1.

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

ani+mlx2naniX1nlog2X,

а так же 0m<X1l. Таких чисел не более klog2X(X1l+1). (Поскольку для выбора i сущ. не более k вариантов)

В общем чисел вида ani+mlx не более (X1l+1)(klog2X+1)<2X1l2klog2X=f(X).

Но на отрезке x их хотя бы XM1>X2M=g(X).

Тогда f(X)g(X)8MkXεlog2X, где ε=11l>0. Но легко понять, что

lim

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

пред. Правка 2   0
3 года 2 месяца назад #

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

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

пред. Правка 2   3
3 года 2 месяца назад #

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

  0
3 года 1 месяца назад #

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

  1
2 года 1 месяца назад #

Решение. Предположим обратное. Пусть 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