Question

Какое наибольшее количество не делящихся на 4 натуральных чисел, меньших 850, можно выбрать таким образом, чтобы у любых двух выбранных был общий делитель, больший 1?

Answer 1

Оценка:

Докажем, что больше 213 чисел выбрать нужным образом не удастся. Пусть мы выбрали хотя бы 214 чисел. Тогда хотя бы в одной из троек чисел [1, 2, 3], [5, 6, 7], ... , [849, 850, 851] (для удобства добавил "850" и "851", нужных чисел от этого меньше не станет) будет выбрано хотя бы два числа. Но они не имеют общих делителей, так как либо отличаются на 1, либо на 2 и оба - нечётные. Значит, нужным образом можно выбрать не более 213 чисел.

Пример:

Выберем все числа, делящиеся на 3. Они все имеют делитель 3, следовательно, удовлетворяют условию. Из каждой тройки мы выбрали ровно одно число, причём из последней было выбрано число 849. Всего троек чисел было 213, следовательно, 213 чисел выбрать можно.

Ответ: 213 чисел.

Answer 2

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

Обратим внимание на то, что число 850 делится на 2 и 5, поскольку оно оканчивается на 0. Чтобы гарантировать, что у двух чисел будет общий делитель, больший 1, необходимо, чтобы выбранные числа не имели делителей, отличных от 2 и 5.

Возьмем все простые числа, меньшие 850, которые не делятся на 4: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83.

Всего таких чисел получилось 23.