---

Показать решение

---

Скрыть решение

Решение

Решим более общую задачу.
Задача. На доске написано натуральное число a₁. Затем на доску последовательно записываются натуральные числа. На (n – 1)-м шаге пишется любое число a_n, которое нельзя представить как ka₁ + a_i, где k — целое неотрицательное, а a_i — одно из ранее написанных чисел. Докажите, что процесс написания чисел конечный.
Решение. Допустим, что процесс бесконечный. Всё множество натуральных чисел, не кратных a₁, разобьём на отрезки A_i. К A_i отнесём все числа n такие, что ia₁ < n < (i + 1)a₁. Так как чисел, меньших a₁, конечное число, то в некоторый момент будет написано число, большее a₁; обозначим его через a₂, а все числа, написанные после a₁, но до a₂, не будем учитывать. По условию задачи, a₂ не есть кратное числа a₁. В дальнейшем на доску не будет выписано ни одно число вида a₂ + ka₁, где k — целое неотрицательное. Это значит, что во всех отрезках A_i, начиная с того, в котором находится a₂, одно число выбывает из игры (a2 находится в отрезке A_i2, где i₂ = [a₂ / a₁]).
В некоторый момент будет написано число, большее i₂a₁; обозначим его через a₃, а все числа, написанные после a₂, но до a₃, не будем учитывать. a₃ не кратно a₁ и не имеет вида a₂ + ka₁. Это значит, что во всех отрезках a_i, начиная с того, в котором находится a₃, ещё одно число выбывает из игры (a₃ находится в отрезке A_i3, где i₃ = [a₃ / a₁]).
Продолжая это рассуждение, приходим к тому, что во всех отрезках A_i, начиная с некоторого, все числа выбывают из игры. После этого можно написать на доске лишь конечное количество чисел. Получено противоречие.