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