Назовём ряд из двух цифр подходящим, если выполняется любое из двух условий: 1)  сумма цифр чётна и вторая цифра больше первой; 2)  сумма цифр нечётна и вторая цифра меньше первой. Назовём многозначное число подходящим, если любые две соседние цифры в его записи образуют подходящий ряд. Примеры подходящих чисел: 26, 63, 30, 2630, 26308. Пример неподходящего числа: 2638. Это число нельзя считать подходящим, так как соседние цифры 3 и 8 в его записи образуют неподходящий ряд. Сколько существует подходящих 11-⁠значных 9-⁠ричных чисел?

Кратко сформулируем задачу и решение. 1) Что значит "подходящий ряд" из двух цифр (a, b): - если a + b четно, то нужно b > a; - если a + b нечетно, то нужно b < a. 2) Многозначное число считается подходящим, если каждая соседняя пара цифр удовлетворяет вышеуказанному правилу. 3) В9-ричной системе цифры — от 0 до 8. При этом 11-значное число не может начинаться с нуля, поэтому для первой цифры есть 8 вариантов (1–8). 4) Пусть 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. 5) Подсчёт числа подходящих 11-значных чисел: - первая цифра d1 может быть любая из 1–8: 8 вариантов; - для каждого последующего места есть ровно 4 выбора (независимо от предыдущих цифр). Итого количество таких чисел равно 8 · 4^{10}. 6) Вычисление: - 4^{10} = 1 048 576 - 8 · 4^{10} = 8 · 1 048 576 = 8 388 608 Ответ: 8 388 608.