На доске написано число 2015 и еще несколько (не менее двух) натуральных чисел, не превосходящих 5000. Все написанные на доске числа различны. Сумма любых двух из написанных чисел делится на какое-нибудь из остальных.
а) Может ли на доске быть написано ровно 1009 чисел?
б) Может ли на доске быть написано ровно пять чисел?
в) Какое наименьшее количество чисел может быть написано на доске?
Заметим, что если среди выписанных чисел есть число 1, то попарные суммы всех остальных чисел будут делиться на 1.
а) Может. Например, числа 1, 2, 3, 5, 7, ..., 2015 (выписано 1008 нечётных чисел от 1 до 2015 и число 2). Сумма 1 и любого нечётного числа делится на 2, сумма 1 и 2 делится на 3, сумма любых двух чисел, отличных от 1, делится
Другой пример: 1, 2, 3, ..., 1007, 2014, 2015. Если среди двух чисел нет 1, то их сумма делится на 1. Если вместе с 1 выписаны числа k и k + 1, то сумма первых двух делится на третье; оставшиеся суммы 1 + 1007 и 1 + 2015 делятся
Третий пример: 1, 2, 3, 5, 6, ... , 1009, 2015 (в группе подряд идущих чисел пропущено 4).
б) Может. Например, числа 1, 2, 3, 5, 2015. Другой пример — числа a, 2a, 3a, 4a, 5a, где a = 403.
в) Пример для четырёх чисел: 1, 2, 3, 2015. Другой пример — числа a, 2a, 3a, 5a, где a = 403.
Покажем, что трёх чисел быть не может. Действительно, пусть три различных числа таковы, что a < b < c. Тогда a + b < 2b < b + c < 2c, откуда в силу делимости суммы двух меньших чисел на большее получаем: a + b = c. Тогда b < a + c = 2a + b < 3b, откуда в силу делимости а + с на b получаем: a + c = 2b. Тогда b = 2a, c = 3a, а искомая тройка чисел имеет вид a, 2a, 3a. По условию одно из этих чисел равно 2015, поскольку 2015 не делится ни на 2, ни на 3, им может быть только число a. Но в этом случае 3a > 5000. Противоречие.
Приведём другое доказательство.
Пусть даны числа a, b, c, и сумма любых двух из них делится на третье. Если они все имеют отличный от 1 наибольший общий делитель d, то на него можно сократить, и свойство делимости сохранится. Будем считать, что все три числа взаимно простые. Поскольку сумма двух чисел делится на третье, то сумма всех чисел делится на каждое. Числа попарно взаимно просты, поэтому их сумма должна делиться на произведение. В частности, a + b + c ≥ abc. Полагая a < b < c, имеем a + b + c < 3c, откуда ab < 3. Следовательно, a = 1, b = 2. При этом c + 3 делится на 2c, поэтому c = 3. Таким образом, тройка чисел должна иметь вид d, 2d, 3d. Поскольку 2015 нечётно и не делится на 3, оно равно d, но тогда 3d > 5000.
Ответ: а) может, например числа 1, 2, 3, 5, 7, ..., 2015; б) может, например числа 1, 2, 3, 5, 2015; в) 4, например, 1, 2, 3, 2015.