Задача 65396
|
|
 |
Условие
Докажите, что любое натуральное число можно представить в виде 3u12v1 + 3u22v2 + ... + 3uk2vk, где u1 > u2 > ... > uk ≥ 0 и 0 ≤ v1 < v2 < ... < vk – целые числа.
Решение
Индукция. База (n = 1) очевидна.
Шаг индукции. Пусть n = 2m. Число m можно представить в указанном виде. Увеличив все vi на 1, получим представление числа n.
Пусть n нечётно. Возьмём v0 = 0. Рассмотрим наибольшее u0, при котором 3u0 ≤ n. Если неравенство строгое, то представим число l = n – 3u0 в указанном виде. При этом v1 > 0, поскольку l чётно, а u1 < u0, потому что l < 3u0+1 – 3u0 = 2·3u0.
Замечания
4 балла
