Назовём ряд из двух цифр подходящим, если выполняется любое из двух условий: 1) сумма цифр чётна и вторая цифра больше первой; 2) сумма цифр нечётна и вторая цифра меньше первой.…
Назовём ряд из двух цифр подходящим, если выполняется любое из двух условий: 1) сумма цифр чётна и вторая цифра больше первой; 2) сумма цифр нечётна и вторая цифра меньше первой. Назовём многозначное число подходящим, если любые две соседние цифры в его записи образуют подходящий ряд. Примеры подходящих чисел: 26, 63, 30, 2630, 26308. Пример неподходящего числа: 2638. Это число нельзя считать подходящим, так как соседние цифры 3 и 8 в его записи образуют неподходящий ряд. Сколько существует подходящих 11-значных 9-ричных чисел?
Кратко сформулируем задачу и решение.
- Что значит "подходящий ряд" из двух цифр (a, b):
- если a + b четно, то нужно b > a;
- если a + b нечетно, то нужно b < a.
Многозначное число считается подходящим, если каждая соседняя пара цифр удовлетворяет вышеуказанному правилу.
В9-ричной системе цифры — от 0 до 8. При этом 11-значное число не может начинаться с нуля, поэтому для первой цифры есть 8 вариантов (1–8).
Пусть d1, d2, …, d11 — цифры числа. Для любой последующей цифры d_{i+1} единственный источник ограничений — предыдущая цифра d_i. Для каждого a в {0,…,8} найдутся ровно 4 допустимые следующих цифры b. Ниже приведены множества допустимых переходов S(a):
- S(0) = {2, 4, 6, 8}
- S(1) = {3, 5, 7, 0}
- S(2) = {4, 6, 8, 1}
- S(3) = {5, 7, 0, 2}
- S(4) = {6, 8, 1, 3}
- S(5) = {7, 0, 2, 4}
- S(6) = {8, 1, 3, 5}
- S(7) = {0, 2, 4, 6}
- S(8) = {1, 3, 5, 7}
Из этого видно: для каждого a из 0…8 существует ровно 4 допустимых варианта следующей цифры b.
- Подсчёт числа подходящих 11-значных чисел:
- первая цифра d1 может быть любая из 1–8: 8 вариантов;
- для каждого последующего места есть ровно 4 выбора (независимо от предыдущих цифр).
Итого количество таких чисел равно 8 · 4^{10}.
- Вычисление:
- 4^{10} = 1 048 576
- 8 · 4^{10} = 8 · 1 048 576 = 8 388 608
Ответ: 8 388 608.
