Информатика. ЕГЭ. Задание 16. Информатика. ЕГЭ. Поляков-7250

Информатика. ЕГЭ

Задание 16. Информатика. ЕГЭ. Поляков-7250

Просмотры: 503

Изменено: 1 февраля 2025

*Обозначим через $a % b$ остаток от деления натурального числа $a$ на натуральное число $b$ , а через $a / / b$ – целую часть от деления $a$ на $b$ . Алгоритм вычисления значения функции $F (n)$ , где $n$ – натуральное число, задан следующими соотношениями:

$F (n) = 1$ , если $n = 0$ ,
$F (n) = F (n / / 8) \cdot (n % 8)$ , если $n > 0$ и n нечётно;
$F (n) = F (n / / 8)$ , если $n > 0$ и $n$ чётно.

Определите количество значений $n$ , таких что $8^{9} ⩽ n ⩽ 8^{10}$ , для которых $F (n) = 25$ .

Решение:

Будем рассматривать числа в $8$ -ричной системе счисления. Тогда $8^{9} = 1 000 000 000_{8}$ , $8^{10} = 10 000 000 000_{8}$ . Т.е., все наши числа $10$ -значные в этой системе счисления (за исключением правой границы $8^{10}$ ; но это число не даст в ответе $25$ , поэтому его мы не будем рассматривать). Чтобы получилось $25$ , необходимо, чтобы в записи числа присутствовали две $5$ , а остальные цифры — это $0$ , $1$ , $2$ , $4$ , $6$ (всего их $5$ , назовём такие числа допустимыми). Учтём также, что на первой позиции не может стоять $0$ , зато может быть $5$ . Рассмотрим отдельно два случая. Первый — на первой позиции стоит одно из четырёх чисел $1$ , $2$ , $4$ , $6$ . На оставшихся размещаются две $5$ и допустимые числа (вакантных позиций $7$ ). Разместить две пятёрки по девяти позициям можно $C_{9}^{2} = 36$ способами. Т.о., получаем $4 \cdot 36 \cdot 5^{7}$ вариантов. Второй случай. На первой позиции стоит $5$ . Тогда на оставшихся девяти находится одна $5$ и допустимые цифры. Всего $9 \cdot 5^{8}$ вариантов. Итого $4 \cdot 36 \cdot 5^{7} + 9 \cdot 5^{8}$ вариантов.

Ответ: $14765625$