На доске написано число 1025 и еще несколько (не менее двух) натуральных чисел, не превосходящих 3000. Все написанные на доске числа различны. Сумма любых двух из написанных чисел делится на какое-нибудь из остальных.
а) Может ли на доске быть написано ровно 514 чисел?
б) Может ли на доске быть написано ровно 5 чисел?
в) Какое наименьшее количество чисел может быть написано на доске?
Заметим, что если среди выписанных чисел есть число 1, то попарные суммы всех остальных чисел будут делиться на 1.
а) Может. Например, числа 1, 2, 3, 5, 7, ..., 1025 (выписано 513 нечётных чисел от 1 до 1025 и число 2). Сумма 1 и любого нечётного числа делится на 2, сумма 1 и 2 делится на 3, сумма любых двух чисел, отличных от 1, делится на 1.
Другой пример: 1, 2, 3, 4, ... , 513, 1025. Если среди двух чисел нет 1, то их сумма делится на 1. Если вместе с 1 выписаны числа k и k 1, то сумма первых двух делится на третье; оставшиеся суммы 1 + 513 и 1+ 1025 делятся на 2.
б) Может. Например, числа 1, 2, 3, 5, 1025. Другой пример — числа a, 2a, 3a, 4a, 5a, где a = 205.
в) Набор чисел 1, 2, 3, 1025 удовлетворяет условию. Докажем, что три числа взять нельзя.
Покажем, что трёх чисел быть не может. Действительно, пусть три различных числа таковы, что Тогда
откуда в силу делимости суммы двух меньших чисел на большее получаем: Тогда
откуда в силу делимости на b получаем:
Тогда
а искомая тройка чисел имеет вид a, 2a, 3a. По условию одно из этих чисел
Противоречие.
Ответ: а) да; б) да; в) 4, например, 1, 2, 3, 1025.

