Задача
У каждого целого числа от n + 1 до 2n включительно (n – натуральное) возьмём наибольший нечётный делитель и сложим все эти делители.
Докажите, что получится n².
Решение
Решение 1: Индукция по n. База (n = 1) очевидна.
Шаг индукции. Заменив в наборе чисел от n + 1 до 2n число n + 1 на 2n + 2 и добавив 2n + 1, получим набор чисел от n + 2 до 2(n + 1). Замена суммы делителей не изменит, так как у чисел n + 1 и 2(n + 1) наибольшие нечётные делители одинаковы. Нечётное же число 2n + 1 само добавится к сумме, увеличив её с n² до (n + 1)².
Решение 2: Частное двух чисел, имеющих одинаковый наибольший нечётный делитель, есть степень двойки. Но 2n/n+1 < 2, поэтому среди данного набора таких чисел нет, то есть все их наибольшие нечётные делители различны. Поскольку их ровно n и они не превосходят 2n – 1, то это – все нечётные числа от 1 до 2n – 1. 1 + 3 + ... + (2n – 1) = n².
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь