Снова о счастливых билетах

42

Снова о счастливых билетах

«Квант» уже на раз писал о счастливых билетах (1975, № 7, 1976, № 12, 1978, № 11, 1988, № 1 и № 4), т. е. билетах, сумма первых трех цфр которых равна сумме трех последних цфр. Число счастливых билетов $N$ выражается с помощью интеграла:

$$N = \frac{1}{\pi} \int_{0}^{\pi} \frac{\sin^6(10x)}{\sin^6 x} dx. \tag{1}$$

В этой замечательной формуле число 6 показывает, что вычисляется число шестизначных счастливых билетов, а число 10 указывает на десятичную систему числения. Если основание системы числения и число цфр билета иные, то формулу нужно изменить оченьным образом.

Г. А. Гальперин из Москвы и А. В. Корллюков из Гродно задались вопросы: что будет, если вычислять число счастливых билетов $N$ по приближенной формуле

$$N = \frac{1}{n} \sum_{k=1}^{n} f(x_k), \tag{2}$$

где $x_k = x_0 + k\pi/n$, $f(x) = \sin^6(10x)/\sin^6 x$. Они обнаружили, что при любом $n \geq 28$ и любом $x_0$ равенство (2) является точным! (Для билетов длины $2S$ и $p$-чной системы числения нужно быть $n \geq 1 + S(p-1)$).

Доказательство можно получить, следующая модель цифровов вывод формулы (1), приведенный в «Кванте» № 11 за 1978 год. Другой способ доказательства основан на том, что дробь $(\sin(px)/\sin x)^{2S}$ можно представить как «гонометрический многочлен» $f(x) = \sum_{k=1}^{n} a_k \times \sin(kx) + bk\cos(kx)$; для всякого такого многочлена выполнен равенство $$\frac{1}{\pi} \int_{0}^{x} f(x) dx = \frac{1}{n} \sum_{k=1}^{n} f(x_0 + k\pi/n)$$ при достаточно большом $n$ (подумайте, как связано $n$ со «степенью» $n_0$ тригонометрического многочлена !).

Вычислять число счастливых билетов на компьютере и на микрокалькуляторе удобнее по формуле (2), чем (1), тем более, что интерраал все равно заменяется на приближенное значение. Кроме того, из формулы (2) можно получить интересные следствия.

Пусть, например, дляна билета равна 2, а система числения десятичная. Тогда в формуле (2) достаточно взять 10 слагаемых. В качестве точек $x_k$ берем $\frac{\pi}{20}, \frac{3\pi}{20}, \dots, \frac{19\pi}{20}$. Число $N$ очень равно 10, а $\sin^2(10x_k) = 1$ для всех $k$. Поэтому

$$\frac{1}{\sin^2(10x)} + \frac{1}{\sin^2(3\pi/10)} = 12.$$

При других $S$ и $p$ читатели могут получить аналогичные равенства самостояльно.

А. А. Михайлов из г. Стучка Латвийской СССР предложает новый подход к задаче о счастливых билетах длины $2n$ в $p$-чной системе числения. Вот его рассудение. Прежде всего, число счастливых билетов равно числу билетов, сумма цфр которых равна $n(p-1)$ (попробуйте это доказать!). Это число, в свою очередь равно коэффициенту при $x^{n(p-1)}$ многочлена $f(x) = (1-x^p)^{2n}/(1-x)^{2n} = (1-x^p)^{2n} \times (1-x)^{-2n}$.

Чтобы найти этот многочлен, можно воспользоваться биномом Ньютона.

$$(1+t)^k = \sum_{S=0}^{k} \binom{k}{S} t^S,$$

где binominalные коэффициенты $\binom{k}{S}$ are равны $k!/S!(k-S)!$ при $0 \leq k \leq S$ и $0$ при $k > S \geq 0$. Binominalная формула верна и для отрицательных показателей $k$; при этом $\binom{-k}{S} = (-1)^S \binom{k+S-1}{S}$. Если выразить оба компоненты, входящих в $f(x)$, с помощью binома, то нетрудно найти коэффициент при $x^{n(p-1)}$. Окончательная формула А. А. Михайлов для числа счастливых билетов выглянит так:

$$N_{2n}^p = \sum_{S=0}^{n} (-1)^S \binom{2n}{S} \binom{n-S}{p+n-1}{2n-1},$$

где $m = \left[ n \left(1 - \frac{1}{p}\right) \right]$, квадратные скобки обозначают целую часть числа. Частный случай этой формулы для десятичной системы обнаружки также студенты из Иркутска Д. Балябин и С. Кривошен.

Для числа обчисленных счастливых билетов получаем

$$N_{6}^{10} = \binom{6}{0} \binom{32}{5} - \binom{6}{1} \binom{22}{5} + \binom{6}{2} \binom{12}{5} = 201376 - 6 \cdot 26334 + 15 \cdot 792 = 55252.$$

Как видите, формула (3) позволяет вычислять число счастливых билетов довольно просто!

Для $p=2$ есть еще более простое выражение для $N$. Действительно, в этом случае $f(x) = (1+x)^{2n}$, поэтому $N = \binom{2n}{n}$.

Кроме того, А. А. Михайлов отмечает, что число счастливых билетов совпадает с числом точек, лежащих строю внутри $2n$-мерного куба $[0, p+1]^{2n}$ на прохождение через центр гиперплоскости, перепределкой главной диагонали. Это число часто встречается в работе по современной вещественной алгебраической геометрии и называется числом Петровского (в честь академика И. Г. Петровского (1901—1973); см. комментарии в книге И. Г. Петровского «Избранные труды», выпущен в 1986 году издательством «Наука»).

*) Их также обозначают $C_k^S$.