Задание 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)(n%8), если n>0 и n нечётно;
F(n)=F(n//8), если n>0 и n чётно.

Определите количество значений n, таких что 89n810, для которых F(n)=25.

Решение:

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

Ответ: 14765625