Question

Значение арифметического выражения $9^8 + 3^5 - 9$ записали в системе счисления с основанием 3. Сколько цифр 2 содержится в этой записи?

Accepted Answer

3

Answer

Идея решения: вычислить значение выражения, перевести результат в троичную систему и подсчитать количество двоек.

Преобразуем выражение, заметив, что $9 = 3^2$:

$$9^8 + 3^5 - 9 = (3^2)^8 + 3^5 - 3^2 = 3^{16} + 3^5 - 3^2$$

В троичной системе счисления число $3^n$ записывается как единица, за которой следуют $n$ нулей: $3^n = 10\ldots0_3$ ($n$ нулей).

Сначала найдём $3^{16} + 3^5$ в троичной системе. Это число имеет единицы на позициях 16 и 5:

$$3^{16} + 3^5 = 1\underbrace{0\ldots0}_{10}1\underbrace{0\ldots0}_{5}_3$$

Теперь вычтем $3^2 = 100_3$. При вычитании из позиции 5 происходит заём из позиции 16:

$$1\underbrace{0\ldots0}_{10}1\underbrace{0\ldots0}_{5}_3 - 100_3 = 1\underbrace{0\ldots0}_{10}0\underbrace{2\ldots2}_{3}00_3$$

В результате получаем три двойки подряд.

Проверим вычислением на Python:

```python
x = 9**8 + 3**5 - 9
s = ''
while x != 0:
    s += str(x % 3)
    x //= 3
s = s[::-1]
print(s.count('2'))
```

Программа вычисляет остатки при делении на 3, собирает цифры в строку (в обратном порядке), затем разворачивает и подсчитывает количество двоек.

Задание №14Системы счисления и арифметикаЕГЭ по информатике