Олимпиадная задача по теории чисел: множество без полных квадратов, классы 7–9
Задача
Существует ли 1000000 таких различных натуральных чисел, что никакая сумма нескольких из этих чисел не является полным квадратом?
Решение
Решение 1: Укажем такие числа. Первый способ. Возьмём простое число p, большее 1012. Искомые числа p, 2p, ..., 1000000p. Действительно, обозначим сумму некоторых n из них через S. Тогда S = kp, где k < 106·106 < p. Таким образом. S делится на p, но не делится на p², то есть не может быть полным квадратом. Второй способ. Возьмём числа 102k+1 (k = 1, 2, ..., 106). Сумма любого количества этих чисел заканчивается на нечётное число нулей и, значит, не является полным квадратом.
Решение 2: Будем строить искомые числа по индукции. База. Возьмём любое число, не являющееся полным квадратом.
Шаг индукции. Предположим, что n чисел x1, ..., xn уже выбраны. Положим xn+1 = z² + 1, где z > x1 + ... + xn. Тогда сумма любого количества этих чисел, содержащая xn+1, больше z², но меньше x1 + ... + xn + xn+1 + z < z² + 2z + 1 = (z + 1)² и потому не может быть полным квадратом.
Ответ
Существует.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь