Задание №8 — Комбинаторика
#69746Задание №8ФИПИ
Количество информации
Сколько существует различных трехзначных чисел, записанных в четверичной системе счисления, в записи которых цифры следуют слева направо в невозрастающем порядке?
Правильный ответ
19
Пояснение
Решение:
В четверичной системе счисления цифры 0, 1, 2, 3. Невозрастающая запись однозначно восстанавливается по набору цифр (с повторами), поэтому число записей равно числу сочетаний с повторениями из 4 цифр по 3:
Из этих 20 наборов один — 000 — начинается с нуля и трёхзначного числа не даёт. Все остальные годятся, ведь при невозрастающем порядке старшая цифра наибольшая, и она равна нулю только у набора 000.
Итого .
from itertools import product
print(sum(1 for d in product(range(4), repeat=3)
if d[0] != 0 and d[0] >= d[1] >= d[2]))
Ответ: 19