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 чисел.