Решения заданий ФИПИ ЕГЭ по информатике: «Системы счисления» — с ответами

Рассмотрим все допустимые значения $x$ от 1 до 2030. Для каждого значения вычислим $N = 5^{150} + 5^{100} - x$ и подсчитаем количество нулей в его записи по основанию 5.$$N = 5^{150} + 5^{100} - x$$

Количество нулей в пятеричной записи можно найти последовательным делением числа на 5: каждая нулевая цифра соответствует нулевому остатку на очередном шаге.

Выразим основания степеней через число $3$: $2187=3^7$, $729=3^6$, $243=3^5$, $81=3^4$, $27=3^3$, $6561=3^8$.

Получаем выражение $N=2\cdot3^{14140}+3^{12126}-2\cdot3^{10110}+3^{8092}-2\cdot3^{6072}-3^8$.

Представим $16$ как степень основания системы счисления:$$16^8 = (4^2)^8 = 4^{16}$$

Преобразуем исходное выражение:$$16^8 \times 4^{20} - 4^{10} - 4 = 4^{36} - 4^{10} - 4$$

Так как $x\leq 2030<7^4=2401$, представим результат с учётом заимствования при вычитании $x$ из разряда $7^{100}$. Количество нулей в старших разрядах не зависит от $x$; дополнительные нули определяются четырёхразрядной записью числа…

Диапазон для числа $y=2401-x$: $371\leq y\leq 2400$. Чтобы в четырёхразрядной записи $y$ было максимально возможное число нулей, выбираем число, состоящее из одной ненулевой цифры и трёх нулей: $y=a\cdot 7^k$.

Поскольку $15 \equiv 1 \pmod{14}$, значение числа в 15-ричной системе сравнимо по модулю 14 с суммой его цифр.

Сумма цифр арифметического выражения равна $9+7+9+6+8+x+7+x+2+3+3=54+2x$.

Последняя цифра записи числа в системе счисления с основанием $p$ равна остатку от деления числа на $p$.$$22 \bmod p = 4$$

Следовательно, основание должно делить разность между числом и его последней цифрой.$$p \mid (22 - 4) = 18$$

Поскольку $15 \equiv 1 \pmod{14}$, каждая степень основания 15 сравнима с единицей по модулю 14. Поэтому остаток числа равен сумме его цифр.$$99658x29_{15}+102x023_{15} \equiv (48+x)+(8+x)=56+2x \pmod{14}$$

Для кратности выражения 14 необходимо, чтобы $56+2x$ делилось на 14. Следовательно, $2x$ делится на 14, то есть $x$ кратно 7. Допустимые значения: $0$, $7$, $14$; наибольшее значение — $x=14$.

Представим слагаемые как степени основания системы счисления:$$125 = 5^3,\quad 25^3 = (5^2)^3 = 5^6$$

Тогда выражение имеет вид:$$5^3 + 5^6 + 5^9$$

Выразим слагаемые через степени основания $64$: $512 = 8 \cdot 64$, поэтому $6 \cdot 512^{395} = 48 \cdot 64^{592}$; далее $3 \cdot 8^{398} = 3 \cdot 64^{199}$ и $5 \cdot 8^{393} = 40 \cdot 64^{196}$.

Разложим последнее слагаемое: $300 = 4 \cdot 64 + 44$. Все коэффициенты являются допустимыми цифрами системы счисления с основанием $64$, поэтому переносов нет.$$N = 48 \cdot 64^{592} + 7 \cdot 64^{396} + 3 \cdot 64^{199} + 40 \cdot 64^{196} + 4 \cdot 64^1 + 44$$

Заменим основания степеней на степени числа $7$:$$343^{515}=(7^3)^{515}=7^{1545},\quad 49^{520}=(7^2)^{520}=7^{1040},\quad 49^{510}=(7^2)^{510}=7^{1020}$$

Исходное выражение преобразуется к виду:$$N=7^{1545}-6\cdot 7^{1040}+5\cdot 7^{1020}-3\cdot 7^{530}-550$$

При вводе 231 начальное значение minDigit равно последней цифре числа: 1. Затем программа рассматривает цифры 1, 3 и 2. Только цифра 2 является чётной, поэтому minDigit становится равным 2.$$231 \to 1,\ 3,\ 2$$

После завершения цикла значение minDigit равно 2, поэтому программа выводит число 2.$$2$$

В начале работы программы $k = 0$, поэтому условие цикла `k % 4 == 0` истинно. После первой итерации $k$ становится равным 1, а $n$ при входном значении 16 становится равным 4.$$16 // 4 = 4$$

После первой итерации условие `k % 4 == 0` становится ложным, поскольку $1 \bmod 4 = 1$. Цикл завершается.

Проверим значения $N$, начиная с небольших чисел, учитывая остаток при делении на 3. Для $N=16$: $16=121_3$, остаток при делении на 3 равен $1$.

Остаток $1$ умножается на $5$, поэтому к записи $121_3$ дописывается троичная запись числа $5$: $5=12_3$.

Если двоичная запись числа $N$ содержит пять разрядов, результат также содержит пять разрядов. При нечётной сумме цифр первые два разряда результата равны $11$, поэтому $R\geq11000_2=48$, что не подходит.$$R\geq 48$$

Значит, сумма цифр исходной пятиразрядной записи должна быть чётной, а первые два разряда результата равны $10$. Тогда $R<40$ означает, что оставшиеся разряды результата дают число не более $0011_2$.$$R=10abc0_2<101000_2$$

Проверим значения $N$, делящиеся на 3. При $N=15$ его двоичная запись имеет вид $1111_2$.

Так как $15$ делится на 3, к записи приписываются три последние двоичные цифры: $111$. Получаем запись $1111111_2$.

Проверим числа, имеющие не более шести цифр в двоичной записи. Для чётного числа с $k$ цифрами результат имеет вид $10b_1b_2\ldots b_k$, поэтому $R=2^{k+1}+N$. Для нечётного числа результат имеет вид $1b_1b_2\ldots b_k01$, поэтому…

Наибольшее нечётное число с шестью двоичными цифрами — $63$. Для него $R=2^8+4\cdot63+1=509$, то есть условие ещё не выполняется.

Обозначим через $E_i$ количество чётных цифр в $i$-й строке. При создании новой строки предыдущая строка записывается дважды, поэтому её вклад удваивается.

Приписанная цифра увеличивает количество чётных цифр на единицу только для чётных номеров строк.

Проверим числа, близкие к $113$, в двоичной системе счисления. Для результата, полученного из нечётного $N$, двоичная запись должна иметь вид $1b00$.

Число $108$ представляется в виде $1101100_2$. Отделяем первую единицу и два последних нуля: получаем $b=1011_2=11_{10}$.

Последовательно проверим натуральные числа, начиная с $N=1$. Для каждого числа применяем правило преобразования.

Для первых значений получаются результаты: $R(1)=3$, $R(2)=4$, $R(3)=4$, $R(4)=13$, $R(5)=8$, $R(6)=8$, $R(7)=15$.

Проверяем значения $N$ по возрастанию, пока результат не станет больше 40.

Для $N=15$: $15_{10}=1111_2$. Сумма цифр равна 4, поэтому справа дописывается 0, а первые два разряда заменяются на 10: $1111_2\rightarrow10110_2=22_{10}$.