Условие задачи
На доске написано число 2045 и ещё несколько (не менее двух) натуральных чисел, не превосходящих 5000. Все написанные на доске числа различны. Сумма любых двух из написанных чисел делится на какое-нибудь из остальных.
а) Может ли на доске быть написано ровно 1024 числа?
б) Может ли на доске быть написано ровно пять чисел?
в) Какое наименьшее количество чисел может быть написано на доске?
Решение
Пусть на доске 3 числа: x, y и z, при этом \(x \, \textless \, t \, \textless \, z\)
\(x+y \, \textless \, 2z \)
\((x+y) \vdots z.\)
Значит, \(x+y=z\)
Получили, что на доске числа \(x, y, x+y.\)
Заметим, что \((x+z) \vdots y\)
\((x+x+y)\vdots y,\) значит, \(2x \vdots y.\)
\(2x \, \textless \, 2y,\) тогда \(2x=y.\)
На доске написаны числа \(x, 2x, 3x.\)
Предположим, что на доске есть число 2045.
Если \(x = 2045,\) то \(3x \, \textgreater \, 5000\) (противоречие с условием)
\(2x = 2045\) или \(3x = 2045\) не может быть, так как 2045 не делится на 2 и на 3.
Значит, на доске не могут быть 3 числа, одно из которых 2045.
а) Припишем к 1. 2. 3 все нечётные числа до 2045 включительно: 1, 2, 3, 5, 7, ... , 2045. Тогда сумма двух нечётных чисел делится на 2. сумма 2 и 1 делится на 3, сумма двойки и большего числа делится на 1.
б) Ровно пять чисел могут быть написаны: 1, 2, 3, 5, 2045.
в) Ровно четыре числа могут быть написаны: 1, 2, 3, 2045. Три числа, как мы видели выше, написать нельзя. Значит, можно написать самое меньшее четыре числа.
Ответ
Ответ:
а) да
б) да
в) 4