§ 1. Сведение задачи к задаче о числе наборов цифр с заданной суммой компонент

Ясно, что задача допускает естественное обобщение: вместо шестизначных номеров можно рассматривать произвольные 2n-значные наборы вида (a₁ ; … ; a_n ; b₁ ; … ; b_n), где a₁ + … + a_n = b₁ + … + b_n .

Лемма. Существует взаимно однозначное соответствие между всеми счастливыми 2n-наборами и всеми 2n-наборами с суммой цифр 9n .

Доказательство. Пусть D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} – множество всех десятичных цифр,

H_n = {(a₁ ; … ; a_n ; b₁ ; … ; b_n)  D^2n | a₁ + … + a_n = b₁ + … + b_n }

– множество всех счастливых 2n-наборов, и

∑ _9n = {(a₁ ; … ; a_n ; b₁ ; … ; b_n)  D^2n | a₁ + … + a_n + b₁ + … + b_n = 9n }

множество всех 2n-наборов с суммой цифр 9n.

Рассмотрим отображение 2n-наборов, заданное следующим правилом:

f(a₁ ; … ; a_n ; b₁ ; … ; b_n) = (a₁ ; … ; a_n ; 9 – b₁ ; … ; 9 – b_n).

Таким образом, каждому 2n-набору отображение f ставит в соответствие однозначно определённый 2n-набор.

При этом отображение f инъективно, т.е. переводит разные наборы в разные: если

f(a₁ ; … ; a_n ; b₁ ; … ; b_n) = f(с₁ ; … ; с_n ; d₁ ; … ; d_n),

то (a₁ ; … ; a_n ; 9 – b₁ ; … ; 9 – b_n) = (c₁ ; … ; c_n ; 9 – d₁ ; … ; 9 – d_n), а значит, (a₁ ; … ; a_n ; b₁ ; … ; b_n) = (с₁ ; … ; с_n ; d₁ ; … ; d_n).

Отображение f сюръективно: если (с₁ ; … ; с_n ; d₁ ; … ; d_n) – любой 2n-набор, то f(с₁ ; … ; с_n ; 9 – d₁ ; … ; 9 – d_n) = (с₁ ; … ; с_n ; d₁ ; … ; d_n).

Таким образом, f – биективное отображение.

Кроме того, если применить f к счастливому набору, для которого выполняется a₁ + … + a_n = b₁ + … + b_n , то получается набор с суммой цифр a₁ + … + a_n + (9 – b₁) + … + (9 – b_n) = 9n. Значит, f биективно отображает множество H_n в ∑ _9n : f : H_n  ∑ _9n .

Лемма доказана.

Эта лемма показывает, что количество счастливых 2n-наборов равно количеству 2n-наборов с суммой цифр 9n. Можно теперь поставить более общую задачу: сколько m-наборов имеют сумму цифр s ?