Задание 5 ЕГЭ: посимвольные преобразования чисел в n-ичных системах

Что проверяет задание

Задание 5 проверяет умение анализировать алгоритм, заданный словесно, который берёт натуральное число $N$, переводит его в некоторую систему счисления (обычно двоичную или троичную, иногда работает прямо с десятичными цифрами), выполняет над цифрами простое преобразование и получает новое число $R$. Нужно либо промоделировать алгоритм для конкретного $N$, либо, наоборот, восстановить $N$ по известному $R$ и дополнительным условиям (минимальное/максимальное значение, ограничение на диапазон). Проверяется не программирование, а точное понимание позиционной записи числа и умение выразить шаги алгоритма формулами.

Как выглядит формулировка и сколько баллов

Типичная формулировка: «Алгоритм получает на вход натуральное число $N$ и строит по нему новое число $R$: 1) переводит $N$ в систему с основанием $n$; 2) выполняет посимвольное преобразование цифр (замена, дополнение, дописывание); 3) переводит результат обратно в десятичную систему; 4) иногда добавляется финальный шаг — разность, сумма или сравнение с исходным числом». Дальше задаётся вопрос: найдите наибольшее/наименьшее $N$ или $R$, удовлетворяющее условию (например, не превышающее данное число, или дающее конкретный результат).

Задание относится к части с кратким ответом, оценивается в 1 первичный балл, ответ — целое число, вводится без пояснений, поэтому единственная ошибка в вычислении полностью обесценивает решение.

Что нужно знать

• Позиционная запись числа в системе с основанием $n$: $N = \sum_{i=0}^{k-1} a_i n^i$, где $a_i \in \{0,1,\dots,n-1\}$, $a_{k-1}\neq 0$.
• Число цифр $k$ представления $N$ в основании $n$ определяется условием $n^{k-1} \le N \le n^k-1$.
• Перевод из десятичной системы в систему с основанием $n$ — последовательное деление на $n$ с выписыванием остатков от последнего к первому.
• Дополнение цифры в системе с основанием $n$: замена $a_i$ на $(n-1)-a_i$. Для троичной системы это замена $0\leftrightarrow 2$, единица остаётся на месте.
• Если у числа с $k$ цифрами в основании $n$ заменить каждую цифру $a_i$ на $(n-1)-a_i$, то новое число (посчитанное с той же длиной $k$, даже если появляются ведущие нули) равно $M = (n^{k}-1) - N$. Удаление ведущих нулей не меняет численного значения $M$, меняется только запись.
• Дописывание к записи числа $N$ (длина $k$ цифр) блока из $m$ цифр со значением $v$ равносильно операции $R = N\cdot n^{m} + v$.
• Для двоичного случая ($n=2$) дополнение цифры — это инверсия бита: $a_i \to 1-a_i$, а формула дополнения принимает вид $M = (2^k - 1) - N$, что совпадает с побитовым «НЕ» числа $N$ в пределах $k$ разрядов.
• Для задач, где преобразование идёт по десятичным цифрам «окнами» (например, тройки соседних цифр), нужно помнить: для числа из $d$ цифр при окне длины $m$ получается $d-m+1$ окон.

Методы решения

1. Формульный метод через основание и длину числа. Вместо ручного перевода каждого конкретного числа выражаем результат алгоритма как формулу от $N$ и числа цифр $k$. Это ключевой приём для задач «замена цифр по правилу дополнения», где $R=|2N-(n^k-1)|$.

2. Метод перебора по остатку/разряду. Когда правило преобразования зависит от остатка от деления $N$ на небольшое число (например, «если кратно 3», «если не кратно»), удобно разбить задачу на случаи по значению остатка и в каждом случае вывести отдельную формулу для $R$, а затем сравнить максимумы.

Мини-пример: если по правилу для чётных $N$ дописывается цифра 0, а для нечётных — цифра 1, то $R=2N$ либо $R=2N+1$ соответственно — из двух формул выбираем нужный случай по чётности.

3. Метод скользящего окна по цифрам. Для задач, где рассматриваются подряд идущие группы цифр десятичной записи (например, тройки), удобно обозначить цифры как $d_1d_2\dots d_k$ и выразить каждое окно как трёхзначное число: $100d_i+10d_{i+1}+d_{i+2}$. Разность между окнами превращается в линейное уравнение относительно цифр.

4. Метод обратного построения (от $R$ к $N$). Составляем уравнение $R = f(N,k)$ и решаем его в целых цифрах с учётом ограничений $0\le a_i\le n-1$, а также условия, что число реально имеет длину $k$ (то есть старшая цифра не равна нулю, либо явное неравенство $n^{k-1}\le N\le n^k-1$). Перебираем $k$ от меньших значений к большим, ищем допустимое решение.

5. Битовый метод для двоичных преобразований. Если преобразование — инверсия каждого бита в записи длиной $k$, результат до сложения с исходным числом равен $2^k-1-N$; если алгоритм затем складывает или вычитает результат с $N$, сумма всегда равна $2^k-1$, а разность равна $|2N-(2^k-1)|$ — та же логика, что в троичном случае, но с основанием 2.

Алгоритм решения по шагам

1. Определить основание системы $n$, в которой строится запись числа (двоичная, троичная, десятичная «по цифрам»).
2. Расписать шаг преобразования как операцию над отдельной цифрой или как операцию над группой цифр (окно, дописывание, дополнение).
3. Найти длину $k$ представления $N$ в этой системе как функцию от диапазона значений $N$ (через неравенство $n^{k-1}\le N\le n^k-1$).
4. Вывести формулу $R(N,k)$, отражающую весь алгоритм целиком (включая финальные операции — разность, сумму, сравнение).
5. Если требуется найти $N$ по известному $R$ — составить уравнение $R=f(N,k)$, решить относительно $N$ при разных $k$, начиная с наименьших, и на каждом шаге проверять, что найденное $N$ действительно попадает в диапазон, соответствующий выбранному $k$.
6. Если требуется найти максимум/минимум $R$ (или $N$) при ограничении — рассмотреть все случаи алгоритма, вывести формулу для каждого случая, найти границы допустимых $N$ внутри случая и выбрать оптимальное значение.
7. Перевести финальный результат в десятичную систему, если ответ требуется именно в ней, и сверить его подстановкой в исходное словесное описание алгоритма.

Разбор примеров

Пример 1

Условие: строим троичную запись $N$; если $N$ кратно 3 — дописываем к записи её последние две троичные цифры; если не кратно — остаток от деления умножаем на 5, переводим в троичную систему и дописываем. Нужно найти максимальное $R\le173$.

Случай $N$ кратно 3. Последняя троичная цифра такого числа всегда равна 0, а предпоследняя — произвольная цифра $0,1,2$. Дописывание двух последних цифр равносильно операции $R=9N+v$, где $v\in\{0,3,6\}$ в зависимости от $N \bmod 9$: $v=0$ при $N\equiv0\ (9)$, $v=3$ при $N\equiv3\ (9)$, $v=6$ при $N\equiv6\ (9)$.

Максимизируем $R\le173$ по подслучаям: при $v=6$ ($N\equiv6$) наибольшее $N=15$, $R=141$; при $v=3$ ($N\equiv3$) наибольшее $N=12$, $R=111$; при $v=0$ ($N\equiv0$) наибольшее $N=18$ (так как $9\cdot18=162\le173$, а $9\cdot27=243>173$), тогда $R=162$.

Случай $N$ не кратно 3. Остаток $r=1$: $5_{10}=12_3$ — 2 цифры, $R=9N+5$, нужно $N\equiv1\ (3)$, максимум даёт $N=16$, $R=149$. Остаток $r=2$: $10_{10}=101_3$ — 3 цифры, $R=27N+10$, нужно $N\equiv2\ (3)$, максимум даёт $N=5$, $R=145$.

Сравнивая значения $141,111,162,149,145$, наибольшее — $R=162$, что и является ответом.

Пример 2

Условие: в десятичной записи $N$ рассматриваются все тройки соседних цифр как трёхзначные числа, среди них ищутся максимум и минимум, результат — их разность. Найти наименьшее $N\ge100$, дающее $R=415$.

Для минимизации $N$ выгодно взять наименьшее возможное количество цифр. При трёх цифрах есть только одно окно, разность равна 0 — не подходит. Берём четыре цифры $N=\overline{abcd}$, тогда есть два окна: $\overline{abc}$ и $\overline{bcd}$, разность между ними $\overline{abc}-\overline{bcd}=100a-90b-9c-d$.

Рассматриваем оба знака. Если $\overline{abc}$ больше: $100a-90b-9c-d=415$; при малых $a$ левая часть не достигает 415, первое подходящее значение $a=5$ даёт $N=5094$.

Если $\overline{bcd}$ больше: $90b+9c+d=415+100a$. При $a=1$ нужно $90b+9c+d=515$; так как $9c+d\le90$, требуется $b\ge5$; при $b=5$ получаем $9c+d=65$, единственное решение $c=7,\,d=2$. Число $N=1572$.

Так как $1572<5094$, а бо́льшие $a$ во втором случае дают ещё бо́льшие числа, минимальным решением среди четырёхзначных чисел оказывается $N=1572$; пятизначные числа заведомо больше. Ответ: $N=1572$.

Пример 3

Условие: строится троичная запись $N$, цифры $0$ и $2$ меняются местами, ведущие нули убираются, результат переводится в десятичную систему, итог — модуль разности $N$ и полученного числа. Найти наименьшее $N$, дающее $R=1\,864\,246$.

Пусть $k$ — количество троичных цифр числа $N$, то есть $3^{k-1}\le N\le 3^k-1$. Замена $0\leftrightarrow2$ во всех $k$ цифрах равносильна формуле дополнения $M=(3^k-1)-N$ — удаление ведущих нулей не меняет численного значения $M$. Тогда $R=|N-M|=|2N-(3^k-1)|$.

Проверка на примере из условия: $N=35=1022_3$, $k=4$, $3^4-1=80$, $|2\cdot35-80|=10$ — совпадает.

Решаем $|2N-(3^k-1)|=1\,864\,246$, перебирая $k$ от малых значений. При $k\le13$ ($3^{13}-1=1\,594\,322$) решений, удовлетворяющих диапазону длины, нет. При $k=14$ ($3^{14}-1=4\,782\,968$): $N=\dfrac{4\,782\,968+1\,864\,246}{2}=3\,323\,607$, что лежит в диапазоне $[3^{13},\,3^{14}-1]$ — подходит. Второй вариант при $k=14$ даёт $1\,459\,361 < 3^{13}$, то есть относится к другой длине и не подходит. При $k\ge15$ значения только возрастают. Минимальное подходящее число — $N=3\,323\,607$.

Типичные ошибки и ловушки

• Путают удаление ведущих нулей с изменением численного значения — на самом деле оно не меняется, меняется только длина записи.
• Забывают проверить, что найденное решение $N$ действительно имеет ту длину $k$, которая использовалась при выводе формулы; без этой проверки можно получить «лишний» корень, не удовлетворяющий условию.
• В задачах с остатком от деления путают, какая операция применяется к остатку, а какая — к самому числу.
• В задачах со скользящим окном забывают, что число окон равно (число цифр − длина окна + 1), и упускают одно из окон на краю записи.
• Рассматривают только один знак модуля или только один порядок операндов в разности, теряя часть решений.
• Допускают арифметические ошибки при переводе чисел в другую систему счисления вручную — стоит проверять перевод контрольной подстановкой обратно по формуле $\sum a_i n^i$.
• При поиске минимального/максимального значения перебирают варианты не по возрастанию длины числа, из-за чего пропускают более выгодный ответ, лежащий при другой длине.

Как готовиться

• Довести до автоматизма перевод чисел между десятичной и системами с основаниями 2, 3, 8, 16 — как в прямом, так и в обратном направлении, без калькулятора.
• Для каждой новой задачи сначала записывать общую формулу $R(N,k)$ через основание системы и длину числа, а не сразу подбирать конкретные числа — это резко снижает число ошибок.
• Отдельно тренировать формулу дополнения $M=(n^k-1)-N$ и её частные случаи для $n=2$ и $n=3$, так как она встречается в большинстве вариантов на эту подтему.
• Прорешать подряд несколько задач банка заданий с разными правилами «дописывания» цифр, чтобы наработать навык быстрого перехода от словесного описания к формуле.
• После получения ответа обязательно подставлять найденное число в исходный алгоритм «вручную» и проверять, что результат совпадает с условием — это главный способ отловить ошибку в диапазоне длины $k$.
• Заучить степени 2 и 3 хотя бы до пятнадцатого-двадцатого порядка — это экономит время на экзамене при переборе значений $k$.