ГЛАВА IV. ЗАДАЧА О СЧАСТЛИВЫХ БИЛЕТАХ

Речь идёт, конечно, о счастливых автобусных билетах. Как известно, каждый такой билет однозначно определяется своим шестизначным номером a b c d e f , причём a + b + c = d + e + f. Цель этой главы – вычислить количество счастливых билетов.

Сведение задачи к задаче о числе

Наборов цифр с заданной суммой компонент

Ясно, что задача допускает естественное обобщение: вместо шестизначных номеров можно рассматривать произвольные 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 ?

Задача о числе наборов цифр с заданной

Суммой компонент

Если искомое количество обозначить через s_m^s , то

s_m^s = 0 при s > 9×m и при s < 0,

s_m⁰ = 1, s_m¹ = m, s_m² = ,

s₁ⁱ = 1 (0 £ i £ 9), s₁ⁱ = 0 (i ³ 10),

s_m+1^s = s_m^s + s_m^s–1 + s_m^s–2 + s_m^s–3 + s_m^s–4 + s_m^s–5 + s_m^s–6 + s_m^s–7 + s_m^s–8 + s_m^s–9.

Последняя формула, справедливая при любом m Î N, следует из того, что в любом наборе (a₁ ; a₂ ;… ; a_m+1) с суммой компонент s на первом месте стоит одна из цифр 0 £ a₁ £ 9, а сумма компонент “хвоста” (a₂ ;… ; a_m+1) равна s – a₁ . Таким образом, .

Пусть (m-набор не может иметь сумму компонент, большую 9×m). Ясно, что

g₁(x) = 1×x⁰ + 1×x¹ + … + 1×x⁹ = 1 + x¹ + … + x⁹,

g₂(x) = 1×x⁰ + 2×x¹ + 3×x² + 4×x³ + 5×x⁴ + 6×x⁵ + 7×x⁶ + 8×x⁷ + 9×x⁸ + 10×x⁹ +

+ 9×x¹⁰ + 8×x¹¹ + 7×x¹² + 6×x¹³ + 5×x¹⁴ + 4×x¹⁵ + 3×x¹⁶ + 2×x¹⁷ + 1×x¹⁸.

При вычислении g₂(x) учитывалось, что пары (a; b) с суммой s при 0 £ s £ 9 исчерпываются следующими: (0; s), (1; s–1), … , (s–1; 1), (s; 0) и их количество s + 1, а при 10 £ s £ 18 таковыми будут пары (s–9; 9), (s–10; 8), … , (8; s–10), (9; s–9) и их число |(s–9)–9| + 1 = |s–18| + 1 = 19–s.

Лемма (о связи g_m(x) и g₁(x)). g_m(x) = g₁(x)^m .

Доказательство.Индукция по m. База для m = 1 верна.

Пусть доказано, что g_m(x) = g₁(x)^m для m = 1, … , k Î N. Докажем, что g_k+1(x) = g₁(x)^k+1 . По предположению индукции

g_k(x) = g₁(x)^k = g₀ + g₁×x + … + g_9×k×x^9×k .

Тогда g₁(x)^k+1 = (1 + x + x² + … + x⁹)×(g₀ + g₁×x + … + g_9×k×x^9×k) =

= 1×g₀ + (1×g₁+1×g₀)×x + … + (1×g_9×k–1+1×g_9×k)×x^9×k+8 + 1×g_9×k×x^9×(k+1).

Здесь при xⁱ стоит сумма 1×g_i + 1×g_i–1 + … + 1×g_i–9 в соответствии с формулой умножения многочленов, которая удобнее записывается для рядов в следующем виде: .

По смыслу g_i – это по предположению индукцииколичество k-наборов с суммой компонент i : g_i = s_kⁱ. Как вычислить число s_k+1^j всех (k+1)-на­боров с суммой компонент j ? Ответ даёт рекуррентная формула из начала параграфа:

s_k+1^j = s_k^j + s_k^j–1 + s_k^j–2 + s_k^j–3 + s_k^j–4 + s_k^j–5 + s_k^j–6 + s_k^j–7 + s_k^j–8 + s_k^j–9,

совпадающая с приведённым выше правилом вычисления коэффициентов многочлена g₁^k+1. Значит, s_k+1^j равно j-му коэффициенту многочлена g₁^k+1.

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

Итак, нужно вычислить (1 + x + x² + … + x⁹)^m = =

= (1 – x¹⁰)^m×(1 – x)^–m = =

Здесь использована формула (1 – y)^–k = , а также соглашение = 0 при p < 0, при q < 0, при q > p.

Итак, , т.е. s_mⁱ – коэффициент при xⁱ в полученном разложении. Итак,

s_m^s = .

В частности, s₆²⁷ = =

= =

= 7×29×31×32 – 18×19×21×22 + 9×10×11×12 = 201376 – 158004 + 11880 = 55252.