На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится троичная запись числа N. 2) К этой записи дописываются справа ещё два разряда по следующему правилу: а) Вычисляется сумма цифр троичной записи числа, остаток от деления этой суммы на 3 дописывается в конец числа. б) Пункт а повторяется ещё раз с полученным числом. Например, запись 100 преобразуется в запись 10012; Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является троичной записью искомого числа R. Укажите минимальное число N, для которого результат работы алгоритма превышает 125. В ответе это число запишите в десятичной системе.

Решение:

Алгоритм преобразует троичную запись числа N в число R. Сначала найдём, каким должно быть число R в троичной системе, чтобы оно превышало 125 в десятичной системе. Минимальное такое число:

\( 125_{10} = ?_{3} \)

Делим 125 на 3:

• \( 125 : 3 = 41 \) остаток \( 2 \)
• \( 41 : 3 = 13 \) остаток \( 2 \)
• \( 13 : 3 = 4 \) остаток \( 1 \)
• \( 4 : 3 = 1 \) остаток \( 1 \)
• \( 1 : 3 = 0 \) остаток \( 1 \)

Таким образом, \( 125_{10} = 11122_{3} \). Следовательно, минимальное число R в троичной системе, превышающее 125, должно быть больше \( 11122_{3} \).

Число R получается путем добавления двух разрядов к троичной записи числа N. Пусть троичная запись N имеет длину \( k \) цифр. Тогда троичная запись R будет иметь длину \( k+2 \) цифры.

Шаг 1: Вычисление последнего разряда R.

Последний разряд R — это остаток от деления суммы цифр троичной записи N на 3. Обозначим троичную запись N как \( n_k n_{k-1} ... n_1 n_0 \). Сумма цифр \( S_1 = \sum_{i=0}^{k} n_i \). Последний разряд \( d_1 = S_1 \% 3 \).

Шаг 2: Вычисление предпоследнего разряда R.

Пункт а) повторяется с новым числом, которое получается после добавления \( d_1 \) к записи N. То есть, мы рассматриваем число, троичная запись которого \( n_k n_{k-1} ... n_1 n_0 d_1 \). Сумма цифр этого числа \( S_2 = S_1 + d_1 \). Предпоследний разряд \( d_2 = S_2 \% 3 \). Таким образом, R в троичной системе будет иметь вид \( n_k n_{k-1} ... n_1 n_0 d_2 d_1 \).

Нам нужно найти минимальное N, такое что \( R > 125_{10} \), то есть \( R_{3} > 11122_{3} \). Поскольку R имеет на два разряда больше, чем N, то R будет как минимум \( 100_{3} \) (если N = 1, N в троичной = 1, R = 100, что равно 9 в десятичной).

Ищем минимальное N. Начнем с N, троичная запись которого будет иметь длину 3 цифры, чтобы R имело длину 5 цифр. Минимальное N в троичной системе — \( 100_{3} \). N = \( 100_{3} \) (4 в десятичной).

• N = \( 100_{3} \). Сумма цифр \( S_1 = 1+0+0 = 1 \). \( d_1 = 1 \% 3 = 1 \).
• Число после шага а) = \( 1001_{3} \). Сумма цифр \( S_2 = 1+0+0+1 = 2 \). \( d_2 = 2 \% 3 = 2 \).
• R = \( 10012_{3} \). В десятичной системе: \( 1 3^4 + 0 3^3 + 0 3^2 + 1 3^1 + 2 3^0 = 81 + 0 + 0 + 3 + 2 = 86 \). Это меньше 125.

Проверим N, троичная запись которого имеет длину 4 цифры. Минимальное N в троичной — \( 1000_{3} \). N = \( 1000_{3} \) (27 в десятичной).

• N = \( 1000_{3} \). Сумма цифр \( S_1 = 1+0+0+0 = 1 \). \( d_1 = 1 \% 3 = 1 \).
• Число после шага а) = \( 10001_{3} \). Сумма цифр \( S_2 = 1+0+0+0+1 = 2 \). \( d_2 = 2 \% 3 = 2 \).
• R = \( 100012_{3} \). В десятичной системе: \( 1 3^5 + 0 3^4 + 0 3^3 + 0 3^2 + 1 3^1 + 2 3^0 = 243 + 0 + 0 + 0 + 3 + 2 = 248 \). Это больше 125.

Значит, минимальное N, троичная запись которого имеет 4 цифры, подходит. Это N = \( 1000_{3} \).

Но нам нужно найти минимальное N. Возможно, N с 3 цифрами может дать R > 125, если оно будет другим. Например, если N = \( 111_{3} \) (13 в десятичной):

• N = \( 111_{3} \). Сумма цифр \( S_1 = 1+1+1 = 3 \). \( d_1 = 3 \% 3 = 0 \).
• Число после шага а) = \( 1110_{3} \). Сумма цифр \( S_2 = 1+1+1+0 = 3 \). \( d_2 = 3 \% 3 = 0 \).
• R = \( 11100_{3} \). В десятичной системе: \( 1 3^4 + 1 3^3 + 1 3^2 + 0 3^1 + 0 3^0 = 81 + 27 + 9 + 0 + 0 = 117 \). Это меньше 125.

Пробуем N = \( 112_{3} \) (14 в десятичной):

• N = \( 112_{3} \). Сумма цифр \( S_1 = 1+1+2 = 4 \). \( d_1 = 4 \% 3 = 1 \).
• Число после шага а) = \( 1121_{3} \). Сумма цифр \( S_2 = 1+1+2+1 = 5 \). \( d_2 = 5 \% 3 = 2 \).
• R = \( 11212_{3} \). В десятичной системе: \( 1 3^4 + 1 3^3 + 2 3^2 + 1 3^1 + 2 3^0 = 81 + 27 + 18 + 3 + 2 = 131 \). Это больше 125.

  Мы нашли N = \( 112_{3} \) = 14 (в десятичной), для которого R = \( 11212_{3} \) = 131, что больше 125.

  Так как мы искали минимальное N, и N = 14 даёт результат больше 125, а предыдущие N (например, 13) давали результат меньше 125, то 14 является минимальным N.

  Ответ: 14