Задание EGEINF042DDB: Подсчёт слов и последовательностей

Основание системы b = 10, длина n = 5. Разрешённые чётные цифры: 0, 2, 4, 6, 8; нечётные: 1, 3, 5, 7, 9. Первая цифра не может быть нулём, иначе число имеет меньшую длину.

Соседние цифры обязаны иметь разную чётность. Значит, после выбора чётности первой цифры весь порядок чётностей однозначен. Обозначим чётную позицию Ч, нечётную Н. Цифры не повторяются; из разных классов одна и та же цифра появиться не может, поэтому отдельно распределяем чётные и нечётные цифры.

Обозначим A(m, k) число упорядоченных выборов k различных элементов из m: A(m, k) = m · (m − 1) · … · (m − k + 1), а A(m, 0) = 1. Первый множитель в каждом случае — число допустимых первых цифр. Затем исключаем уже занятые цифры из соответствующих классов и заполняем оставшиеся позиции.

Десятичное число делится на 5 ровно тогда, когда последняя цифра равна 0 либо 5. Эти два случая не пересекаются. Фиксируем последний знак и исключаем его из выбора первой цифры и остальных цифр того же класса. Чётность последней цифры должна соответствовать чередующемуся шаблону.

Шаблон ЧНЧНЧ, последняя цифра 0. Первую цифру выбираем из 2, 4, 6, 8. После фиксации крайних цифр остаётся выбрать 1 чётных из 3 и 2 нечётных из 5.
Число способов = 4 · A(3, 1) · A(5, 2) = 4 · 3 · 20 = 240.

Шаблон НЧНЧН, последняя цифра 5. Первую цифру выбираем из 1, 3, 7, 9. После фиксации крайних цифр остаётся выбрать 2 чётных из 5 и 1 нечётных из 3.
Число способов = 4 · A(5, 2) · A(3, 1) = 4 · 20 · 3 = 240.

Всего = 240 + 240 = 480.

Проверка: перебираем все упорядоченные наборы различных разрешённых цифр нужной длины, убираем ведущий ноль и проверяем каждую соседнюю пару и последнюю цифру 0 или 5. Получается 480. Разбиение по первому классу и последней цифре исчерпывает все возможности, поэтому ни один подходящий набор не потерян и не посчитан дважды.

Ответ: 480.