Задание 14 ЕГЭ: операции с числами в системах счисления

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

Задание 14 проверяет умение работать с позиционными системами счисления: переводить числа из одной системы в другую, выполнять арифметические операции над числами, записанными в разных основаниях, и решать задачи с неизвестными цифрами. Проверяются три навыка одновременно: перевод чисел в десятичную систему по формуле $N_b=\sum a_i b^i$, работа с диапазонами допустимых цифр в разных основаниях и решение линейных сравнений по модулю для поиска неизвестных цифр, удовлетворяющих условию кратности.

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

Типичная формулировка: даны два числа, записанные в системах счисления с разными основаниями, где часть цифр заменена буквами x и y. Нужно найти такие значения x и y (допустимые цифры в соответствующих системах), при которых сумма чисел минимальна и кратна заданному числу m. Затем вычисляется частное от деления суммы на m, и это частное записывается в ответе в десятичной системе. Задание оценивается в 1 балл, ответ — короткая числовая строка без указания основания.

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

• Позиционная запись числа: $N_b=a_{k-1}b^{k-1}+a_{k-2}b^{k-2}+\dots+a_1b^1+a_0b^0$
• Допустимые цифры в системе с основанием $b$: $0 \le a_i \le b-1$
• Перевод из десятичной в систему с основанием $b$: последовательное деление с остатком
• Свойство модульной арифметики: $(A+B)\bmod m = \left((A\bmod m)+(B\bmod m)\right)\bmod m$
• Линейное сравнение: $ax \equiv c \pmod m$ решается через обратный элемент, если $\gcd(a,m)=1$
• Обратный элемент по модулю: $a \cdot a^{-1}\equiv 1 \pmod m$, находится расширенным алгоритмом Евклида
• Правило переноса при сложении столбиком в системе с основанием $b$: если сумма цифр разряда $\ge b$, вычитаем $b$ и переносим 1 в следующий разряд

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

Метод 1. Прямой перевод и сложение чисел без неизвестных. Оба слагаемых переводятся в десятичную систему по формуле $N_b=\sum a_ib^i$, затем складываются как обычные десятичные числа. Пример: $23_5+14_5$. Переводим: $23_5=2\cdot5+3=13$, $14_5=1\cdot5+4=9$. Сумма $13+9=22$.

Метод 2. Параметризация суммы через неизвестные цифры. Каждое число записывается как линейная функция от x и y с коэффициентами — степенями основания. После сложения получаем выражение вида $S=S_0+Px+Qy$. Пример: число $2x_7=2\cdot7+x=14+x$; число $1y_9=1\cdot9+y=9+y$; сумма $S=23+x+y$.

Метод 3. Решение сравнения по модулю m. Из условия кратности $S\equiv 0\pmod m$ получаем сравнение $Px+Qy\equiv -S_0\pmod m$. Для одной переменной при фиксированной другой находим обратный элемент коэффициента и вычисляем недостающую цифру. Пример: $3x\equiv 5\pmod 7$. Обратный к 3 по модулю 7 — это 5 (так как $3\cdot5=15\equiv1$). Тогда $x\equiv5\cdot5=25\equiv4\pmod7$.

Метод 4. Перебор с приоритетом минимизации. Сумма — возрастающая функция от x и y, поэтому минимальное решение ищут, перебирая x от наименьшего допустимого значения; для каждого x решают сравнение относительно y и проверяют, попадает ли y в допустимый диапазон. Первое найденное сочетание даёт минимальную сумму.

Метод 5. Прямое сложение столбиком в одной системе счисления. Если оба числа заданы в одной системе без перевода в десятичную, складывают их «в столбик» по обычным правилам с переносом, когда сумма цифр достигает основания. Пример: сложение в восьмеричной системе $57_8+36_8$: $7+6=13_{10}=15_8$ (пишем 5, перенос 1); $5+3+1=9_{10}=11_8$ (пишем 1, перенос 1); итог $115_8$.

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

1. Определить основания систем счисления обоих чисел и диапазоны допустимых цифр для x и y в каждой системе; взять пересечение диапазонов, если переменная встречается в обоих числах.
2. Записать каждое число как линейную функцию от x и y: $A=A_0+P_1x+Q_1y$, $B=B_0+P_2x+Q_2y$.
3. Сложить выражения и привести к виду $S=S_0+Px+Qy$.
4. Найти остатки $S_0\bmod m$, $P\bmod m$, $Q\bmod m$, где $m$ — заданное число кратности.
5. Составить сравнение $Px+Qy\equiv -S_0 \pmod m$.
6. Перебирать x, начиная с минимального допустимого значения; для каждого x решить сравнение относительно y через обратный элемент по модулю и проверить, что найденное y попадает в допустимый диапазон.
7. Как только найдена первая подходящая пара (минимальный x, минимальный подходящий y), это и есть искомое решение — сумма минимальна.
8. Подставить x и y в выражение для S, вычислить численное значение, разделить на m и записать частное в десятичной системе.

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

Пример 1. Числа $88x4y_9$ и $7x44y_{11}$. Найти x, y, при которых сумма минимальна и кратна 61; в ответе — частное от деления на 61.

Диапазон: в первом числе x, y — цифры системы с основанием 9, значит $0\le x,y\le8$; во втором числе x, y — цифры системы с основанием 11, $0\le x,y\le10$. Так как x и y общие для обоих чисел, берём пересечение: $0\le x,y\le8$.

Переводим числа в десятичную форму: $88x4y_9=8\cdot9^4+8\cdot9^3+x\cdot9^2+4\cdot9+y=52488+5832+81x+36+y=58356+81x+y$

$7x44y_{11}=7\cdot11^4+x\cdot11^3+4\cdot11^2+4\cdot11+y=102487+1331x+528+y=103015+1331x+y$

Сумма: $S=58356+81x+y+103015+1331x+y=161371+1412x+2y$

Остатки по модулю 61: $161371\equiv26$, $1412\equiv9$, $2\equiv2\pmod{61}$.

Сравнение: $9x+2y\equiv35\pmod{61}$ (так как $-26\equiv35$).

Перебираем x от 0: при $x=0,1,2$ получаем y вне диапазона 0–8 (48, 13, 39 соответственно). При $x=3$: $27$, $35-27=8$, $2y\equiv8\Rightarrow y\equiv4\pmod{61}$. Значение $y=4$ подходит.

Итог: $x=3$, $y=4$. Сумма $S=161371+1412\cdot3+2\cdot4=165615$. Частное $165615/61=2715$ — это ответ.

Пример 2. Числа $8x78y_{13}$ и $79xy7_{18}$; сумма минимальна и кратна 9.

Диапазоны: система 13 даёт $0\le x,y\le12$; система 18 даёт $0\le x,y\le17$; пересечение $0\le x,y\le12$.

Переводим: $8x78y_{13}=8\cdot13^4+x\cdot13^3+7\cdot13^2+8\cdot13+y=228488+2197x+1183+104+y=229775+2197x+y$

$79xy7_{18}=7\cdot18^4+9\cdot18^3+x\cdot18^2+y\cdot18+7=734832+52488+324x+18y+7=787327+324x+18y$

Сумма: $S=229775+2197x+y+787327+324x+18y=1017102+2521x+19y$

Остатки по модулю 9: сумма цифр 1017102 равна 12, остаток 3; сумма цифр 2521 равна 10, остаток 1; для 19 остаток 1.

Сравнение: $x+y\equiv6\pmod9$ (так как $-3\equiv6$).

Минимальный $x=0$ требует $y\equiv6\pmod9$, подходит $y=6$ (в диапазоне 0–12). Меньшего x нет, значит решение найдено.

Итог: $x=0$, $y=6$. Сумма $S=1017102+0+19\cdot6=1017216$. Частное $1017216/9=113024$ — ответ.

Пример 3. Числа $90x4y_{15}$ и $91xy2_{16}$; сумма минимальна и кратна 56.

Диапазоны: система 15 даёт $0\le x,y\le14$, система 16 даёт $0\le x,y\le15$; пересечение $0\le x,y\le14$.

Переводим: $90x4y_{15}=9\cdot15^4+0+x\cdot15^2+4\cdot15+y=455625+225x+60+y=455685+225x+y$

$91xy2_{16}=9\cdot16^4+1\cdot16^3+x\cdot16^2+y\cdot16+2=589824+4096+256x+16y+2=593922+256x+16y$

Сумма: $S=455685+225x+y+593922+256x+16y=1049607+481x+17y$

Остатки по модулю 56: $1049607\equiv55\equiv-1$, $481\equiv33$, $17\equiv17$.

Сравнение: $33x+17y\equiv1\pmod{56}$ (так как $-1+\dots\equiv0$ даёт $\dots\equiv1$).

При $x=0$: $17y\equiv1\pmod{56}$. Обратный к 17 по модулю 56 равен 33 (проверка: $17\cdot33=561=560+1$). Получаем $y\equiv33\pmod{56}$ — не входит в диапазон 0–14, решений нет.

При $x=1$: $33+17y\equiv1\Rightarrow17y\equiv24\pmod{56}$. $y\equiv24\cdot33=792\equiv8\pmod{56}$. Значение $y=8$ входит в диапазон.

Итог: $x=1$, $y=8$. Сумма $S=1049607+481\cdot1+17\cdot8=1050224$. Частное $1050224/56=18754$ — ответ.

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

• Забыть, что переменная x (или y), встречающаяся в обоих числах, должна одновременно удовлетворять ограничениям каждой системы счисления — нужно брать пересечение диапазонов, а не диапазон только одной системы.
• Ошибиться в степенях основания при переводе больших чисел — стоит заранее выписать таблицу степеней нужного основания до нужной степени.
• Минимизировать сумму «на глаз», подбирая маленькие x и y без проверки сравнения по модулю — можно получить сумму, не кратную m.
• Неправильно найти обратный элемент по модулю: проверка $a\cdot a^{-1}\equiv1\pmod m$ обязательна.
• Забыть проверить, что найденное значение переменной после решения сравнения попадает в допустимый диапазон цифр — иначе решение ложное и нужно переходить к следующему x.
• Спутать порядок минимизации: минимизировать нужно ту переменную, у которой больше коэффициент в выражении суммы, поскольку она сильнее влияет на итоговое значение.
• Забыть перевести итоговое частное в десятичную систему счисления, оставив его в системе одного из оснований.
• Арифметические ошибки при вычислении больших сумм — полезно проверять результат через контроль остатка по модулю m в самом конце.

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

Начинать нужно с уверенного перевода чисел между системами счисления любых оснований — тренировать это до автоматизма, включая перевод через промежуточную десятичную систему. Далее стоит освоить модульную арифметику: вычисление остатков от деления больших чисел, нахождение обратного элемента по модулю через расширенный алгоритм Евклида или простым перебором для небольших модулей. Полезно решить десяток однотипных задач с параметризацией через x и y, каждый раз явно выписывая диапазоны цифр и составляя линейное сравнение — это вырабатывает устойчивый алгоритм действий. После получения ответа стоит всегда делать проверку: подставить найденные x и y в исходное выражение, убедиться, что сумма действительно делится на заданное число без остатка, и только потом делить и записывать частное. Такой порядок работы исключает большинство ошибок и позволяет решать задание быстро и без пересчётов.