|
|
 |
Условие
На доску последовательно записываются натуральные числа. На n-м шаге (когда написаны числа a1, a2, ..., an–1) пишется любое число, которое нельзя представить в виде суммы a1k1 + a2k2 + ... + an–1kn–1, где ki – целые неотрицательные числа (на a1 никаких ограничений не накладывается). Доказать, что процесс написания чисел не может быть бесконечным.
Решение
Предположим, что выписана бесконечная последовательность. Так как количество остатков от деления на a1 конечно, то какой то остаток встретится в этой последовательности бесконечное число раз, то есть найдётся бесконечная подпоследовательность b1, b2, ..., все члены которой имеют один остаток от деления на a1. По условию эта подпоследовательность строго убывает (поскольку bm+1 нельзя представить в виде bm + ka1). Но это невозможно.
Замечания
6 баллов
