Условие
Какое наибольшее количество чисел можно выбрать из набора
1, 2,..., 1963,
чтобы сумма никаких двух чисел не делилась на их разность?
Решение
Покажем, сначала, что из данного набора можно
выбрать требуемым способом 655 чисел. В самом деле, возьмём все числа вида
3
k + 1;
k = 0, 1,..., 654. Разность любых двух таких чисел, очевидно,
делится на 3, в то время как сумма любых двух из них дает при делении на 3
остаток 2. Отсюда следует, что сумма никаких двух чисел из выбранных нами не
делится на их разность, т. е. выбор произведён правильно.
Покажем теперь, что выбор большего количества чисел, удовлетворяющих условиям
задачи, невозможен. Действительно, если бы мы выбрали больше, чем 655 чисел,
то нашлись бы два числа, отличающихся друг от друга менее, чем на 3 (в
противном случае разность между наибольшими и наименьшими числами данного
набора была бы больше, чем
3×654 = 1962, что невозможно). Итак,
должны найтись два числа, отличающиеся друг от друга на 1 или на 2. В первом
случае разность между ними равна 1, а на 1 делится любое число, в том числе и
их сумма. Во втором случае разность между взятыми числами равна 2, и потому
оба эти числа имеют одинаковую чётность, а значит, их сумма — чётное число.
И в этом случае сумма взятых чисел делится на их разность.
Мы показали, что из данного набора нельзя выбрать более, чем 655 чисел так,
чтобы выполнялись условия задачи, и построили пример того, как можно выбрать
655 чисел. Следовательно, наибольшее количество чисел, которое можно выбрать
из данного набора в соответствии с условиями задачи, равно 655.
Источники и прецеденты использования
