Решение. Рассмотрим какие числа могут получаться при составлении по условиям.
Рассмотрим двузначные числа.
Первой цифрой не может быть ноль, возьмем цифру 1.
Если первая цифра 1, то второй цифрой могут быть 0, 3, 5, 7. Всего 4 варианта.
Если первая цифра 2, то второй цифрой могут быть 1, 4, 6, 8. Всего 4 варианта.
Если первая цифра 3, то второй цифрой могут быть 0, 2, 5, 7. Всего 4 варианта.
Если первая цифра 4, то второй цифрой могут быть 1, 3, 5, 7. Всего 4 варианта.
Если первая цифра 5, то второй цифрой могут быть 0, 2, 4, 7. Всего 4 варианта.
Если первая цифра 6, то второй цифрой могут быть 1, 3, 5, 8. Всего 4 варианта.
Если первая цифра 7, то второй цифрой могут быть 0, 2, 4, 6. Всего 4 варианта.
Если первая цифра 8, то второй цифрой могут быть 1, 3, 5, 7. Всего 4 варианта.
Если рассматривать трехзначные числа, то между второй и третьей цифрами к приведенным вариантам добавляется вариант с 0: если цифра 0, то второй цифрой могут быть 2, 4, 6, 8. Всего 4 варианта.
Таким образом, в 12-значном 9-ричном числе первую цифру можно выбрать 8 способами (1–8), каждую следующую — 4 способами.
Всего 8 · 411 = 33554432 подходящих 12-значных 9-ричных чисел.
Ответ: 33554432.
Приведём решение на языке Python.
def f(n):
s = str(n)
if len(s) == 12:
return 1
podr = []
for i in range(9):
if (int(s[-1]) + i)%2 == 0 and i > int(s[-1]):
podr.append(int(s+str(i)))
if (int(s[-1]) + i)%2 != 0 and i < int(s[-1]):
podr.append(int(s + str(i)))
return sum(f(i) for i in podr)
print(sum(f(i) for i in range(1,9)))
Приведём решение Егора Чернецова на языке Python.
dp = [int(0 < d < 9) for d in range(9)]
for _ in range(11):
dp = [sum(dp[d] * (n > d if (d+n) % 2 == 0 else n < d) for d in range(9)) for n in range(9)]
print(sum(dp))
Приведём решение Юрия Красильникова на языке Python.
import functools
@functools.lru_cache(1000)
def kp(d,l):
if l==2: return len(dic[d])
return sum(kp(x,l-1) for x in dic[d])
dic={d:[x for x in range(9) if ((d+x)%2==0 and x > d) or ((d+x)%2==1 and x < d)] for d in range(9)}
print(sum(kp(x,12) for x in range(1,9)))
Приведём решение Сергея Донец на PascalABC.NET:
[cache]
function rec(pos, prev: integer): double :=
if ((pos = 13)) then 1.0 else
(0..8)
.Where(curr -> (pos = 1)or( (prev + curr) mod 2 = 0)and(curr > prev)or( (prev + curr) mod 2 = 1)and(curr < prev)and( (pos > 1)or(curr > 0) )
).Sum(curr -> rec((pos + 1), curr));
begin
Println( (1..8).Sum(start -> rec(2, start)) ); // 33554432
end.
PDF-версии: 