Наличие и отсутствие общих простых делителей

[Ktina]

Доказать, что для любых натуральных $2\leqslant k < m\leqslant n$
найдутся $n$ таких натуральных чисел, что у любых $k$ из них есть хотя бы один общий простой делитель, а у любых $m$ из них общих простых делителей нет.

[mihaild]

Индукцией по $n$ доказывается тривиально (как и построением сразу в лоб). Можно ли устроить индукцию скажем по $k$ и $m$?..

[Ktina]

mihaild
А можете без индукции? Например, существуют ли такие 2018 натуральных чисел, что у любых трёх из них есть хотя бы один общий простой делитель, а у любых четырёх из них общих простых делителей нет?

[mihaild]

Подсказка: минимальное из этих чисел не меньше $p_{C_{2017}^2}\#$.

[waxtep]

Можно представить эти числа как $n$ вертикальных стопок; каждая горизонталь - определенное простое число, свое для каждой горизонтали. Положим на самую нижнюю горизонталь по золотой монетке для каких-нибудь $k$ чисел из $n$, и по серебряной для остальных. На вторую горизонталь положим $k$ золотых монеток на другие $k$ мест (не полностю совпадающих с предыдущими), а на остальные снова серебряные. Будем делать так, пока не построим $n$ стопок высотой $C_n^k$: для любых $k$ стопок найдется горизонталь с $k$ золотыми монетками в этих стопках, и ни на одной горизонтали нет более $k$ золотых монеток

[Ktina]

mihaild
waxtep
Большое спасибо!

[JohnDou]

Можно воспользоваться следующими алгоритмом:
1) Возьмём массив $k$ одинаковых простых чисел $n_i$.
2) Добавим в него $x:=1$ и с каждым из $k-1$ домножим $x$ и $n_i$ на простое число, отличное от предыдущих.
3) Заменим числа из п.1 на полученные в п.2 и повторим процедуру.
Простых бесконечно много $\implies$ алгоритм реализуем. Массив растёт $\implies$ процедура конечна.

(Пример)

$n=4,\ k=3, \ m=4$
1) $[2_1, 2_2, 2_3]$
2) $[2_1, 2_2, 2_3]$: $3\cdot (1, 2_1, 2_2)$, $5\cdot (3, 2_1\cdot 3, 2_3)$, $7\cdot (3\cdot 5, 2_2\cdot 3, 2_3\cdot 5)$.
Повтор цикла:
1) Новый массив: $[30, 42, 70, 105]$
2) $[30, 42, 70, 105]$: $11\cdot (1, 30, 42)$, $13\cdot (11, 30\cdot 11, 70)$...

Не сложно написать программу для практических нужд.