Билеты и ящики

44

С. Фомин

Билеты и ящики

В этой заметке решается задача, предлагая в 1977 году на втором (исследовательском).type XI Всесоюзной олимпiadы по математике. Эта задача была помещена в «Задание к Кванта» («Квант», 1977, № 9, М465). Напомним ее формулировку.

Имеется тысяча билетов с номерами 000, 001, …, 999 и стю ящиков с номерами 00, 01, …, 99. Билет разрезается опускать в ящик, если номер ящика можно получить из номера этого билета вычеркиванем одной из цифр. Докажите, что

a) можно разложить все билеты в 50 ящиков;
b) нельзя разложить все билеты менее чем в 40 ящиков;
b) нельзя разложить все билеты менее чем в 50 ящиков.

Пусть вообще имеется 10^k билетов с k-значными номерами от 00…0 до 99…9. Билет разрезается опу-
скать в ящик, номер которого можно получить из номера этого билета вычеркиванем одной из цифр. Докажите, что

1. Функция F(k, N)

Начнем с вопроса, на первый взгляд, не связанного с нашей задачей.

Пусть k и N — два натуральных числа. Рассмотрим всевозможные наборы из k целых неотрицательных чисел, сумма которых равна N. Для каждой такого набора найдем сумму квадратов входящих в него чисел (рис. 1). Наименьшую из этих сумм обозначим F(k, N). Пусть она соответствует набору A = {a₁, a₂, …, aₖ}.

Лемма. Каждый цисла, входящих в набор A, отличаются не более чем на 1.

Доказательство. Предположим противное. Пусть, скажем, a₂ > a₁ + 1. Рассмотрим набор A’ = {a₁ + 1, a₂ - 1, a₃, …, aₖ}.

Поскольку

$$\left( a_1 + 1 \right)^2 + \left( a_2 - 1 \right)^2 = a_1^2 + a_2^2 - 2 \left( a_2 - a_1 \right) < a_1^2 + a_2^2,$$

сумма квадратов чисел, входящих в набор A’, меньше аналогичной суммы для A. Полученное противное доказывает lemму.

Теперь понятно, как вычислять F(k, N). Нужно разделить N на k с остатком и подбрать k чисел так, чтобы каждое из них было либо равно частному, либо на 1 больше его, а сумма этих чисел была равна N.

На рисунке 2 приведена таблица значений функций F(k, N) для небольших k и N.

Какова «геометрическая» интерпретация F(k, N)? Пусть для простоты k = 3. Тогда задачу нахождения F(k, N) можно воспринять следующим образом: найти в треугольнике ABC, задавемом в пространстве уравнений x₁ + x₂ + x₃ = N и неравенствами x₁ ≥ 0,

45

Рис. 2.

$x_2 \geq 0, x_3 \geq 0$ (рис. 3), мощу $M$ с целыми координатами, наименее удалению от начала координат $O$ (интересующая нас сумма квадратов есть не что иное, как квадрат расстояния от точки $O$ до $M$). Естественно, что нужно взять эту точку попытке к основанию перепределения, опущенного из $O$ на плоскость треугольника $ABC$, то есть к точке $\left(\frac{N}{3}; \frac{N}{3}; \frac{N}{3}\right)$.

Для $k > 3$ аналогичные расчужнения возможны с привлечением понятия $k$-мерного пространства.

Рассмотрим еще одну интерпретацию $F(k, N)$. Пусть для простоты $k = 2$. Тогда рассматриваемые наборы имеют вид $|a, N - a|(a - \text{целое неотрицательное})$, и перед нами стоит задача нахождения минимума функции $x \rightarrow x^2 + (N - x)^2$, заданной на множество целых чисел из intervala $[0, N]$. Эта функция — квадратный трехчлен; минимум достигается в точке $x = \frac{N}{2}$. Поэтому $F(2, N)$ равно $\frac{N^2}{2}$ или $\frac{N^2 + 1}{2}$ в зависимости от четности $N$ (рис. 4).

Для $k > 2$ нужно рассматривать соответствующее функцию $k - 1$ переменных и находить ее минимум.

2. Решение задач a) и b)

Расположим все ящики в виде квадрата $10 \times 10$, как показано на рис. 5, $a$. На рис. 5, $b$ этот квадрат $Q_0$ нарисован в привящном для нас виде; будем считать, что каждая его клетка — это ящик с соответствующим номером. Строчки и столбцы этого квадрата пропумерем цифрами от 1 до 9. Поскольку все цифры в условиях задачи равноправны, строчки и столбцы квадрата $Q_0$ можно переставлять.

Нам нужно выбрать некоторое количество ящиков и разложить все билеты в эти ящики. Договоримся клетки, соответствующие выбранным ящикам, закрашивать в $Q_0$. Пусть минимальное количество клетки

46

ТОК, а именно $n_0$, закрашено в нулевой строке; можно считать, что это первыые $n_0$ клеток строки. Расстояним теперь квадрат $Q_1$, получащийся из $Q_0$ вычеркиванием первых $n_0$ строкек и первых $n_0$ столбцов (рис. 6). Покажем, что все клетки $Q_1$ должны быть закрашены. Для этого возьмем ящики с номером $xy$, где $x \geq n_0$, $y \geq n_0$. В него обязаτεльно попадает билет $0xy$: его нельзя положить в ящики $0x$ и $0y$, так как соответствующие клетки не закрашены. Значит, клетка с номером $xy$ должна быть закрашена для всех $x \geq n_0$, $y \geq n_0$.

После темы, сколько же всего клеток закрашено в нашем квадрате $Q_0$. В каждой строке прямогольника $\Pi_0$ (см. рис. 6) закрашено по крайней мере $n_0$ клеток. В $Q_1$ закрашены все $(10-n_0)^2$ клеток. Таким образом, в $Q_0$ закрашено по крайней мере $n_0^2 + (10-n_0)^2$ клеток. Наименьшая из этих сумм равна $F(2, 10)$ 50. Так что, во всяком случае, в $Q_0$ закрашено не менее 50 клеток. С другой стороны, пятидесети ящиков с номерами, выписанными на рисунке 7, достаточно: вычеркив в номере каждого билета цифру так, чтобы оставались две цифры одинаковой четности, мы поместим этот билет в соответствующей ящик. Эти два сообщения завершают решение пунктов a) и b) задачи.

3. Решение задачи d)

Пусть теперь билеты $k$-значные. Будем считать, что у нас не 10 цифр, а $N$, где $N$ — некоторое произвольное натуральное число (так, как если бы

нас была принята $N$-ичная система численения).

Строки квадрата $Q_0$ занумерут теперь числа от 0 до $N-1$; таким образом, в $Q_0$ всего $N^2$ клеток.

По-прежнему будем считать, что в нулевой строке — $n_0$ закрашенных клеток, а в любой другой строке — не меняше, чем $n_0$. Аналогично построим квадрата $Q_1$. Поступим с $Q_1$ так же, как мы поступали с $Q_0$, — выберем в нем строкку, в которой меняше всего закрашенных клеток (пусть это его первая строкка, т. е. строкка с номером $n_0$ в исходном квадрате), обозначим количество закрашенных клеток в ней через $n_1$ и, выкинув из $Q_1$ первые $n_1$ строкек и столбцов, получим квадрата $Q_2$. С ним построим так же, и т. д., до квадрата $Q_{k-2}$ (рис. 8). Примогольники, аналогичные $\Pi_0$, обозначим через

Рис. 7.