|
|
 |
Условие
Для n = 1, 2, 3 будем называть числом n-го типа любое число, которое либо равно 0, либо входит в бесконечную геометрическую прогрессию
1, (n + 2), (n + 2)², ..., либо является суммой нескольких различных её членов. Докажите, что любое натуральное число можно представить в виде суммы числа первого типа, числа второго типа и числа третьего типа.
Решение 1
Пусть a1, a2, a3, ... – неубывающая последовательность натуральных чисел. Для k ≥ 2 обозначим через Sk = a1 + ... + ak–1 сумму k – 1 первых членов этой последовательности и положим S1 = 0.
Докажем, что каждое натуральное число представимо в виде суммы различных членов последовательности {ak} тогда и только тогда, когда для любого k выполнено неравенство ak ≤ Sk + 1 (*).
Действительно, если ak > Sk + 1, то натуральное число Sk + 1 нельзя представить в требуемом виде.
Для проверки достаточности докажем по индукции, что любое натуральное число от 1 до Sk включительно можно представить в требуемом виде, используя только члены a1, a2, ..., ak–1.
База. Из неравенства a1 ≤ S1 + 1 = 1 следует, что a1 = 1, S2 = a1 = 1 и для k = 2 утверждение верно.
Шаг индукции. Без использования ak мы, по индукционному предположению, можем получить все числа от 1 до Sk. Добавляя ak к этим числам, мы сможем получить все натуральные числа от ak + 1 до ak + Sk = Sk+1, и само ak также представимо в нужном виде. Отрезки [1, Sk] и [ak, Sk+1] покрывают
все натуральные числа от 1 до Sk+1.
В исходной задаче последовательность {ak}, состоит из членов геометрических прогрессий 1, 3, 3², 3³, ..., 1, 4, 4², 4³, ... и 1, 5, 5², 5³, ..., расположенных в порядке неубывания: 1, 1, 1, 3, 4, 5, 9, 16, 25, 27, ...
Проверим неравенство (*). Для k = 1, 2, 3 оно выполнено ввиду a1 = a2 = a3 = 1. Пусть для k > 3 сумма Sk состоит ровно из n членов первой геометрической прогрессии (от 30 до 3n–1), m – второй (от 40 до 4m–1) и l – третьей (от 50 до 5l–1). Тогда следующее число последовательности ak равно минимальному из чисел
3n, 4m, 5l. Имеем
Решение 2
Индукция. База. Непосредственной проверкой убедимся в том, что для чисел 1, 2, ..., 9 доказываемое утверждение верно.
Шаг индукции. Пусть N > 9. и для всех натуральных чисел, меньших N, утверждение уже доказано.
Пусть 3k, 4l и 5m – наибольшие из членов указанных в условии трёх прогрессий, не превосходящие N. Если N < 2·3k, то N – 3k < 3k. Число N – 3k можно по предположению индукции представить в виде суммы чисел трёх типов. Прибавляя к числу первого типа 3k, мы (поскольку N – 3k < 3k) получим новое число первого типа, сумма которого с прежними числами второго и третьего типов будет равна N. Аналогично можно получить представление числа N в виде суммы чисел трёх типов, когда N < 2·4l или N < 2·5m.
Пусть теперь N ≥ max {2·3k, 2·4l, 2·5m}. Обозначим через a, b и c соответственно наибольшее, среднее и наименьшее из чисел 3k, 4l и 5m. Тогда
N/2 ≥ a ≥ b ≥ c и N – a – b > 0. Если N – a – b < c, то, представляя число N – a – b в виде суммы чисел трёх типов и добавляя к соответствующим слагаемым числа a и b, мы получим нужное представление числа N. Если же N – a – b ≥ c, то или N = a + b + c (и требуемое представление уже получено), или N – a – b – c > 0. В последнем случае либо N – a – b – c < c (и тогда требуемое представление числа N можно получить из представления в виде суммы для числа N – a – b – c), либо N – a – b – c ≥ c.
Так как 3k+1 > N, 4l+1 > N и 5m+1 > N, то c > N/5, и в последнем случае
N – a – b – c ≥ c > N/5 > N/6 ≥ 3k–1 и N – a – b – c < N – N/3 – N/4 – N/5 < 2N/9 < 2· 3k–1.
Итак, 0 < N – a – b – c – 3k–1 < 3k–1 . Представив N – a – b – c – 3k–1 в виде суммы чисел трёх типов и добавив затем к первому числу 3k–1 + 3k, ко второму – 4l, а к третьему – 5m, получим требуемое представление для числа N.