Текст статьиВасильев Н. Б. Расстановка кубиков // Квант. — 1972. — № 4. — С. 4—9.
В этой статье мы расскажем решение одной из задач, предлагавшихся девятиклассникам и десятиклассникам на прошлогодней Всесоюзной математической олимпиаде в Риге (см. «Квант» №11, 1971). Она формулировалась так.
Задача. Куб с ребром длины $n$ разбит на $n^3$ единичных кубиков. Выберем несколько кубиков и проведём через центр каждого из них три прямые, параллельные рёбрам. Какое наименьшее число кубиков можно выбрать так, чтобы проведенные через них прямые перечеркнули все кубики?
Укажите ответ для маленьких значений $n$: для $n=2$, 3, 4.
Попробуйте найти огвет для $n=10$.
Решите общую задачу. Если вам не удастся найти точный ответ, докажите какие-либо неравенства, оценивающие сверху и снизу число отмеченных кубиков.
Заметьте, что эту задачу можно сформулировать так. Рассмотрим всевозможные наборы $x_1,x_2,x_3)$, где каждая из букв $x_1$, $x_2$, $x_3$ принимает одно из $n$ значений 1, 2, $\ldots$, $n$. Какое наименьшее число наборов нужно выбрать, чтобы для каждого из остальных наборов среди выбранных нашелся такой, который отличался бы от него только в одном месте (значением только одной из координат $x_1$, $x_2$, $x_3$)? Попробуйте найти оценки для числа наборов в более общей задаче, когда рассматриваются наборы не из трёх, а из четырёх и большего количества букв.
Формулировка с ладьями
Чтобы не путаться в словах «куб», «кубик» и «выбранный кубик», удобно переформулировать задачу в других терминах. Весь куб $n\times n\times n$ мы назовём «пространственной шахматной доской», каждый из кубиков $1\times1\times1$ — «клеткой», каждый выбранный кубик — «клеткой, занятой ладьёй». Будем считать, что ладья, стоящая в какой-то клетке $x$, держит под ударом все клетки, расположенные вдоль трех прямых, параллельных ребрам куба и проходящих через центр клетки $x$ (в том числе будем считать, что ладья бьёт и саму эту клетку $x$ (рис. 1)). Тогда вопрос, поставленный в условии, можно сформулировать так: какое наименьшее число ладей можно расставить на доске $n\times n\times n$, чтобы они били всю доску (т. е. все клетки без исключения)?
Рис. 1. Ладья, стоящая на поле 222 [розовый кубик), бьёт десять полей: кроме самого поля 222, ещё 122, 322, 422 (в направлении $x_1$ в «ширину»), 212, 232, 242 (в направлении $x_2$ в «высоту»), 221, 223 и 224 (в направлении $x_3$ в «глубину»).
Упражнение 1. Решите аналогичную задачу для «плоской» шахматной доски $n\times n$. (Ответ: $n$. Заметьте, что если на доске $n\times n$ стоит меньше чем $n$ ладей, то найдутся горизонталь и вертикаль, свободные от ладей.)
Первоначальные грубые оценки
Обозначим через $A_n$ наименьшее количество ладей, которые могут побить всю доску $n\times n\times n$.
Поскольку на доске $n\times n\times n$ каждая ладья бьёт $3n-2$ клеток, а всего клеток $n^3$, то, чтобы побить всю доску, нужно расставить по крайней мере $\dfrac{n^3}{3n-2}$ ладей. Другими словами,
$$
A_n\ge\dfrac{n^3}{3n-2}.\tag1
$$
Отсюда следуег, что
$$
A_2\ge2,\quad A_3\ge4,\quad A_4\ge7,\quad A_5\ge10.
$$
Легко придумать пример расстановки $n^2$ ладей, быющих всю доску (их можно расставить в одном горизонтальном «слое»).
Это даёт такую грубую оценку:
$$
A_n\le n^2.\tag2
$$
Упражнение 2. Докажите, что
$$
A_n\le\dfrac{3n^2}4,
$$
воспользовавшись следующим соображением: если расставить $n_1$, ладей вдоль ребра $n_1$ доски $n_1\times n_2\times n_3$, то после этого останется решить задачу для доски $n_1\times(n_2-1)\times(n_3-1)$.
Запись расстановок «в плане»
При $n=2$, очевидно, двух ладей достаточно, чтобы держать под ударом все восемь клеток (рис. 2), т. е. $A_2=2$. Несколько труднее исследовать случай $n=3$. Пример нужной расстановки пяти ладей показан на рисунке 3.
Рис. 2. Ладьи 111 и 222 бьют всю доску $2\times2\times2$.Рис. 3. Ладьи 111, 223, 232, 322 и 333.
В этом рисунке уже довольно трудно разобраться. С увеличением $n$ дело ещё ухудшится. Поэтому необходимо придумать более удобный способ описания расстановок ладей. Можно было бы, конечно, просто перечислять все «координаты» ладей, как это сделано в подписях под рисунками, но мы предложим более наглядный способ записи.
Будем называть слоем множество клеток, центры которых лежат в плоскости, параллельной одной из граней доски, и линией — множество клеток, центры которых лежат на одной прямой, параллельной ребру; слой состоит из $n^2$ клеток, линия — из $n$ клеток. Нарисуем проекцию доски на одну из граней, скажем, на плоскость $Ox_1x_2$ (вид спереди) и на каждом поле полученной доски $n\times n$ напишем номер слоя, в котором встречается ладья, проектирующаяся на это поле. Тогда расстановка ладей, изображённая на рисунке 3, запишется так, как показано на рисунке 4 (ситуации, когда в одной линии стоит больше одной ладьи, у нас не будут встречаться, поэтому на каждом поле доски $n\times n$ будет записываться не более чем одно число). Заметьте, что на рисунке 4 для каждого пустого поля в строке и столбце, на пересечении которых оно стоит, встречаются все номера: 1, 2 и 3. Это и означает, что каждое поле доски $3\times3\times$, которое не бьётся в направлении $x_3$, бьётся или в направлении $x_1$, или в направлении $x_2$.
Рис. 4
Итак, мы убедились, что $A_3\le5$. То, что $A_3\ge4$, было уже доказано (см. (1)). Возникает вопрос: чему же равно $A_3$: 4 или 5? Мы предоставляем читателям возможность разобраться в случаях $n=3$, $n=4$ и т. д., а затем перейдем сразу к общему случаю.
Упражнение 3.
Докажите, что 4 ладьи нельзя расставить так, чтобы они били всю доску $3\times3\times3$;
укажите пример расстановки 8 ладей, которые бьют всю доску $4\times4\times4$;
докажите, что $A_4=8$.
Общий случай. Формулировка результата
В нашей задаче едва ли не самое трудное — выдвинуть правильную гипотезу: чему равно $A_n$. Зная ответ, уже значительно легче и построить пример (т. е. оценить $A_n$ сверху), и доказать, что меньшим числом ладей обойтись нельзя. А ответ таков:
$$
A_n=\begin{cases}
\dfrac{n^2}2,&\text{если}~n~\text{чётно},\\\\[-6pt]
\dfrac{n^2+1}2,&\text{если}~n~\text{нечётно}.
\end{cases}
$$
В частности, $A_4=8$, $A_5=13$, $\ldots$, $A_{10}=50$.
Рис. 5
Примеры «оптимальной» расстановки $A_n$ ладей ясны из рисунков 5, а($n$ чётно) и 5, б ($n$ нечётно). Легко проверить, что все поля, которые не бьются в направлении $x_3$, бьются либо в направлении $x_2$, либо в направлении $x_2$: в каждом «кресте» — строке и столбце, на пересечении которых стоит пустое поле — встречаются все номера от 1 до $n$.
Осталось доказать, что в меньшем количестве ладьи не могут побить всю доску.
Первое доказательство
Пусть $M$ ладей расставлены так, что они бьют все клетки доски. Выберем из всех слоёв тот, в котором количество ладей минимально (если таких слоёв несколько, возьмём любой из них). Можно считать, что он расположен параллельно плоскости $Ox_1x_2$. Обозначим этот слой через $S$, а количество ладей в нём — через $m$. Пусть эти $m$ ладей бьют $m_1$ рядов в направлении $x_1$ и $m_2$ рядов в направлении $x_2$ (можно считать, что $m_1\ge mg_2$; разумеется, $m\ge m_1$ и $m\ge m_2$). Тогда в слое $S$ эти ладьи оставляют непобитыми $(n-m_1)(n-m_2)$ клеток, которые должны биться в направлении $x_3$. (На рисунке 6 слой $S$ — передний, клетки, занятые ладьями, — красные, $n=9$, $m=m_1=4$, $m_2=3$.)
Рис. 6Рис. 7
Рассмотрим теперь все $n$ «горизонтальных» слоёв — слоёв, параллельных плоскости $Ox_1x_3$. В тех $n-m_1$ из них, которые не содержат ладей слоя $S$, как мы убедились, должно быть не менее $(n-m_1)(n-m_2)$ ладей. В каждом из остальных $m_1$ слоёв (зелёных на рисунке 6) — не менее $m$ ладей (по выбору $m$). Поэтому
$$
M\ge(n-m_1)(n-m_2)+mm_1\ge(n-m_1)^2+m_1^2.
$$
Но минимальное значение правой части при целом $m_1$, как легко доказать, как раз равно $\dfrac{n^2}2$ при нечётном $n$ и $\dfrac{n^2+1}2$ при нечётном $n$ (график функции $f(x)=(n-x)^2+x^2$ изображён на рисунке 7).
Второе доказательство
Лемма. Пусть в таблице $n\times n$ стоят целые неотрицательные числа так, что если в каком-то поле стоит 0, то сумма всех чисел строки и столбца, на пересечении которых стоит это поле, не меньше $n$. Тогда сумма всех чисел таблицы не меньше $\dfrac{n^2}2$ (и следовательно, если все числа в таблице целые, то при нечётном $n$ эта сумма не меньше $\dfrac{n^2+1}2\Big)$.
Из леммы нужная оценка для $A_n$ получается легко: достаточно спроектировать доску на одну из граней и написать в каждом поле полученной таблицы $n\times n$, сколько ладей в неё спроектировалось. Ясно, что условие леммы для полученной таблицы будет выполнено.
Осталось доказать лемму. Мы не будем этого делать, поскольку эта лемма уже встречалась недавно в «Кванте»: как это ни парадоксально, она предлагалась в том же прошлом году в качестве отдельной задачи на Международной олимпиаде (см. «Квант» №12, 1971 г.). К сожалению, второе доказательство нашей задачи, а тем самым и лемма не рассказывались на разборе задач Всесоюзной олимпиады, так что этой леммы не знали ни руководители советской команды (иначе они, разумеется, добились бы, чтобы её не предлагали школьникам, как слишком известную), ни участникам нашей команды (иначе бы они все решили её безупречно).
Итак, основная задача, о которой идет речь в пунктах а), б) и в) условия, решена.
Замечания по поводу обобщений
Что же касается более общей задачи, сформулированной в пункте г), — аналогичной задачи не для «трёхмерной», а для «$k$-мерной» доски ($k\ge4$), то здесь окончательный результат не известен. Для минимального числа $A_n^k$ ладей, бьющих всю доску $n\times n\times{\ldots}\times n$ (мы сохраняем шахматную терминологию, но напомним, что теперь клетка $x$ — это набор из $k$ чисел $(x_1,x_2,{\ldots},x_k)$, где каждое $k$ принимает значение от 1 до $n$), легко получить оценки, аналогичные (1), (2):
$$
A_n^k\le n^{k-1},\quad A_n^k\ge\dfrac{n^k}{k(n-1)+1}.
$$
Упражнение 4. Докажите эти неравенства. Постарайтесь улучшить оценку $n^{k-1}$, используя те же соображения, что и в упражнении 2.
Поскольку $A_n^2=n$ и $A_n^3$ равно $\dfrac{n^2}2$ или $\dfrac{n^2+1}2$, напрашивается гипотеза, что $A_n^k$ близко к $\dfrac{n^{k-1}}{k-1}$. Эту гипотезу, наряду с другими, обсуждали участники олимпиады и члены жюри не только во время олимпиады, но и после неё. Один из наиболее интересных результатов нам сообщили выпускник физико-математической школы при Ленинградском университете Д. Григорьев и наш читатель Б. Гинзбург: им (независимо) удалось доказать, что если $M$ ладей бьют всю доску и при этом никакие две не бьют друг друга, то $M\ge\dfrac{n^{k-1}}{k-1}$ доказательство мы помещаем в конце статьи). По-видимому, этот результат верен и без дополнительного предположения, выделенного курсивом, т. е. верно неравенство $A_n^k\ge\dfrac{n^{k-1}}{k-1}$‚ причём, как показывают примеры, при $n\gt k$ эта оценка довольно близка к точной (или даже в точности совпадает с ней).
Однако оценка $\dfrac{n^{k-1}}{k-1}$ заведомо не является «очень точной» при всех $n$ и $k$.
Например, если $n=2$, то $\dfrac{n^{k-1}}{k-1}=\dfrac{2^{k-1}}{k-1}$, и «грубая» оценка $\dfrac{n^k}{k(n-1)+1}=\dfrac{2^k}{k+1}$ оказывается лучше (при $k\gt3$); при больших $k$ число $\dfrac{2^k}{k+1}$ примерно в два раза больше, чем $\dfrac{2^{k-1}}{k-1}$.
Одна задача, очень близка к нашей по формулировке, является значительно более исследованной — прежде всего, потому, что она важна для приложений. В «шахматных терминах» она звучит так: какое наибольшее число ладей можно расставить на $k$-мерной доске $n\times n\times{\ldots}\times n$, чтобы они не били друг друга? (Другой вариант: чтобы никакое поле не билось двумя ладьями?) Иначе говоря: какое множество $Y$ наборов $y=(y_1,y_2,{\ldots},y_k)$ можно составить так, чтобы а) каждые два набора в $Y$ отличались более чем в одной координате, или б) каков бы ни был набор $x=(x_1,x_2,{\ldots},x_k)$, в множестве $Y$ найдётся не больше одного набора $y$, отличающегося от $x$ лишь в одной координате? Сформулированные задачи прямо относятся к теории информации, точнее, к её разделу, — теории кодов, исправляющих ошибки. Эта теория занимается задачами такого типа: составить множество $Y$ «слов» $(y_1,y_2,{\ldots},y_k)$ такое, что если при передаче одного из этих слов (скажем, по телеграфу или по каналу связи в вычислительной машине) вкралась ошибка в какой-то «букве», то эту ошибку можно было бы обнаружить, а ещё лучше, исправить, т. е. восстановить переданное «слово». Поэтому множество $Y$, удовлетворяющее условию а), называется «кодом, обнаруживающим одиночные ошибки», а удовлетворяющее условию б) — «кодом, исправляющим одиночные ошибки». Вы видите, что в математике слово «код» используется не совсем так, как в книгах про шпионов.
Упражнение 6. Пусть $B_n^k$ — наибольшее число ладей, которые можно расставить на $k$-мерной доске $n\times n\times{\ldots}\times n$ так, чтобы они не били друг друга.
Какое число больше: $B_n^k$ или $A_n^k$?
Найдите $B_n^2$, $B_n^3,$ $B_2^4$.
Теория кодов представляет собой, пожалуй, самый яркий пример применения современной алгебры в далёкой от неё, на первый взгляд, области, прямо связанной с техническими приложениями. Ей посвящено много научных работ и несколько толстых книг, она быстро развивается и заслуживает специального знакомства.
Приложение
Теорема. Пусть $X$ — множество всех наборов $x=(x_1,x_2,{\ldots},x_{k+1})$, где каждая из $k+1$ координат $x$ принимает $n$ значений: 1, 2, $\ldots$, $n$; $Y$ — подмножество $X$ такое, что
любые два набора из $Y$ отличаются хотя бы двумя координатами и
для каждого $x$ из $X$ существует набор $y$ из $Y$, отличающийся от $x$ не более чем в одной координате.
Тогда в $Y$ не более $\dfrac{n^k}k$ элементов.
Доказательство. Пусть $\alpha(x)=1$, если $x$ принадлежит $Y$, и $\alpha(x)=0$, если нет. Положим
$$
\begin{gather*}
\beta(x)=\beta(x_1,x_2,{\ldots},x_k)=\textstyle\sum\limits_{1\le x_{k+1}\le n}\alpha(x_1,x_2,{\ldots},x_k,x_{k+1});\\
\gamma_i(x)=\gamma_i(x_1,{\ldots},x_{i-1},x_{i+1},{\ldots},x_k)=\textstyle\sum\limits_{1\le x_i\le n}\beta(x_1,{\ldots},x_k),\quad\text{где}~i=1{,}~2{,}~{\ldots}{,}~k.
\end{gather*}
$$
(«Укороченные» наборы из $k$ и $k-1$ координат мы будем обозначать той же буквой $x$, помня, что у аргументов $\beta$ всегда выброшено $x_{k+1}$, а у $\gamma_i$ — и $x_{k+1}$, и $x_i$.) По условию (1) $\beta(x)\le1$ для любого $x$. По условию (2), если $\beta(x)=0$ для некоторого $x$, то $\sum\limits_{1\le i\le k}\gamma_i(x)\ge n$ для этого $x$. Поэтому для всех $x$ без исключения
$$
\textstyle\sum\limits_i\gamma_i(x)(1-\beta(x))\ge n(1-\beta(x)).
$$
Просуммируем все такие неравенства, соответствующие $n^k$ различным наборам $(x_1,x_2,{\ldots},x_k)$. Это суммирование обозначим буквой $\sum\nolimits'$, а суммирование по всем координатам, кроме $x_i$, — через $\sum\nolimits_i'$. Пусть общее число элементов $Y$ разно $M$. Тогда, поскольку $\sum\nolimits'\beta(x)=M$ и $\sum\nolimits_i'\gamma_i(x)=M$ для каждого $i$, получим
$$
\textstyle\sum\limits_i\left(nM-\sum\nolimits_i'\gamma_i^2(x)\right)\ge n^{k+1}-nM.
$$
Поскольку сумма квадратов $N$ вещественных чисел всегда не меньше квадрата их суммы, делённой на $N$, левая часть не больше
$$
\textstyle\sum\limits_i\left(nM-\sum\nolimits_i'\gamma_i^2(x)\right)\le\sum\limits_i
\left(nM-\dfrac{\left(\sum\nolimits_i'\gamma_i(x)\right)^2}{n^{k-1}}\right)=knM-\dfrac{kM^2}{n^k-1}.
$$
Таким образом, верно неравенство $knM-\dfrac{kM^2}{n^{k-1}}\ge n^{k+1}-nM$, откуда $M\le\dfrac{n^k}k$.
