Решение. Рассмотрим какие числа могут получаться при составлении по условиям.
Рассмотрим двузначные числа.
Первой цифрой не может быть ноль, возьмем цифру 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 варианта.
Таким образом, в 11-значном 9-ричном числе первую цифру можно выбрать 8 способами (1–8), каждую следующую 4 способами.
Всего 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.
PDF-версии: 