[Решения задач М3—М5]

42

М3. (а) На рисунке 1, а плоскость покрыта квадратами пяты цветов. Центры квадратов одного и того же цвета расположены в вершинах квадратной сетки. При каком числе цветов возможно аналогичное заполнение плоскости?

(б) На рисунке 1, б плоскость покрыта шестиугольниками сем и цветов так, что центры шестиугольников одного и того же цвета образуют вершины решетки из одинаковых правильных треугольников. При каком числе цветов возможно аналогичное построение?

Примечние. В первой задаче число цветов может равнять единицу (все квадраты одного цвета) и двум (как на шахматной доске). Во второй задаче вы без труда найдете решения с одним цветом и с третья цветами. Желательно дать полное решение задач, т. е. описать все раскраски, удовлетворяющие указанным условиям. Присылайте, однako, и неполные решения, если они показутся вам интересными. Подумайте, например, существует ли во второй задаче решения с тринадцатью цветами?

Решение*)

Тепер будем считать правильным только такое заполнение плоскости квадратами (или шестиугольниками), при котором сетка, соответствующая какому-то одному цвету, имеет такие же размеры и направления сторон квадратов (или треугольников), как и сетка, соответствующая любому другому цвету. Иначе говоря, все сетки должны получаться друг из друга параллельным сдигром. Разумеется, разные сетки не могут быть закрашены одним цветом. Решение задачи для общих случаев (квадраты и шестиугольники) аналогично, и мы рассмотрим оба случая сразу.

1. Докажем сначала, что если плоскость заполнения указанным образом, то число цветов равно $k^2 + l^2$ в случае квадратов и $k^2 + kl + l^2$ в случае шестиугольников, где $k, l$ — целые неотрицательные числа (но не равные нулю одновременно)**).

*) Начало решения этой задачи смотри в «Кванте» № 7, стр. 54.
**) Существуют и другие формулы, представляющие те же самые множества чисел, например, $k^2 - kl + l^2$ для шестиугольников,

43

Прием за единцу длины расстояние между центрами двух соседних квадратов или шестиугольников.

Начертим жирными черными линяями сетку, проходящую через центры квадратов или шестиугольников одного цвета, скажем, красного (рис. 2, 3).

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

Пусть $ABCD$ — один квадрат или один ромб сетки. Выведем формулу для его площади.

В случае квадрата проведем через точки $A$ и $B$ прямые, параллельные сторонам окруженных квадратков и точку их пересечения обозначим $M$. Длины $AM=k$ и $BM=l$ — целые числа (одно из них может быть равно нулю). На рисунке 1 $k=3$, $l=2$. Тогда $AB=\sqrt{k^2+l^2}$, а площад $ABCD$ равна $k^2+l^2$.

В случае ромба проведем через точки $A$ и $B$ прямые, параллельные апсфемам шестиугольников, и точку их пересечения обозначим $M$. Угол $AMB$ может оказаться равным $120^\circ$ или $60^\circ$. Проведем прямые так, чтобы он был равен $120^\circ$. Длины $AM=k$ и $BM=l$ — целые числа (одно из них может быть равно нулю). На рисунке 2 $k=1$, $l=2$. Тогда $AB=\sqrt{k^2+kl+l^2}$, а площад ромба равна $\frac{\sqrt{3}}{2}(k^2+kl+l^2)$.

Мы доказем, что число цветов, участвующих в раскраске, равно отношению площади $ABCD$ к площади одного окружного квадрата (случай (a)) или шестиугольника (случай (6)) и, тем самым, равно:

в случае квадратов $k^2+l^2$,

в случае шестиугольников $k^2+kl+l^2$

(так как площад одного шестиугольника равна $\frac{\sqrt{3}}{2}$).

Это сразу следует из следующей леммы.

Основная лемма. Часть $ABCD$, закрашенная какдым цветом, участвующим в раскраске, либо представляет собой один квадрат (в случае (a)), соответствующего шестиугольнику (в случае (6)), либо состоит из кусочков (для красного цвета — четырех, для других цветов — двух), из которых можно сложить такой же квадрат или соответственно шестиугольник.

Доказательство леммы несложно, и мы предлагаем читателю проведи

44

Рис. 4. Плоскость заполнена одинаковыми фигурами площади 13 квадрата. Попробуйте найти «элементарный» кусок заполненной таким образом плоскости и склейть из него тор, как мы это сделали с квадратом.

Указание. Надо выбрать 13 фигуры, из них сложить многоугольник, который не будет квадратом, но тем не менее легко склейся в тор. Делать это надо с листом клеетой бумаги.

Это самостояльно. Заметим только, что раскраска всех квадратов (ромбов) жирной сетки одинаковова, то есть если вырезать квадрат (ромб) $ABCD$ из плоскости и наложить его, скажем, на соседний квадрат (ромб), то часть $ABCD$, закрашенная любым цветом, точно совместится с частью соседнего квадрата (ромба), закрашенной тем же цветом.

Существует другой способ изложить это доказательство, более красивый, но требующий некоторой работы воображения. Ограничимся сначала случаем квадратной сетки. Выражем из плоскости квадрат $ABCD$ и склейм из него трубку — цилиндр, раскрашенной стороны снаружи, совместимыми из сторон $AB$ и $DC$. Эта трубка ограничена двумя окружностями, полученными из сторон $AB$ и $DC$. Склейм эти окружности друг с другом (совместив точку $A=D$ с точкой $B=C$). Бумажную трубку придется для этого сплошить, но мы все равно считать все ее окрашенную поверхность за единое целое, не разделенное на части сгибами. Площадь поверхности полученной фигуры равна $k^2+l^2$, а часть ее, закрашенная любым из цветов раскраски, — квадратик размером $1 \times 1$. Мы вам советем все это практическими проделать с квадратным листом бумаги, раскраив его пятую или большим числом цветов.

В случае шестиугольников мы приdem к аналогичному результату, если таким же образом склейм прямогольник, имеющий одну сторону, общую с ромбом $ABCD$, а другую, равную высоте ромба.

Можно заполнить плоскость и другими равными фигурами, в которых площади, закрашенные разными цветами, равны. Например, в решении задачи (a), присланном из Киева (пер. Белинского 8, кв. 32, фамилия автора не указана), предлагается заполнить плоскость фигурами, составленными из двух квадратов со стороны $k$ и $l$. Скажем, для $k=2$ и $l=3$ (13 цветов) фигура будет такой, как на рисунке 4.

II. Тепер пусть нам дано число $m=k^2+l^2$ или $n=k^2+kl+l^2$. Покажем, что плоскость можно заполнить в соответствии с условиям квадратами $m$ цветов или шестиугольниками $n$ цветов.

Заполним плоскость равными квадратами или правильными шестиугольниками и начнем их раскраивать следующим образом.

Закрасим один из них красным. Отсчитаем от него $k$ квадратков (шестиугольников) в одну сторону, потом повернем на $90^\circ$ для квадратов и на $60^\circ$ для шестиугольников и отчитаем $l$ квадратков (шестиугольников) в новом направлении, и тот квадратик (шестиугольник), в котором мы приdem, тоже закрасим красным. На отрезке, соединяющим центры двух красных квадратков (шестиугольников), как на стороне, построим квадрат (a) или правильный треугольник (6). Пристраивая к нему равные квадраты (правильные треугольники), мы получим центры всех квадратов (шестиугольников), которые надо закрасить красным; сдвигая параллельно всю сою

45

Купность красных квадратов (шестиугольников), мы будем получить каждый раз новую совокупность незакрашенных квадратов (шестиугольников) и закрашивать ее новым цветом, пока не закрасим всю плоскость. По доказанному выше числу цветов будет равно $k^2+l^2$ в случае (a) и $k^2+kl+l^2$ в случае (б).

III. Какие же натуральные числа представимы в виде $k^2+l^2$ или $k^2+kl+l^2$? Чтоы выписать первые несколько таких чисел, удобно составить две таблицы: таблицу 1 — для $k^2+l^2$, таблицу 2 — для $k^2+kl+l^2$.

Числа ниже диагонали повторяют уже написанные, и их писать не нужно. Некоторые числа входят в таблицу дважды; соответствующие клетки выделены. Это значит, что при таком числе цветов имеются два существенно различных способа заполнения плоскости. Теперь уже легко найти выписать эти числа в порядке возрастания.

Первая таблица: 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, …
Вторая таблица: 1, 3, 4, 7, 9, 12, 13, 16, 19, 21, 25, 27, 28, …

Пусть мы уже выписали эти числа до какого-то места и ищем следующее по величины число.

Красные линии, проведенные на первой таблице, помогают это сделать. Чтобы обсянить, как они проведены, заметим, что в первой таблице каждое число равно квадрату расстояния от центра той клетки, в которой оно стоит до точки 0 в левом верхнем углу (за единицу длины принимаем сторону клетки). Поэтому, если проведение несколько окружностей с центром 0, то они разобут наши числа (то есть центры клеток, в которых они стоит) на группы в порядке возрастания. Если попытаться proveсти от руки аналогичные линии во второй таблице, то может показаться, что они прямы. Но это, конечно, не так. На самом деле это графики соответствуют вида

$$k^2+kl+l^2=c=\text{const}$$

в системе координат с началом 0 и осями, идущими: ось $k$ — вправо, ось $l$ — вниз. Перейдя к другой паре переменных: $x=k+l$, $y=k-l$, можно увидеть, что это эллипсы, вытянутые в направлении оси $y^*$).

В определенном смысле мы получили ответ, но, быть может, его можно упростить. Например, если в какой-то другой задаче мы получим ответ: все числа вида $k^2+l^2+m^2+n^2$, две $k$, $l$, $m$, $n$ целые, то его можно будет переписать так: любое целое неотрицательное число, поскольку все натуральные числа представимы в таком виде. Можно быть, и в нашу последовательность

*) Те, кто читал книжку Н. Б. Васильева и В. Л. Гутенмахера «Прямы и кривы», конечно, заметили, что красные линии — это линни уровня функций $k^2+l^2$ и $k^2+kl+l^2$ на плоскости $(k, l)$.

46

ность входят все натуральные числа, начиная с некоторого места? Чтоы доказать, что это не так, можно воспользоваться системой пунктных линей.

Проведем в первой таблице красную окружность с центром 0 радиуса $n$. Центры всех клеток, в которых стоит числа, меньше или равны $n^2$, лежат внутри или на гранисе сектора этой окружности с центральным углом $45^\circ$. Поэтому все такие клетки лежат внутри фигуры, получаются из этого сектора, если к нему добавить окаймляющую его полосу ширины 1. Площадь этой фигуры меньше $\frac{\pi n^2}{8} + 3n + 4$.

Отсюда среди первых $n^2$ натуральных чисел $\frac{\pi n^2}{8} + 3n + 4$, представимых в виде $k^2 + l^2$. При больших $n$ второе число первого и составляет от него примерно $\frac{\pi}{8}$. В действительности, так как неокторые числа в таблице равны, чисел вида $k^2 + l^2$ еще меньше. Легко убедиться в том, что доля чисел, представимых в виде $k^2 + kl + l^2$, еще меньше.

M4. Дан отрезок $AB$. Найти на плоскости множества точки $C$ таких, что в треугольнике $ABC$ медиана, проведенная из вершины $A$, равна высоте, проведенной из вершины $B$.

Решение

Редакция получила много писем с решениями этой задачи, но почти все они неполные. Многие читатели забили, что при отыскании геометрического места точек (ГМТ) надо обозначенно убедиться в двух вещи: 1) все точки найденного множества удовлетворяют условиям; 2) все точки, удовлетворющие условиям, принадлежат найденному множеству. Требование 1) многое как раз и не учили. Мы приведем два решения задачи: одно — чисто геометрическое, второе — с помощью метода координат.

Первое решение. Начнем с 2). Пусть нам дан отрезок $AB$ и путь $C$ — точка, удовлетворяющая условиям, $AD$ — медиана треугольника $ABC$. Достроим треугольник до параллелограмма, продолжив медиану $AD$ до точки $E$ так, что $AD=DE$. Здесь возможно два случая: угол $AEB$ острый или тупой.

(a) Пусть угол $AEB$ острый (рис. 5, a). Проведем $BF \perp AC$, $AK \parallel BF$, тогда в прямогольном треугольнике $AEK$ катет $AK$ равен половине гипotenузы $AE$, поэтому $\angle AEB=30^\circ$.

47

(6) Пусть угол AEB типой (рис. 5, 6). Проведяя BF ⊥ AC, AK || BF, получим аналогично случаю (a), что ∠AEK=30°, поэтому ∠AEB=150° (отличие от случая (a) в том, что теперь точки K и B лежат по разные стороны от E).

Итак, если C — искомая точка, то отрезок AB виден из точки E под углом в 30° или в 150°. Как известно, все такие точки E находится на двух окружности O₁ и O₂, которые делятся хордой AB на дуги в 300° и 60° (рис. 6, a), и, следовательно, все точки C — на таких же окружности O’₁ и O’₂, полученных из O₁ и O₂ параллельным переносом на отрезок l=AB в направлении от B к A (рис. 6, 6).

Теперь доказем, что любая точка M окружностей O’₁ и O’₂ принадлежит искомому множество точек. Пусть M — произвольная точка одной из этих окружностей; тогда проведя MK=AB, MK||AB, мы получим точку K на одной из окружностей O₁ или O₂ (рис. 7, a, 6). На рисунке 7, a’ BF ⊥ MA, AL||BF, AL=BF, тогда (из ΔAKL) AL=1/2 AK, т. е. точка M удовлетворяет условиям. Аналогично на рисунке 7, 6 BF ⊥ MA, AL=BF, AL||BF, ∠AKB=150°, ∠AKL=180°−∠AKB=30°, т. е. AL=1/2 AK, и точка M также удовлетворяет условиям. Итак, все точки O’₁ и O’₂, кроме точки N и A, удовлетворяют условиям.

Отметим, что многие читатели, решавшие задачу геометриски, получали в ответе части окружностей O’₁ и O’₂. (Рисунок 8, a получился, например, у В. Машанов из г. Гродно, рисунок 8, 6 — у С. Иваненко из г. Федосии и рисунок 8, в у А. А ля е в а из Пензенской обл.) Правильное решение (хотя и немного отличное от приведенного здесь) прислада Л. Столяров из г. Пензы.

Второе решение. (Небольшое упрощение решения, прислаанного А. Гришковым из г. Томска.) Введем прямогольную систему координат с началом в точке A, пусть точка B имеет координаты (2; 0), а искомая точка C — координаты (x; y). Пусть AF — медиана в треугольнике ABC, BK ⊥ AC (рис. 9). Легко показать, что точка F имеет координаты (x+2/2; y/2). Тогда AF²=(x+2/2)²+y²/4. По условиям BK²=AF², поэтому

48

Рис. 8, а. Рис. 8, б. Рис. 8, с.

из подобия треугольников АКВ и АCD следует, что $\frac{BK^2}{AK^2} = \frac{CD^2}{AD^2}$ или
$$\frac{\left(\frac{x+2}{2}\right)^2 + \frac{y^2}{4}}{4 - \left[\left(\frac{x+2}{2}\right)^2 + \frac{y^2}{4}\right]} = \frac{y^2}{x^2}.$$

Преобразовывая (1), получим
$$y^4 + (2x^2 + 4x - 12)y^2 + (2x + x^2)^2 = 0.$$

Это и есть уравнение, связывающее координаты искомых точек. Некоторые читатели писали дальше, что оно определяет кривую четвертого порядка, нарисовать которого довольно трудно.

На самом деле оказывается, что левая часть уравнения (2) раскладывается на множители:
$$[(x+1)^2 + (y+\sqrt{3})^2 - 4] [(x+1)^2 + (y-\sqrt{3})^2 - 4] = 0.$$

Рис. 9. Рис. 10.

49

Догадаться об этом можно, например, так.

Введем обозначение: $y^2 = z$. Тогда (2) — квадратное уравнение относительно $z$. Разложим его левую часть на множители. Для этого найдем корни (2).

$$z_{1,2} = \frac{12 - 2x^2 - 4x \pm \sqrt{(12 - 2x^2 - 4x)^2 - 4(2x + x^2)^2}}{2} =$$

$$= \frac{12 - 2x^2 - 4x \pm \sqrt{48(3 - x^2 - 2x)}}{2} = 6 - x^2 - 2x \pm 2\sqrt{3(3 - x^2 - 2x)} =$$

$$= (\sqrt{3 - x^2 - 2x} \pm \sqrt{3})^2.$$

Уравнение (2) можно представить теперь в таком виде:

$$\left| z - (\sqrt{3 - x^2 - 2x} + \sqrt{3}) \right| \left| z - \sqrt{3 - x^2 - 2x} - \sqrt{3} \right|^2 = 0$$

или

$$\left| y^2 - (\sqrt{4 - (x + 1)^2} + \sqrt{3}) \right| \left| y^2 - (\sqrt{4 - (x + 1)^2} - \sqrt{3}) \right|^2 = 0.$$

(см рисунок 10, где одно из этих множества — красное, а другое — зеленное).

Преобразуем (4) дальше:

$$\left| y - \sqrt{4 - (x + 1)^2} + \sqrt{3} \right| \left| y + \sqrt{4 - (x + 1)^2} - \sqrt{3} \right| [\dots] [\dots] = 0;$$

отсюда получается (3)*.

Девятиклассник П. Криксунов из г. Киева и некоторые другие читатели, писавшие нам решения этой задачи, заметили, что аналогично можно решить и такую более общую задачу: найти множество точек $C$ таких, что в треугольнике $ABC$ относение медians $AD$ к высоте $BF$ равно данному числу $k$ (годится любой из двух описанных выше способов решения).

M5. В множестве $E$, состоящем из $n$ элементов, выделены $m$ различных подмножества (отличных от самого $E$) так, что для каждой двух элементов из $E$ найдетсяровно одно из данных подмножества, в котором входят оба эти элемента.

Доказать, что $m \geq n$. В каких случаях возможно решение?

Решение

По письмам читателей можно судить о том, что эта задача чрезвычайно трудная, но интересная. Собственно говоря, здесь мы имеем дело с двумя задачи: 1) доказать, что $m \geq n$, 2) в каких случаях возможно решение?

Что касается первой задачи, то ее решил полностью только $A$. Существ из г. Ленинграда. Его доказательство описется на одну из основных теорем линейной алгебры, утверждающего, что если $n$-векторов больше чем $n$, то они линейно зависитмы.

Для тех, кто знаком с этим понятями, будет интересно придумать такое доказательство. Что касется второй задачи, то ее показано, да это и не удивительно, так как ниже будет показано, что она связается к одной известной, но нерешенной математической probleme.

Для удобства изложения некоторые читатели предложили другие формулировки задачи. Вот две из них.

*) Уравнение $(x - a)^2 + (y - b)^2 = c^2$ определяет окружность с центром в точке $(a; b)$ радиуса $c$ (см., например, И. М. Гельфанд, Е. Г. Глаголева, А. А. Кирр и лов, Метод координат, «Наука», 1968).

50

Рис. 11.

a) Учащие одной школе часто собираются группами и ходят есть мороженое. После такого посещения они сорятся настолько, что никакие две из них после этого вместе мороженое не едят. К концу года выяснили, что в дальнейшем они могут ходить в кафе-mороженое только подиночке. Доказать, что если посещенный было к этому времени больше 1, то оно не меньше числа учащихся в школе.

6. Пусть дано $n$ точек. Через каждые две точки проведенаровно одна прямая, причем на каждой прямой лежит не более чем $(n-1)$ точек. Нужно доказать, что число прямых не меньше $n$.

Является ли эти задачи эквивалентными первоначальной?

Во всяком случае, удобно, размышляя над этой задачей, представлять себе элементы «точками», а подножества — «линиями», прохождения через эти точки и делать для себя рисунки типа наших рисунков 11 и 12. (Не добиться, чтобы все линии были прямыми, вообще говоря, нельзя; как показывает задача М36, рисунок 12 нельзя исправить так, чтобы и красная линия была прямой, так что задача 6) не эквивалентна исходной.)

Далее мы излагаем решение задачи, следуя указанием самого автора задачи Н. Бурбаки*), и также для удобства переписываем условия задачи.

Дано $n$ различных элементов и имеет система $m$ множества, составленных из этих элементов, причем:

1. никакое множество нашей системы не содержит сразу всех элементов;
2. каждые два из данных $n$ элементов встречаются в одном из множества системы;
3. если два элемента встречаются в одном из множества, то они не встречаются вместе ни в одном из остальных множества системы.

Докажем, что $m \geq n$.

Приведем какой-нибудь пример такого размещения элементов. Пусть $n=5$ и имеются элементы: $a, b, c, d, e$. Составим такую систему множества из этих элементов;

$(a, b), (a, c, e,), (b, e), (b, c), (b, d), (a, d), (d, e), (c, d)$.

Очевидно, она удовлетворяет условиям 1), 2), 3). Здесть $m=8$, и кстати $8 \geq 5$.

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

Доказательство. Заметим, что $n>2$ и что достаточно доказать неравенство $m \geq n$ для системы множества, содержащих не менее двух элементов.

1. Система состоит не менее чем из двух множества, то в силу условия 2) это множество содержащего бы сразу все элементы, что противоречит условиям 1).

*) См. Н. Бурбаки, Теория множества, «Мир», М., 1965, стр. 220.

51

2. Каждый элемент входит не менее чем в два множества системы. Если бы элемент входил только в одно множество, то в силу 2) оно должно быть содержать все $n$ элементов, что противоречит 1).

3. Один и тот же элемент не может входить сразу во все множества системы. Пусть какой-то элемент, называем его $x$, входит во все множества системы. Тогда в силу условия 3) никакие два множества не содержат одинаковых элементов, за исключением элемента $x$. Следовательно, никакие два элемента, отличные от $x$, не встречаются ни в одном из множества, но это противоречит 2).

4. Сопоставим каждому элементу число множества системы, в которых он входит, т. е. считаем, сколько раз он повторяется в этой системе. В примере элементу $a$ сопоставляется число 3, элементу $b$ — 4 и т. д.

Какому множеству системы сопоставим число элементов, которые оно содержит. В примере первого множеству сопоставляется число 2, второму — 3 и т. д.

Сумма всех чисел, соответствующих элементам, равна сумме всех чисел, соответствующих множествам. В примере $3+4+3+4=2+3+2+2+2+2+2+2=17$.

В самом деле, если считать два элемента разными, когда они входят в разные множества, то обе суммы числу элементов всех множества системы.

5. Обозначия. Возьмем один из тех элементов, которые соответствуют наименшеее число, т. е. который входит в наименшеее число множества системы. В примере мы можем взять либо $a$, либо $c$, либо $e$; возьмем $a$. Обозначим этот элемент через $a_n$, а число множества, в котором он входит, через $k_n$. В примере $a_5=a$, $k_5=3$. В силу пп. 2 и 3 имеем $2 \leqslant k_n < m$.

Множества, в которых входит $a_n$, обозначим в некотором порядке через $A_1$, $A_2$, …, $A_{k_n}$, а остальные через $A_{k_n+1}$, …, $A_m$. В примере $A_1=(a, b)$, $A_2=(a, c, e)$, $A_3=(a, d)$, $A_4=(b, e)$, …, $A_8=(c, d)$.

Рассмотрим первые $k_n$ множества $A_1$, $A_2$, …, $A_{k_n}$. Рассуjdая так же, как в п. 3, мы видим, что никакие два из них не содержат одинаковых элементов, за исключением $\dot{a}_n$. Следовательно, мы можем взять по одному элементу каждого из этих множества и обозначить их соответственно через $a_1$, $a_2$, …, $a_{k_n}$. Остальные элементы обозначим в некотором порядке через $a_{k_n+1}$, $a_{k_n+2}$, …, $a_n$. В примере $a_1=b$, $a_2=c$, $a_3=d$, $a_4=e$; тогда $A_1=(a_1, a_5)$, $A_2=(a_2, a_4, a_5)$, $A_3=(a_3, a_5)$, $A_4=(a_1, a_4)$, $A_5=(a_1, a_2)$, $A_6=(a_1, a_3)$, $A_7=(a_3, a_4)$, $A_8=(a_2, a_3)$.

Теперь обозначим числа, соответствующие элементам $a_1$, $a_2$, …, $a_{k_n}$, …, $a_{n-1}$ в том же порядке через $k_1$, $k_2$, …, $k_{n-1}$. Например, что элемент $a_n$ соответствует число $k_n$, причем оно наименшеее из всех чисел $k_1$, $k_2$, …, $k_{n-1}$, $k_n$.

Наконец, обозначим числа, соответствующие множествам $A_1$, $A_2$, …, $A_m$ в том же порядке через $s_1$, $s_2$, …, $s_{k_n}$, …, $s_m$.

Обратим еще раз внимание на то, как мы пронумервали элементы и множества.

Во-первых, $k_n$ наименшеее из чисел $k_1, k_2, ..., k_{n-1}$.

Во-вторых, $k_n$ — номер последнего из множества, в которых входит элемент $a_n$, и, таким образом, элемент $a_n$ не входит в множества $A_{k_n+1}$, …, $A_m$.

Множество $A_i$ содержит элемент $a_i$, но не содержит элементов $a_j$, если $1 \leqslant i \leqslant k_n$, $1 \leqslant j \leqslant k_n$ и $i \neq j$. Кроме того, согласно п. 4, $k_1 + \dots + k_n = s_1 + \dots + s_m$.

52

6. Если элемент $a_i$ не принадлежит какому-нибудь множеству $A_j$, то $k_i \geqslant s_j$. Действительно, пусть множество $A_j$ не содержит элемента $a_i$ и состоит из $s_j$ различных элементов. тогда элемент $a_i$ должен встречаться с каждым из этих элементов в каком-нибудь из остальных множества системы. С другой стороны, никакие два из этих элементов не могут ни разу встречаться в этих множествах, так как они уже встречались в $A_j$. Следовательно, число множества, в которых элемент $a_i$ не меньше $s_j$.

7. Рассмотрим первый $k_n$ множество $A_1, A_2, \dots, A_{k_n}$ и первый $k_n$ элементов $a_1, a_2, \dots, a_{k_n}$. Они выбраны таким образом, что каждое множество $A_i$ содержит элемент $a_i$ с тем же номером, но не содержит элементов с другими номерами, тогда, согласно п. 6, $s_1 \leqslant k_2, s_2 \leqslant k_1$, если $k_n = 2$ и

$$\begin{align*} s_1 &\leqslant k_2, \quad s_2 \leqslant k_1, \quad \dots, s_{k_n} \leqslant k_1, \\ s_1 &\leqslant k_{k_n}, \quad s_2 \leqslant k_{k_n}, \quad \dots, s_{k_n} \leqslant k_{k_n-1}, \end{align*}$$

если $k_n > 2$.

В примере $k_n = 3$ и

$$\begin{align*} 2 &= s_1 \leqslant k_2 = 3, \quad 3 &= s_2 \leqslant k_1 = 4, \quad 3 &= s_3 \leqslant k_1 = 4, \\ 2 &= s_1 \leqslant k_3 = 4, \quad 3 &= s_2 \leqslant k_3 = 4, \quad 3 &= s_3 \leqslant k_2 = 3. \end{align*}$$

8. Складывая все неравенства, мы получаем, что

$$(k_n - 1)(s_1 + s_2 + \dots + s_{k_n}) \leqslant (k_n - 1)(k_1 + \dots + k_{k_n})$$

или

$$s_1 + s_2 + \dots + s_{k_n} \leqslant k_1 + \dots + k_{n}.$$

9. Телерь мы можем доказать требуемое в задание неравенство $m \geqslant n$. Допустим, что $m < n$. Сравним две суммы

$$S = (s_1 + s_2 + \dots + s_{k_n}) + s_{k_n+1} + \dots + s_m$$

и

$$K = (k_1 + k_2 + \dots + k_n) + k_{k_n+1} + \dots + k_n.$$

Заметим, что мы так перенumerовали множество, что элемент $a_n$ не принадлежит множеством $A_{k_n+1}, \dots, A_m$; значит, $s_{k_n+1} \leqslant k_n, \dots, s_m \leqslant k_n$ и тем более $s_{k_n+1} \leqslant k_{k_n+1}, \dots, s_m \leqslant k_m$, так как $k_n$ — наименьшее из всех чисел $k_i$. В таком случае, поскольку $m < n$, получаем: $k_{k_n+1} + \dots + k_n > s_{k_n+1} + \dots + s_m$, но тогда $S < K$, а это противоречит п. 4.

Доказательство того, что $m \geqslant n$, окончено.

10. Попробем выяснить, в каких случаях возможно равенство. Если $m = n$, то из п. 8, 9 и 4 следует:

$$k_1 + \dots + k_{k_n} + \dots + k_n = s_1 + \dots + s_{k_n} + \dots + s_n.$$

Очевидно, для этого необходимо, чтобы выполнялось равенство

$$k_1 + \dots + k_{k_n} = s_1 + \dots + s_{k_n}$$

и все неравенства из п. 8 приведились в равенства. Поскольку $k_n$ наименьшее из чисел $k_i$, мы имеем

$$s_{k_n+1} = \dots = s_n = k_{k_n+1} + \dots + k_n.$$

Далее рассмотрим два случая.

(a) $k_n = 2$. В этом случае, как нетрудно видеть, возможно такая система множества (рис. 9): $(a_n, a_1), (a_n, a_2, a_3, \dots, a_{n-1}), (a_1, a_2), (a_1, a_3), \dots, (a_1, a_{n-1})$. При любом $n$ она удовлетворяет условиям задачи.

(b) $k_n > 2$. В этом случае получаем, что все неравенства п. 7 должны об-

53

рапится в равенства. Сравнивая все эти равенства, получаем, что $s_1=s_2=\dots=s_{k_n}=k_1=k_2=\dots=k_{k_n}$.

И так же, как для случая (a): $s_{k_n+1}=\dots=s_n=k_{k_n+1}=\dots=k_{n-1}=k_n$.
Очевидно, что одно из чисел $s_1, s_2, \dots, s_{k_n}$ не более одного из чисел $k_{k_n+1},\dots,k_{n-1}$ и, следовательно, $s_1=s_2=\dots=s_n=k_1=k_2=\dots=k_n=l>2$.

В итоге мы получаем, что в этом случае выполняется такое условие:

4. какое множество содержитровно $l$ различных элементов и какый элемент входитровно в $l$ различных множеств.

Для этого необходимо, чтобы $n=l(l-1)+1$. Действительно, рассмотрим какой-нибудь элемент $x$. Он должен входитьровно в $l$ множество, следовательно, все эти множества содержат все $n$ элементов так, как $x$ должен встречаться со всеми элементами. Кроме того, они не могут содержать одинаковые элементы, так как все они содержат элемент $x$. Отсюда получаем требуемое равенство.

Для $l=3$, т. е. $n=7$, легко построить нужную систему множества (рис. 10). Но вопрос о том, для каких $n$ вида $l^2-l+1$ у множества из $n$ элементов существует система подмножества, удовлетворяющая условием 1), 2), 3) и 4), оказывается очень сложным.

Такая система имеет специальное название: конечная проективная плоскость порядка $l-1$. (На рис. 12 изображена проективная плоскость порядка 2, состоящая из 7 точек и 7 прямых.) Легко доказать, что для любой конечной проективной плоскости выполняется и такое свойство, «двойственное» свойству 2):

5. Любые два множества из нашей системы имеют общий элемент (очевидно, только один); другие словами, какые две прямы пересекаются в одной точке.

Покажем, как построить конечную проективную плоскость порядка $p$ (с $n=p^2-p+1$), где $p$ — простое число. Для этого нужно использовать «числа» из $p$-арфметики (см. статью «Сравнения по модулю и арфметике остатков», «Квант» № 5, стр. 27—33) — arфметики остатков по модулю $p$. В такой.arфметике, если $p$ — простое, можно делить любое «число» на любое другое, отличное от нуля. Изовем точкой тройку «число» $(x_1, x_2, x_3)$, рассматриваемых с точностью до пропорциональности (т. е. тройки $(x_1, x_2, x_3)$ и $(kx_1, kx_2, kx_3)$ определяют одну и ту же точку). Договоримся тройку $(0, 0, 0)$ не считать точкой.

Прямая задается тройкой чисел $(a_1, a_2, a_3)$ (кроме тройки $(0, 0, 0)$), рассматриваемых с точностью до пропорциональности. Точка $(x_1, x_2, x_3)$ принимает прямой прямой $(a_1, a_2, a_3)$ в том и только в том случае, когда $a_1x_1+a_2x_2+a_3x_3=0$.

Проверьте, что для таких определенных прямых и точек выполнен все условия 1)—5). Убедитесь, что для $p=2$ получается как раз тот пример проективной плоскости порядка 2, который изобран на рисунке 12.

Аналогично можно доказать, что существует проективная плоскость порядка $p^k$, где $p$ — простое, $k$ — любое натуральное. Доказано, что проективных плоскостей порядка $N$ не существует для бесконечного количества $N$ (в частности, для $N=6$, $N=14$). Но уже для $N=10$ неизвестно, существует ли проективная плоскость порядка $N$ или нет: просто перебрать все возможные комбинации не может ни одна вычислительная машина.

О теории конечных проективных плоскостей и связанных с ними комбинаторов задач можно прочесть в книге Г. Дж. Райзер «Комбинаторная математика» («Мир», 1966, серия «Библиотека сборника «Matematika»»).

А. Тоом, Ж. Раббот, В. Гутенахер