Скрыть решение
Решение
Решим более общую задачу.
Задача. На доске написано натуральное число
a1. Затем на доску последовательно записываются натуральные числа. На (
n – 1)-м шаге пишется любое число
an, которое нельзя представить как
ka1 +
ai, где
k — целое неотрицательное, а
ai — одно из ранее написанных чисел. Докажите, что процесс написания чисел конечный.
Решение. Допустим, что процесс бесконечный. Всё множество натуральных чисел, не кратных
a1, разобьём на отрезки
Ai. К
Ai отнесём все числа
n такие, что
ia1 <
n < (
i + 1)
a1. Так как чисел, меньших
a1, конечное число, то в некоторый момент будет написано число, большее
a1; обозначим его через
a2, а все числа, написанные после
a1, но до
a2, не будем учитывать. По условию задачи,
a2 не есть кратное числа
a1. В дальнейшем на доску не будет выписано ни одно число вида
a2 +
ka1, где
k — целое неотрицательное. Это значит, что во всех отрезках
Ai, начиная с того, в котором находится
a2, одно число выбывает из игры (
a2 находится в отрезке
Ai2, где
i2 = [
a2 /
a1]).
В некоторый момент будет написано число, большее
i2a1; обозначим его через
a3, а все числа, написанные после
a2, но до
a3, не будем учитывать.
a3 не кратно
a1 и не имеет вида
a2 +
ka1. Это значит, что во всех отрезках
ai, начиная с того, в котором находится
a3, ещё одно число выбывает из игры (
a3 находится в отрезке
Ai3, где
i3 = [
a3 /
a1]).
Продолжая это рассуждение, приходим к тому, что во всех отрезках
Ai, начиная с некоторого, все числа выбывают из игры. После этого можно написать на доске лишь конечное количество чисел. Получено противоречие.