Question

Даны натуральные числа n и k такие, что 1 < k < n. Мальвина приказала Буратино записать n натуральных чисел таких, что любые k из них имеют общий делитель, больший 1, а любые k + 1 - нет. Всегда ли выполнимо это задание?

Answer 1

Ответ: Да, всегда выполнимо.

Пример для любых n>k>1:

Возьмем n единиц.

Каждые k из них умножим на простое число. (каждый набор из k чисел умножаем на разное простое число, простых чисел бесконечно, а наборов С из n по k).

Полученный набор чисел удовлетворяет условиям:

1) Любые k из имеют общий делитель, больший 1.

Условие (1) Выполняется, т. к. любые k из них делятся на какое-то простое число (из построения примера).

2) Любые k+1 число из них не имеют общий делитель, больший 1, т. е. их наибольший общий делитель равен 1.

Допустим, что это условие не выполняется, найдутся k+1 число с наибольшим общим делителем, не равным 1.

Тогда их наибольший общий делитель раскладывается на простые множители.

На каждый из этих простых множителей делится не более k чисел в наборе из условия построения примера.

Следовательно ни на один из этих простых множителей не делятся все k+1 число. Противоречие, значит условие (2) выполняется.

Answer 2

Да, всегда выполнимо это задание. Для любых натуральных чисел n и k, где 1 < k < n, можно записать n натуральных чисел с заданными свойствами.

Рассмотрим следующую последовательность n чисел:

1. Начнем со значения 2, так как это наименьшее простое число, и все простые числа больше 1 удовлетворяют условию (имеют только один делитель - себя самого).
2. Далее, заполним последовательность простыми числами в возрастающем порядке: 2, 3, 5, 7, 11, 13, 17, и так далее.

Такая последовательность удовлетворяет условиям задания:

1. Любые k чисел из последовательности, где 1 < k < n, будут иметь общий делитель, больший 1. Поскольку k всегда меньше n, нам необходимо рассмотреть только k чисел из последовательности. Эти числа будут первыми k простыми числами (2, 3, 5, ..., p_k, где p_k - k-ое простое число). Все эти числа имеют общий делитель, равный 1, так как они простые.
2. Любые k + 1 чисел из последовательности не будут иметь общего делителя, большего 1. Это также верно, так как если мы возьмем любые k + 1 чисел из последовательности простых чисел, то последнее число в этой подпоследовательности будет следующим простым числом после k-го простого числа. Но следующее простое число всегда будет иметь только один общий делитель с предыдущим простым числом, и это число будет равно 1.

Таким образом, существует последовательность из n натуральных чисел, которая удовлетворяет заданным условиям для любых натуральных чисел n и k, где 1 < k < n.