Высшая проба 2021, 11 класс, задача 2
( баллов) В последовательности чисел некоторые члены умножили на , причем известно, что осталось бесконечно много положительных членов. Докажите, что любое натуральное число представимо в виде суммы нескольких различных членов полученной последовательности.
Решения. Будем называть последовательность, удовлетворяющую условию задачи ПУУЗ.
Первое решение. Заметим, что следующая операция из ПУУЗ делает ПУУЗ: из последовательности выкидываем первый член, а все остальные делим на . В самом деле, все члены остались плюс или минус степенями двойки, и положительных все еще бесконечно. Назовем эту операцию сокращением.
Докажем по индукции утверждение: любое натуральное для любой ПУУЗ представляется в виде суммы некоторых ее различных членов.
База. Докажем что в таком виде представляется . В самом деле, у любой ПУУЗ есть положительные члены, пусть первый из них . Тогда заметим что .
Переход. Пусть утверждение доказано для всех натуральных чисел, меньших . Рассмотрим и ПУУЗ . Если четное - представим в виде суммы нескольких различных членов сокращения , этому представлению соответствует представление в виде суммы различных членов . Если нечетное - вычтем из него первый член (который равен или ) и результат поделим пополам. Мы получили одно из чисел , оно натуральное и строго меньше , значит для него уже доказано, что оно представляется в виде суммы различных членов произвольной ПУУЗ, в частности - сокращения . Снова строим соответствующее представление в виде суммы различных членов .
Второе решение. Зафиксируем произвольную ПУУЗ . Докажем более сильное утверждение:
Лемма . Для произвольного натурального или нулевого множество целых чисел, представимых в виде суммы некоторых различных членов последовательности выбранных из первых , есть отрезок длины .
Замечание. Как всегда, когда речь идет о подмножествах множества целых чисел, длинной отрезка мы называем число целых чисел на нем, а не его геометрическую длину. Так, отрезок имеет длину а не . Так же как всегда будем считать, что сумма пустого множества слагаемых равна нулю.
Докажем сформулированное утверждение по индукции. База: для утверждение верно, поскольку представим только , одно целое число это отрезок длины . Переход. Пусть утверждение доказано для некоторого , то есть числа, представимые в виду суммы различных членов последовательности , образуют отрезок . Рассмотрим все числа, представимые как суммы различных членов, выбранных из . Заметим, что любое представление или не включает , и тогда представляет какое-то число из , или включает, и тогда представляет какое-то число из . Вспомним что и посмотрим, чему равно объединение двух вышеозначенных отрезков в обоих случаях. Заметим, что оно - всегда отрезок (два отрезка легли в точности в стык), и его длина всегда . Переход доказан.
Выведем из доказанного утверждения задачу. По условию, положительных членов бесконечно много. Тогда мы можем выбрать так, чтобы сумма положительных членов была больше любого наперед заданного числа . Но для этого в виде суммы различных членов последовательности (из первых ) представляется и (как сумма пустого множества), и сумма всех положительных членов среди первых , а по Лемме - и все числа между и всеми положительными, в частности - все число от до . В силу произвольности мы доказали, что все натуральные числа представляются
A0Любойпроцесс,конечностькоторогонеочевидна(например,алгоритмидетпоразрядам в бесконечную сторону), при том что в работе конечность не доказывается.
A1 Процесс, конечность которого очевидна (например, сразу выделяется конечное число кусков, в которых будут лежать все ненулевый знаки представления, далее куски только объ- единяются или сокращаются, но никогда не напарщиваются в бесконечную сторону), однако в описании процесса пропущен случай, разбирающийся аналогично разобранным.
B1 Приведено верное явное описание представления, но не доказано, что таким образом представлено именнно требуемое число:Комментарий:Вбольшинстверешений,гдепредставлениестроилосьврезультатепроцесса, достаточно очевидно, что если процесс завершается то результат представляет именно требуе- моечисло,врешенияхчерезявныйвидэтокакправилонеочевидно,ипримерноэквивалентно по сложности доказательству того, что процесс завершается за конечное число шагов.