Задача M314

Условие

Среди всех 9-значных чисел, в десятичной записи которых нет цифры 0, найти такое, для которого разность между самим числом и произведением его цифр:
a) наименьшая;
b) наиболее.

Каков будет ответ для $n$-значных чисел при любом $n$?

А. Г. Лейдерман

Решение

Среди всех 9-значных чисел, в десятичной записи комorbых нём цифры 0, найти макое, для коморого разность между самим числом и произведением его цифра a) наименьшая;
б) наибольшая;
Каков будем ответ для п-значных чисел при любом n?

Будем решать задачу сразу для n-значных чисел.
Начнем с задачи a). Пусть искомое число — обозначим его через A — записывается цифрами $a_1, \dots, a_n$: $A = \overline{a_1, \dots, a_n}$. Тогда
$$A = a_1 \cdot 10^n - 1 + a_2 \cdot 10^n - 2 + \dots + a_{n-1} \cdot 10 + a_n.$$
Обозначим разность между числом A и произведением его цифр через B:
$$B = a_1 \cdot 10^n - 1 + \dots + a_{n-1} \cdot 10 + a_n - a_1 \cdot a_2 \dots a_n.$$
Покажем, что если B — наименьшая разность, то у числа A не может быть одновременного двух цифр, отличных от единицы или девятки.
В самом деле, пусть есть две такие цифры: $a_k$ и $a_l$. Тогда, у увеличив, а затем уменьшив цифру $a_k$ на единицу, мы можем составить новые для n-значные числа (среди цифр которых не будет нулей):
$$A_1 = a_1 \cdot 10^n - 1 + \dots + (a_k + 1) \cdot 10^n - k + \dots + a_{n-1} \cdot 10 + a_n;$$
$$A_2 = a_1 \cdot 10^n - 1 + \dots + (a_k - 1) \cdot 10^n - k + \dots + a_{n-1} \cdot 10 + a_n.$$
Запишем разности $B_1$ и $B_2$ между числами $A_1, A_2$ и произведением их цифр:
$$B_1 = A_1 - a_1 \cdot \dots \cdot (a_k + 1) \cdot \dots \cdot a_{n-1} \cdot a_n = (A - a_1 \cdot \dots \cdot a_n) + 10^n - k - a_1 \cdot \dots \cdot a_{k-1} \cdot a_{k+1} \cdot \dots \cdot a_n = B + (10^n - k - a_1 \cdot \dots \cdot a_{k-1} \cdot a_{k+1} \cdot \dots \cdot a_n);$$
$$B_2 = A_2 - a_1 \cdot \dots \cdot (a_k - 1) \cdot \dots \cdot a_{n-1} \cdot a_n = B + (-10^n - k + a_1 \cdot \dots \cdot a_{k-1} \cdot a_{k+1} \cdot \dots \cdot a_n).$$
По предположению B — наименьшая разность; поэтому одновременное должно быть выполнться неравенства $B \leqslant B_1$ и $B \leqslant B_2$:
$$\begin{cases} 10^n - k - a_1 \cdot \dots \cdot a_{k-1} \cdot a_{k+1} \cdot \dots \cdot a_n \geqslant 0, \\ -10^n - k + a_1 \cdot \dots \cdot a_{k-1} \cdot a_{k+1} \cdot \dots \cdot a_n \geqslant 0. \end{cases}$$
откуда
$$a_1 \cdot \dots \cdot a_{k-1} \cdot a_{k+1} \cdot \dots \cdot a_n = 10^n - k.$$

Точно так же получим, что
$$a_1 \cdot \dots \cdot a_{l-1} \cdot a_{l+1} \cdot \dots \cdot a_n = 10^n - l.$$

Деля (1) на (2), получаем:
$$\frac{a_l}{a_h} = 10^{l-k} \quad (l \neq k),$$

но этого быть не может, поскольку $a_l$ и $a_k$ — натуральные числа, меньше 10.

Значит, у искомого числа одновременного двух цифр, отличных от 1 и 9, быть не может.

Предположим, что у искомого числа есть одна цифра, отличная от 1 и 9, — пусть это цифра $a_{n-p}$. Тогда, как и выше, имеем
$$10^p = a_1 \cdot \dots \cdot a_{n-p-1} \cdot a_{n-p+1} \cdot \dots \cdot a_n,$$

33

где цифры $a_1, \dots, a_{n-p-1}, a_{n-p+1}, \dots, a_n$ равны 1, либо 9. Но при $p \geqslant 1$ такое равенства быть не может: левая часть его делится на 10, а правая — не делится.

Если же $p = 0$, то тогда все цифры $a_1, \dots, a_{n-1}$ должны быть единицами, а цифра $a_n$ может быть любой. Само число при этом имеет вид $\underbrace{1 \dots 1}_{n-1} a_n$. Отметим, что разность между числом такого вида и произведением его цифра построена и не зависит от последней цифры $a_n$:

$$\underbrace{1 \dots 1}_{n-1} a_n - 1 \dots 1 \cdot a_n = \underbrace{1 \dots 1}_{n-1} 0.$$

Ниже мы показем, что именно эта разность и является наименшей (то есть, что цифра $\underbrace{1 \dots 1}_{n-1} a_n$ — искомые).

Птак, если у исключого числа есть цифра, отличная от 1 и 9, то оно обязательно вида $\underbrace{1 \dots 1}_{n-1} a_n$.

Предположим теперь, что все цифры исключого числа — единицами или девятки. Пусть это число состоит из $k$ девяток и $n-k$ единиц. Тогда произведение его цифра равно $9^k$ — построенным числу, и для того, чтобы разность между числом и произведением его цифра была наименшей, нужно, чтобы само число (составленное из $k$ девяток и $n-k$ единиц) было наименшим.

Понятно, что таким числом будет число $\underbrace{1 \dots 1}_{n-k} \underbrace{9 \dots 9}_{k},$ у которого все единицы стояят в старших разрядах.

Составим разность

$$B' = \underbrace{1 \dots 1}_{n-k} \underbrace{9 \dots 9}_{k} - 9^k.$$

Возьем теперь число, у которого на одну единицу больше: $\underbrace{1 \dots 1}_{n-k+1} \underbrace{9 \dots 9}_{k-1}$. Для него соответствующая разность равна

$$B'' = \underbrace{1 \dots 1}_{n-k+1} \underbrace{9 \dots 9}_{k-1} - 9^k - \underbrace{1 \dots 1}_{n-k+1} \underbrace{9 \dots 9}_{k-1} + 9^k-1 = 8(10^k-1-9^k-1) \geqslant 0$$

(Cравенство достаточно при $k=1$); то есть $B' \geqslant B''$.

Значит, заменяя всякий раз первую слева девятку единицей, мы тем самым уменьшаем разность между получаемыми числом и произведением его цифр. Поэтому числом, состоящим из одних только единиц и девяток, для которого указанная разность минимальная, является число $\underbrace{1 \dots 1}_{n-1}$.

В силу сказанного равше, от того, какая цифра стоит на последнем месте у числа, все остальные цифры которого равны единице, разность не зависит; то есть на последнем месте может быть любая цифра.

Итак, ответ в задаче a) такое: исключение $n$-значные числа имеет вид $\underbrace{1 \dots 1}_{n-1} a_n$, где $a_n$ — любая цифра.

Перейдем теперь к задаче b).

Рассуждая, как и прежде, получаем, что если число обладает тем свойством, что разность между ним и произведением

34

дением его цифр — наиболееяя, то все его цифры — либо единицы, либо девятки.

Пусть есть число, состоящее из $k$ девяток и $n - k$ единиц. Произведение цифр такого числа построено — равно $9^k$, поэтому для того, чтобы разность была наиболееяя, нужно, чтобы самое число было наиболеешим средним всех чисел, составленных из $k$ девяток и $n - k$ единиц.

Понятно, что таким числом является число $\underbrace{9 \dots 9}_{k} \underbrace{1 \dots 1}_{n - k}$.

Обозначим разность между ним и произведением его цифр через $A'$:

$$A' = \underbrace{9 \dots 9}_{k} \underbrace{1 \dots 1}_{n - k} - 9^k.$$

Посмотрим теперь, каково должно быть $k$, чтобы разность $A'$ между числом $\underbrace{9 \dots 9}_{k} \underbrace{1 \dots 1}_{n - k}$ и произведением его цифр была наиболееяя.

Увеличим $k$ на единицу: возьмем число $\underbrace{9 \dots 9}_{k + 1} \underbrace{1 \dots 1}_{n - k - 1}$.

Для получения числа разность равна

$$A'' = \underbrace{9 \dots 9}_{k + 1} \underbrace{1 \dots 1}_{n - k - 1} - 9^{k + 1}.$$

Уменьшим $k$ на единицу: получим

$$A''' = \underbrace{9 \dots 9}_{k + 1} \underbrace{1 \dots 1}_{n - k + 1} - 9^{k + 1}.$$

Имсем:

$$A' - A'' = \underbrace{9 \dots 9}_{k} \underbrace{1 \dots 1}_{n - k} - 9^k - \underbrace{9 \dots 9}_{k + 1} \underbrace{1 \dots 1}_{n - k - 1} + 9^{k + 1}$$

$$- 8 \cdot 10^{n - k - 1} + 9^k (9 - 1) = 8 \left( -10^{n - k - 1} + 9^k \right) \geq 0,$$

(3)

так как $A'$ по предположению наиболееяя разность.

Аналогично

$$A' - A''' = \underbrace{9 \dots 9}_{k} \underbrace{1 \dots 1}_{n - k} - 9^k - \underbrace{9 \dots 9}_{k + 1} \underbrace{1 \dots 1}_{n - k - 1} + 9^{k + 1}$$

$$= 8 \cdot 10^{n - k} - 9^{k + 1} (9 - 1) = 8 \left( 10^{n - k} - 9^{k + 1} \right) \geq 0.$$

(4)

Из (3) и (4) получаем систему неравенств:

$$\begin{cases} 9^k \geq 10^{n - k - 1}, \\ 10^{n - k} \geq 9^{k + 1}, \end{cases}$$

из которой

$$\begin{cases} k \geq \frac{n - 1}{\lg 9 + 1}, \\ k \leq \frac{n + \lg 9}{\lg 9 + 1}, \end{cases}$$

то есть

$$\frac{n - 1}{\lg 9 + 1} \leq k \leq \frac{n - 1}{\lg 9 + 1} + 1.$$

(5)

35

Так как $k$ — число целое, то из (5) следует, что

$$k = \left[ \frac{n-1}{\lg 9 + 1} + 1 \right],$$

где $[x]$ — целая часть числа $x$.

Итак, в задаче 6) искомое число имеет вид

$$\underbrace{9 \dots 9}_{k} \underbrace{1 \dots 1}_{n-k},$$

где $k = \left[ \frac{n-1}{\lg 9 + 1} + 1 \right].$

И. Н. Клумова, А. Г. Лейдерман

a) Вычислим сумму квадратов $2n+1$ последовательных натуральных чисел. Обозначив менше из них через $x-n$, получим:

$$S_{2n+1} = (x-n)^2 + (x-n+1)^2 + \dots + x^2 + (x+1)^2 + \dots + (x+n)^2 = (2n+1)x^2 + 2(1^2 + 2^2 + 3^2 + \dots + n^2) = (2n+1)x^2 + \frac{1}{3}n(n+1)(2n+1).$$

В частности, $S_3 = 3x^2 + 2$, $S_5 = 5x^2 + 10$, $S_7 = 7x^2 + 28$, $S_9 = 9x^2 + 60$, $S_{11} = 11x^2 + 110$. Сумма квадратов трех последовательных целых чисел не может быть точным квадратом, так как квадрат любого целого числа либо делится на 3, либо при делении на 3 дает остаток 1, а число $S_3 = 3x^2 + 2$ при делении на 3 дает остаток 2.

Докажем, что ни одно из чисел $S_5$, $S_7$ и $S_9$ также не является точным квадратом ни при каком целом $x$. Для этого воспользуемся таким очевидным свойством, вытекающим из единственной разложения на простые множители: если квадрат делится на простое $p$, то он должен делиться на $p^2$. Остается заметить, что $x^2 + 2$ никакого не делится на 5, $x^2 + 4$ никакого не делится на 7, а $3x^2 + 20$ никакого не делится на 3.

6. Это — числа 18, 19, …, 27, 28. В самом деле, число $S_{11} = 11(x^2 + 10)$ должно делиться на $11^2$, следовательно, и число $x^2 - 1 = (x^2 + 10) - 11$ должно делиться на 11. Но так как $x^2 - 1 = (x - 1)(x + 1)$, то либо $x - 1 = 11l$, либо $x + 1 = 11k$. При $l = 2$ получим $x = 23$, $S_{11} = 77^2$, так что

$$x - n = 23 - 5 = 18$$

и

$$18^2 + 19^2 + 20^2 + \dots + 28^2 = 77^2.$$

Э. Г. Готман

Рассмотрим сначала случай, когда все золото было сосредоточено в одной — «богатой»—стране. Тогда, если после перераспределения в этой стране остатется золотой запас $M$, то в страны, имеющие с ней общую границу, нужно распределить золота не меньше, чем $M/13$, в страны, имеющие с ними общую границу — не меньше, чем $M/169$, и так далее.

Введем понятие рассмотрения $\rho(A, B)$ между двумя странами $A, B$. Будем считать, что $\rho(A, B) = k$, если из страны $A$ можно проехать в страну $B$, пересекая границы $k$ раз, и нельзя, пересекая их меньше число раз. Теперь высказанное

*)Решение задачи M315 было опубlikовано в предыдущем номере.

36

дая страна лишилась не более половины именшегося у нее золота.

Страна, находящаяся на расстоянии $k > 0$ от «богатой» страны, должны граничить хотя бы с одной страной, находящаяся от «богатой» страны на расстоянии $k-1$, и поэтому не может граничить более чем с шестю странами, отстоящими от «богатой» страны на расстоянии $k+1$. Значит, количество страна, находящихся от «богатой» страны на расстоянии $k+1$, превыходит количество страна, находящихся на расстоянии $k$, не более, чем в 6 раз. Стран же, отстоящих от «богатой» на расстоянии 1, не больше 7. Из сказанного следует, что количество страна, находящихся от «богатой» страны на расстоянии $k$, не превыходит числа $7 \cdot 6^{k-1}$. Распределив в каждую страну, находящихся на расстоянии $k$, не превышает числа $7 \cdot 6^{k-1}$ золота (напомним, что «богатая» страна после распределения «получила» золотой запас $M$), мы истратим золота не больше, чем

$$M + 7 \cdot \frac{M}{13} + 7 \cdot 6 \cdot \frac{M}{13^2} + \dots = M + \frac{7}{6} M \left[ \frac{6}{13} + \left( \frac{6}{13} \right)^2 + \dots \right] = 2M.$$

Значит, первоначально в «богатой» стране было не больше 2$M$ золота, и тем самым после описанного перераспределения она лишилась не более половины именшегося у нее золота. То, что описанное перераспределение — требуемое, следует из того, что две граничные друг с другом страны $B$ и $C$ лежат либо на одном и том же расстоянии от третьей страны $A$, либо же эти расстояния отличия на единицу. Это — частный случай «неравенства треугольника»:

$$\rho (A, B) + \rho (B, C) \geq \rho (A, C)$$

при $\rho (B, C) = 1$ ($\rho (A, B)$ — расстояние от $A$ до $B$); доказите это «неравенство треугольника» для нашего расстояния в общем случае.

Заметим еще, что в случае, если на расстоянии $k$ от «богатой» страны находится ро вно $7 \cdot 6^{k-1}$ стран (см. рис. 1), то золотой запас, который необходимо перераспределить, в точности равен 2$M$, а потому $M$ — равно половина на первоначальное именование у «богатой» страны золота. Докажем, что распределив в каждую страну $A_i$

$$\sum_{k} M_k \cdot 13 - \rho (A_i, A_k)$$ золота, мы получим требуемое распределение. В самом деле, во-первых, каждая страна $A_i$ получает не менее $M_i$ золота, и, следовательно, лишается не больше половины именшегося у нее запаса в силу выбора $M_i$. Во вторых, если $A_i$ и $A_j$ граничящие страны, то $\rho (A_i, A_j) = 1$.

Страна $A_i$ получает $\sum_{k} M_k \cdot 13 - \rho (A_i, A_k)$ золота, страна $A_j - \sum_{k} M_k \cdot 13 - \rho (A_j, A_k)$. Подставляя $\rho (A_i, A_j) = 1$ в неравенства треугольника:

$$\rho (A_j, A_k) + \rho (A_i, A_j) \geq \rho (A_i, A_k),$$

$$\rho (A_i, A_k) + \rho (A_j, A_j) \geq \rho (A_j, A_k),$$

37

получаем:
$$\rho(A_j, A_k) + 1 \geq \rho(A_i, A_k),$$
$$\rho(A_i, A_k) + 1 \geq \rho(A_j, A_k),$$

то есть
$$1 - \rho(A_i, A_k) \geq -\rho(A_j, A_k),$$
$$- \rho(A_j, A_k) \geq -1 - \rho(A_i, A_k),$$

откуда для любого номера $k$:
$$13 \cdot M_k \cdot 13 - \rho(A_i, A_k) \geq M_k \cdot 13 - \rho(A_j, A_k) \geq$$
$$\geq \frac{1}{13} \cdot M_k \times 13 - \rho(A_i, A_k),$$

то есть
$$13 \sum_{k} M_k \cdot 13 - \rho(A_i, A_k) \geq \sum_{k} M_k \cdot 13 - \rho(A_j, A_k) \geq$$
$$\geq \frac{1}{13} \sum_{k} M_k \cdot 13 - \rho(A_i, A_k),$$

и каждые две границы друг с другом страны действительно после перераспределения отличия по количеству золота не более, чем в 13 раз.

Замечание. Суммы $\sum_{k} M_k \cdot 13 - \rho(A_i, A_k)$ всегда существует, если число страна конечно (очевидно), или же если можно указать такое число $C$, что во всех странах не больше $C$ золота (доказhte; вам помогет стать М. Л. Гервера «От перемены мест слагаемых…», опубликованная в «Кванте» № 9 за 1974 год). Существование такого числа $C$ предполагается в условиях задачи, — иначе утверждение задачи становится неверным. Постройте соответствующий пример.

Г. В. Егоров