Числа с общим делителем

[Ktina]

а) Иришка выписывает в ряд натуральные числа. Каждое следующее число больше предыдущего на 1, на 2, на 3 или на 4. Докажите, что рано или поздно в этом ряду появятся 2014 чисел (не обязательно идущих подряд), имеющих общий делитель больше 1.

б) Сардаана выписывает в ряд натуральные числа. Каждое следующее число больше предыдущего на 1, на 2, на 3, на 4, на 5 или на 6. Верно ли, что рано или поздно в этом ряду появятся 2014 чисел (не обязательно идущих подряд), имеющих общий делитель больше 1?

в) Существует ли такое натуральное число $n$, заменив которым числа 4 и 6 в пунктах а) и б) соответственно, можно получить отрицательный ответ на задачу?

[Руст]

Ktina в сообщении #838512 писал(а):

а) не обязательно идущих подряд

Так задача делается тривиальной и даже можно усилить.
Для любых n,N,k чисел, каждое последующее больше предыдущего больше на величину, не превосходящую k, существует n чисел (не обязательно подряд идущих), что они имеют общий делитель больше $N$.

[Shadow]

Ktina в сообщении #838512 писал(а):

а) Иришка выписывает в ряд натуральные числа. Каждое следующее число больше предыдущего на 1, на 2, на 3 или на 4. Докажите, что рано или поздно в этом ряду появятся 2014 чисел (не обязательно идущих подряд), имеющих общий делитель больше 1.

Например четверку последовательных чисел $30k-5,30k-4,30k-3,30k-2$ нельзя "перепрыгнуть", а каждое из них имеет делитель 2,3 или 5.

Руст в сообщении #838551 писал(а):

существует n чисел (не обязательно подряд идущих), что они имеют общий делитель больше $N$.

Типа того:
$a!-(N+1),a!-(N+2),\cdots, a!-(N+k)$ при $a \ge N+k$
Там...факториал, праймориал, с плюсами, с минусами...

[guas]

Гм. Слова "так задача делается тривиальной" вызывают нездоровый интерес. В смысле, можно всё-таки найти 2014 ПОСЛЕДОВАТЕЛЬНЫХ взаимно простых членов? При том, что можно, скажем, прибавлять 1?
Чтобы скрыть основной мотив комментирования, сообщаю решение п. б): в натуральном ряду можно (*) найти бесконечно много отрезков из 6 (в варианте Руста - $k$) последовательных натуральных чисел, каждое из которых делится на одно из данных 6 ($k$) простых. Поскольку проскочить такой отрезок наша последовательность не может, мы наберём сколько угодно членов, каждый из которых делится на одно из данных шести ($k$) простых. Значит, по принципу Дирихле, наберём и сколько угодно членов, делящихся на какое-то одно из них.
Утверждение (*) для Руста следует из китайской теоремы об остатках (ну, или без неё - возьмём отрезок от $(k+1)!m+2$ до $(k+1)!m+k+1$), для Иришки можно предъявить (сэкономив одно простое) числа $30m+3$, $30m+4$, $30m+5$, $30m+6$, Сардаане подойдут числа от $210m+3$ до $210m+7$.
А теперь главный вопрос к топикстартеру - откуда в Эрец Исраэль Сардаана? Признавайтесь, Вы из Якутии?

[Ktina]

Shadow в сообщении #838579 писал(а):

Типа того:
$a!-(N+1),a!-(N+2),\cdots, a!-(N+k)$ при $a \ge N+k$
Там...факториал, праймориал, с плюсами, с минусами...

Верно. За каждым достаточно большим факториалом гуськом следуют числа делящиеся на 1, 2, 3, ... n.
Единичку считать не станем, посчитаем 2, 3, 4, ... n+1. При этом очередным ходом перескочить через эти числа невозможно, так как длина хода не превышает n. А поскольку каждый из делителей (2, 3, 4, ... n+1) должен встретиться не более 2013 раз, всего можно сделать лишь конечное число таких "не-перескакиваний".
Как-то так...

-- 20.03.2014, 00:17 --

(Оффтоп)

guas в сообщении #838580 писал(а):

А теперь главный вопрос к топикстартеру - откуда в Эрец Исраэль Сардаана? Признавайтесь, Вы из Якутии?

По месту рождения - из Якутии. По месту проживаания - из Израаиля.
А Сардаану ничто не мешает привезти в Израаиль и посадить
Я, разумеется, о цветке:

[Руст]

Задача тривиальная в том смысле, что для любого х, хотя бы одно из чисел $x+1, x+2,...,x+k$ принадлежит последовательности.
Возьмем числа взаимно простые $M_1,M_2,...,M_k$ большие $N$ (например соответствующие простые).
Найдем число $x_0=-i\mod M_i$. Тогда для любого числа $x_j=x_0+jM, M=M_1*M_2...*M_k$
Последующий член последовательности делится на одно из $M_i$.
Берем члены последовательности $a_{i_j}$ непосредственно следующие после $x_j$ при $j=0,1,...,(n-1)k$.
Так как среди них (всего (n-1)k - чисел) найдется n, таких что $a_{i_j}=l\mod M$. Соответственно все они делятся на $M_l>N$.