На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится троичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры троичной записи, и остаток от деления суммы на 3 дописывается в конец числа (справа). Например, запись 2102 преобразуется в запись 21022;
б) над этой записью производятся те же действия: справа дописывается остаток от деления суммы цифр на 3.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является троичной записью искомого числа R. Укажите минимальное число R, которое превышает 82 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
1) Проанализируем работу алгоритма. А именно рассмотрим, какие цифры могут быть дописаны к исходному числу в результате его работы. Заметим, что возможные остатки от деления на 3 могут быть равны 0, 1 или 2.
Остаток 0 может быть получен только в случае, когда сумма цифр делится на 3. В этом случае после второго шага алгоритма также будет получен 0. В результате работы алгоритма последними двумя разрядами в полученном числе будут 00.
Остаток 1 может быть получен только в случае, когда сумма цифр может быть представлена в виде 3k + 1, где k —натуральное число. В этом случае после второго шага алгоритма будет получено число на 1 больше предыдущего, то есть представимое в виде 3k + 1 + 1 = 3k + 2. Остаток от деления на 3 такого числа равен 2. В результате работы алгоритма последними двумя разрядами в полученном числе будут 12.
Остаток 2 может быть получен только в случае, когда сумма цифр может быть представлена в виде 3k + 2, где k —натуральное число. В этом случае после второго шага алгоритма будет получено число на 2 больше предыдущего, то есть представимое в виде 3k+2+2 = 3k+3+1 = 3k1+1.
Остаток от деления на 3 такого числа равен 1. В результате работы алгоритма последними двумя разрядами в полученном числе будут 21.
2) По условию задачи требуется найти наименьшее число, превышающее 82. Возьмём наименьшее возможное число 83. Рассмотрим, может ли быть это число результатом работы алгоритма. Переведём это число в троичную систему счисления 8310 = 34 + 2 = 100023. Согласно алгоритму, последние две цифры 02 этого числа были приписаны к исходному. Согласно рассуждений, приведённых выше, такие числа не могут быть дописаны в результате работы алгоритма.
Построим упорядоченную возрастающую последовательность троичных чисел, начиная с числа 10002, в которой каждое последующее двоичное число на 1 больше предыдущего: 10002, 10010, 10011, 10012, 10020 . . . .
Для поиска числа R среди этой последовательности, будем искать наименьшее, в котором сумма цифр (за исключением двух последних) кратна 3 и число оканчивается на 00, или сумма цифр (за исключением двух последних) при делении на 3 даёт в остатке 1 и число оканчивается на 12, или сумма цифр (за исключением двух последних) при делении на 3 даёт в остатке 2 и число оканчивается на 21. Таким числом является 10012.
Переведём это число в десятичную систему счисления 100123 = 1 · 34 + 0 · 33 + 0 · 32 + 1 · 31 + 2 · 30 = 81 + 3 + 2 = 86.
Ответ: 86