Назовём ряд из двух цифр подходящим, если выполняется любое из двух условий:
1) сумма цифр чётна и вторая цифра больше первой;
2) сумма цифр нечётна и вторая цифра меньше первой.
Назовём многозначное число подходящим, если любые две соседние цифры в его записи образуют подходящий ряд.
Примеры подходящих чисел: 26, 63, 30, 2630, 26308.
Пример неподходящего числа: 2638. Это число нельзя считать подходящим, так как соседние
Сколько существует подходящих 11-значных 9-ричных чисел?
Рассмотрим какие числа могут получаться при составлении по условиям.
Рассмотрим двузначные числа.
Первой цифрой не может быть ноль, возьмем
Если первая
Если первая
Если первая
Если первая
Если первая
Если первая
Если первая
Если первая
Если рассматривать трехзначные числа, то между второй и третьей цифрами к приведенным вариантам добавляется вариант
Таким образом, в 11-значном 9-ричном числе первую цифру можно выбрать
Всего 8 · 410 = 8388608 подходящих 11-значных 9-ричных чисел.
Ответ: 8388608.
Приведём решение на языке Python.
def f(n):
s = str(n)
if len(s) == 11:
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.
def f(d,n):
if n==11:
return 1
d1=[x for x in range(9) if ((d+x)%2 == 0 and x > d) or ((d+x)%2==1 and x < d)]
return sum([f(x,n+1) for x in d1])
print(sum([f(x,1) for x in range(1,9)]))
Приведём решение Сергея Донец на PascalABC.NET:
var Base := 9; // 9-ричных
var Length := 11; // 11-значных
[cache] // Кэшируем результаты
function GetValidNext(prev: integer): sequence of integer;
begin
Result := (0..Base-1)
.Where(x -> (((prev + x) mod 2 = 0) and (x > prev)) or (((prev + x) mod 2 <> 0) and (x < prev)))
.ToArray;
end;
begin
var memo := (0..Length-1).Select(i -> (0..Base-1).Select(p -> 0).ToList).ToList;
memo[0] := (0..Base-1).Select(p -> 1).ToList;
for var rem := 1 to Length-1 do
for var p := 0 to Base-1 do
memo[rem][p] := GetValidNext(p).Sum(x -> memo[rem-1][x]);
Writeln( (1..Base-1).Sum(x -> memo[Length-1][x]) ); // 8388608
end.