Расстановка кубиков

6

Рис. 4.

Будем назвать слоем множество клеток, центры которых лежат в плоскости, параллельной одной из граней dockки, и линей — множество клеток, центры которых лежат на одной прямой, параллельной ребру; слой состоит из $n^2$ клеток, линии — из $n$ клеток. Нарисуем проекцию dockки на одну из граней, скажем, на плоскость $Ox_1x_2$ (вид спереди) и на каждом поле полученной dockки $n \times n$ напишем номер слоя, в котором встречается ладья, проектирующая на это поле. Тогда расстановка ладей, изображенная на рисунке 3, запишется так, как показано на рисунке 4 (ситуации, когда в одной линии стоит больше одной ладьи, у нас не будет встречаться, поэтому на каждом поле dockки $n \times n$ будет записывать не более чем одно число). Заметьте, что на рисунке 4 для каждой пустого поля в строке и столбце, на пересечении которых оно стоит, встречаются все номера: 1, 2 и 3. Это и означает, что каждое поле dockки $3 \times 3 \times 3$, которое не будет в направлении $x_3$, будет или в направлении $x_1$, или в направлении $x_2$.

Итак, мы убедились, что $A_3 \leq 5$. То, что $A_3 \geq 4$, было уже доказано (см. (1)). Возникает вопрос: чем же равно $A_3$: 4 или 5? Мы предоставляем читательам возможность разо-

браться в случае $n=3, n=4$ и т. д., а затем перейдем сразу к общему случаю.

Упражнение, что 4 ладьи нельзя расставить так, чтобы они были всего dockку $3 \times 3 \times 3$; 6) указывает пример расстановки 8 ладей, которые быот всего dockку $4 \times 4 \times 4$; в документа, что $A_4=8$.

Общий случай. Формулировка результата

В нашей задаче edва ли не самое трудное — вывинуть правильногипотезу: чем равно $A_n$. Эта ответ, уже значительно легче и построить пример (то есть оценить $A_n$ сверху), и доказать, что меньше числом ладей обойтись нельзя. А ответ таков:

$$A_n = \begin{cases} \frac{n^2}{2}, \text{ если } n \text{ четно}, \\ \frac{n^2 + 1}{2}, \text{ если } n \text{ нечетно}. \end{cases}$$

В частности, $A_4=8$, $A_5=13, \dots, A_{10}=50$.

Примеры «оптимальный» расстановки $A_n$ ладей ясны из рисунков 5, $a$ ($n$ четно) и 5, $b$ ($n$ нечетно). Легко проверить, что все поля, которые не быются в направлении $x_3$, быются либо в направлении $x_1$, либо в направлении $x_2$: в каждом «кресте» — строке и столбце, на пересечении которых стоит пустое поле — встречаются все номера от 1 до $n$.

Осталось доказать, что в меньше количества ладьи не могут побить всю dockку.

Первое доказательство

Пусть $M$ ладей расставлены так, что они быот все клетки dockки. Выберем из всех слоев тот, в котором количество ладей минимально (если таких слоев несколько, возможно ли их). Можно считать, что он расположен параллельно плоскости $Ox_1x_2$. Обозначим этот слой через $S$, а количество ладей в нем — через $m$. Пусть эти $m$ ладей быот $m_1$ рядов в направлении $x_1$ и $m_2$ рядов в направлении $x_2$ (можно считать, что $m_1 \geq m_2$; разумеется, $m \geq m_1$ и $m \geq m_2$). Тогда

8

Второе доказательство

Лемма. Пусть в таблице $n \times n$ стоит целые неотрицательные числа так, что если в каком-то поле стоит 0, то сумма всех чисел строки и столбца, на пересечении которых стоит это поле, не меньше $n$. тогда сумма всех чисел таблицы не меньше $\frac{n^2}{2}$ (и следовательно, если все числа в таблице целые, то при нечетном $n$ эта сумма не меньше $\frac{n^2+1}{2}$).

Из леммы нужно оценка для $A_n$ получается легко: достаточно спроектировать доску на одну из граней и написать в каком поле полученной таблицы $n \times n$, сколько ладей в нее спроектировалось. Ясно, что условие леммы для полученной таблицы будет выполнено.

Осталось доказать лемму. Мы не будем этого делать, поскольку эта лемма уже встречалась недавно в «Кванте»: как это ни парадоксально, она предлагалась в том же прошлом году в качестве отдельной задачи на Международной олимпийде (см. «Кванте» № 12, 1971 г.). К сожалению, второе доказательство нашей задачи, а тем самым и лемма не расссказывались на разборе задачи Всеюозной олимпийде, так что этой леммы не знали ни руководители советской команды (инчете они, разумется, добавились бы, чтобы ее не предлагали школьникам, как слишком известную), ни участникам нашей команды (инчете они все решили ее безпречно).

Итак, основная задача, о которой идет речь в пунктах a), б) и в) условия, решения.

Замечания по поводу обобщений

Что же касается более общей задачи, сормулированной в пункте r),— аналогичной задачи не для «трехмерной», а для «k-мерной» доски ($k \geq 4$), то здесь окончательный результат не известен. Для минимального числа $A_n^k$ ладей, быоших всего доску $n \times n \times \dots \times n$ (мы сохраняем шахматную терминологию, но например, что теперь клетка $x$ — это набор из $k$ чисел ($x_1, x_2, \dots, x_k$),

где каждое $k$ принимает значение от 1 до $n$), легко получить оценки, аналогичные (1), (2):

$$A_n^k \leq n^{k-1}, A_n^k \geq \frac{n^k}{k(n-1)+1}.$$

У разжене 4. Докажите эти неравенства. Постраайтесь улучшить оценку $n^{k-1}$, используя те же соображения, что и в упражнения 2.

Поскольку $A_n^2=n$ и $A_n^3$ равно $\frac{n^2}{2}$ или $\frac{n^2+1}{2}$, направивется гипотеза, что $A_n^k$ близко к $\frac{n^{k-1}}{k-1}$. Эту гипотезу, наряду с другими, обсуждали участники оlimппады и члены жюри не только во время оlimппады, но и после нее. Однако из наиболее интересных результатов нам сообщили выпускник физико математического школа при Ленинградском университете Д. Григорьев и наш читатель В. Гинзбург: им (независимо) удалось доказать, что если $M$ ладей быот всего доску и при этом никакие две не былом другие, то $M \geq \frac{n^{k-1}}{k-1}$ (доказательство мы помещаем в конце статьи). По-видимому, этот результат верен и без дополнительного предположения, выделенного курсиом, то есть верен неравенство $A_n^k \geq \frac{n^{k-1}}{k-1}$, причем, как показывалот примеры, при $n > k$ эта оценка довольно близка к точной (или даже в точности совпадает с ней).

Однако оценка $\frac{n^{k-1}}{k-1}$ зависит не является «очень точной» при всех $n$ и $k$.

Например, если $n=2$, то $\frac{n^{k-1}}{k-1} = \frac{2^{k-1}}{k-1}$, и «грубая» оценка $\frac{n^k}{k(n-1)+1} = \frac{2^k}{k+1}$ оказалась лучшей (при $k>3$); при больших $k$ число $\frac{2^k}{k+1}$ применено в два раза больше, чем $\frac{2}{k-1}$.

У разжене 5. Найдите $A_2^4, A_3^4, A_2^5$.

Некоторые слов про задачи о кодах

Одна задача, очень близка в нашей по формулировке, является значительной преждевременной — преждевременно, потому что она важна для приложений. В «шахматных терминах» она звучит так: какое наиболее

9

шее число ладей можно расставить на $k$-мерной доске $n \times n \times \dots \times n$, чтобы они не были друг друга? (Другой вариант: чтобы никакое поле не было двуяяями?) Иначе говоря: какое множество $Y$ наборов $y = (y_1, y_2, \dots, y_k)$ можно составить так, чтобы а) каждый два набора в $Y$ отличались более чем в одной координате, или б) каждый ни был набор $x = (x_1, x_2, \dots, x_k)$, в множество $Y$ найдется не больше одного набора $y$, отличаться от $x$ лишь в одной координате? Сформирование заданий прямо относится к теории информатии, точнее, к ее разделу, — теории кодов, исправляющих ошибки. Эта теория занимается задачами такого типа: составить множество $Y$ «слов» $(y_1, y_2, \dots, y_k)$ такое, что если при передаче одного из этих слов (скажем, по телефapy или по каналу связи в вычислительной машине) включается в какой-то «букве», то эту ошибку можно было бы обнаружить, а еще лучше, исправить, то есть восстановить переданное «слов». Поэтому множество $Y$, удовлетворяющее условию a), называется «кодом, обнаруживающим одиночные ошибки», а удовлетворящее условию б) — «кодом, исправляющим одиночные ошибки». Вы видите, что в математике слово «код» используется несовсем так, как в книгах про шпинов.

У праванении б. Пусть $B_n^k$ — наиболее число ладей, которые можно расставить на $k$-мерной доске $n \times n \times \dots \times n$ так, чтобы они не были друг друга a) Какое число больше: $B_n^k$ или $A_n^k$? б) Найдите $B_n^2, B_n^3, B_n^4$.

Teория кодов представляет собой, пожалуй, самый яркий пример применения современной алгебры в дальнейот нее, на первый взгляд, области, прямо связанной с техническими приложениями. Ей посвящего много научных работ и несколько толстых книг *, она быстро развивается и заслуживает специализацию знакомства.

*) У. Питерсон. Коды, направляющие ошибки, «Мир», 1964; Э. Берлекэм п Алгебраической теории кодирования, «Мир», 1971.

Приложение

Теорема. Пусть $X$ — множество всех наборов $x = (x_1, x_2, \dots, x_k+1)$, где каждая из $k+1$ координат $x$ принимает $n$ значений: $1, 2, \dots, n$; $Y$ — подмножество $X$ такое, что (1) любые два набора из $Y$ отличаются хотя бы двумя координатами и (2) для каждой $x$ из $X$ существует набор $y$ из $Y$, отличаться от $x$ не более чем в одной координате. Тогда в $Y$ не более $n^k/k$ элементов.

Доказательство. Пусть $\alpha(x)=1$, если $x$ принадлежит $Y$, и $\alpha(x)=0$, если нет. Положим $\beta(x)=\beta(x_1, x_2, \dots, x_k)$:

$$\sum_{i=1}^{k} \alpha(x_i, x_j, \dots, x_k) = \sum_{i=1}^{k} \alpha(x_i, x_j, \dots, x_k) = \sum_{i=1}^{k} \beta(x_i, x_j, \dots, x_k)$$

(«Укороченные» наборы из $k$ и $(k-1)$ координат мы будем обозначать той же буквой $x$, помня, что у аргументов $\beta$ всегда выброшено $x_{k+1}$, а $y \gamma_i - x_{k+1}$, и $x_i$. По условию (1) $\beta(x) \leq 1$ для любого $x$. По условию (2), если $\beta(x)=0$ для некоторого $x$, то $\sum_{i=1}^{k} \gamma_i(x) \geq n$ для этого $x$. Поэтому для всех $x$ без исключения

$$\sum_{i=1}^{k} \gamma_i(x) (1-\beta(x)) \geq n (1-\beta(x))$$

Просуммируем все такие неравенства, соответствующие $n^k$ различных наборам $(x_1, x_2, \dots, x_k)$. Это суммирование обозначим буквой $\Sigma'$, а суммирование по всем координатам, кроме $x_i$, — через $\Sigma'_i$. Пусть общее число элементов $Y$ разно $M$. Тогда, поскольку $\Sigma'_i(x)=M$ и $\Sigma'_i(y)=M$ для каждой $i$, получим

$$\sum_{i=1}^{k} (nM - \sum_{i=1}^{k} \gamma_i^2(x)) \geq n^{k+1}-nM$$

Поскольку сумма квадратов $N$ вещественных чисел не меньше квадратных сумм, деленной на $N$, левая часть не большеше

$$\sum_{i=1}^{k} (nM - \sum_{i=1}^{k} \gamma_i^2(x)) \leq \sum_{i=1}^{k} \left( nM - \frac{(\sum_{i=1}^{k} \gamma_i(x))^2}{n^{k-1}} \right) = knM - \frac{kM^2}{n^{k-1}}.$$

Таким образом, верно неравенство

$$knM - \frac{kM^2}{n^{k-1}} \geq n^{k+1}-nM,$$

откуда $M \leq n^{k/k}$.