МОШ 2020, 9 класс, задача 6
Глеб задумал натуральные числа и , . Число он написал на доске. Затем он начал выполнять следующую операцию: делить с остатком на последнее выписанное на доску число, а полученный остаток от деления также записывать на доску. Когда на доске появилось число , он остановился. Мог ли Глеб изначально выбрать такие и , чтобы сумма выписанных чисел была больше ?
Ответ
Ответ. Да, мог.
Решение. Рассмотрим число и последовательность, которую Глеб мог выписать на доску. Исходное число обозначим через , а все последующие через . Из условия имеем при , а также , где через обозначены неполные частные от делений.
Мы хотим добиться выполнения неравенства .
Как нетрудно видеть, , откуда ; кроме того, . Следовательно, достаточно добиться выполнения неравенства .
Покажем, что существуют такие изначальные числа и , что при всех выполнено и . Если это удастся, то задача будет решена, так как неравенство , как известно, верно при достаточно больших (см. комментарий 1 в конце решения). Итак, мы выбрали неполные частные, осталось найти подходящие и . Заметим, что равенство , (1) дополненное неравенством , эквивалентно тому, что является остатком от деления на с неполным частным . Сначала выберем и . Далее определим все по формуле (1), начиная с конца. Часть из полученных чисел, возможно, окажутся рациональными; однако, как легко видеть, если и все домножить на произвольное число, равенства (1) сохранятся, как и условие последнего деления . Просто домножим и все на их общий знаменатель, и они станут целыми. Осталось убедиться, что все положительные и что . Для этого сначала докажем индукцией по , что . База очевидна, так как . Пусть мы доказали для , докажем для . Так как , то , а заменяя на согласно (1), получаем искомое .
Осталось заметить, что при
.
Это завершает доказательство того, что полученная последовательность искомая.
Комментарии. 1. Докажем, что для любого натурального можно выбрать несколько первых членов последовательности , чтобы их сумма была больше . Например, можно взять первые чисел. Действительно, их можно разбить на частей: в первой части число , во второй — числа и , в третьей — от до и т. д., то есть в -й части числа от до . Тогда для каждого от до в -ю часть попадут чисел, и их сумма будет не менее , поэтому сумма всех чисел окажется не менее .
-
Нетрудно видеть, что неполные частные возрастают с ростом , так как соотношение не может выполняться при и . Аналогично можно показать, что самое последнее частное хотя бы на больше предпоследнего. Отсюда ясно, что используемая выше последовательность в некотором смысле «минимальна».
-
Можно показать, что в качестве общего знаменателя, на который мы домножали полученные в решении числа , чтобы они стали целыми, можно было взять . Тогда нетрудно вычислить и
.