В множестве $E$, состоящем из $n$ элементов, выделены $m$ различных подмножеств (отличных от самого $E$) так, что для каждых двух элементов $E$ найдётся ровно одно из данных подмножеств, в которое входят оба эти элемента.
Докажите, что $m \geq n$. В каких случаях возможно равенство?
По письмам читателей можно судить о том, что эта задача чрезвычайно трудная, но интересная.
Собственно говоря, здесь мы имеем дело с двумя задачами: 1) доказать, что $m \ge n$, 2) в каких случаях возможно равенство?
Что касается первой задачи, то её решил полностью только А. Суслин из г. Ленинграда.
Его доказательство опирается на одну из основных теорем линейной алгебры,
утверждающую, что если число $n$-векторов больше чем $n$, то они линейно зависимы.
Для тех, кто знаком с этими понятиями, будет интересно придумать такое доказательство.
Что касается второй задачи, то её пока полностью никто не решил, да это и не удивительно,
так как ниже будет показано, что она сводится к одной известной,
но нерешённой математической проблеме.
Для удобства изложения некоторые читатели предложили другие формулировки задачи.
Вот две из них.
Учащиеся одной школы часто собираются группами и ходят есть мороженое.
После такого посещения они ссорятся настолько, что никакие двое из них после этого
вместе мороженое не едят. К концу года выяснилось, что в дальнейшем они могут ходить
в кафе-мороженое только поодиночке. Доказать, что если число посещений
было к этому времени больше 1, то оно не меньше числа учащихся в школе.
Пусть дано $n$ точек. Через каждые две точки проведена ровно одна прямая,
причём на каждой прямой лежит не более чем $n-1$ точек. Нужно доказать,
что число прямых не меньше $n$.
Являются ли эти задачи эквивалентными первоначальной?
Во всяком случае, удобно, размышляя над этой задачей, представлять себе элементы «точками»,
а подмножества — «линиями», проходящими через эти точки и делать для себя рисунки
типа наших рисунков 11 и 12. (Но добиться, чтобы все линии были прямыми,
вообще говоря, нельзя; как показывает задача М36, рисунок 12 нельзя исправить так,
чтобы и красная линия была прямой, так что задача б) не эквивалентна исходной.)
Рис. 11Рис. 12
Далее мы излагаем решение задачи, следуя указаниям самого автора задачи
Н. Бурбаки,
и также для удобства переписываем условие задачи.
Дано $n$ различных элементов и имеется система $m$ множеств, составленных из этих элементов,
причём:
никакое множество нашей системы не содержит сразу всех элементов;
каждые два из данных $n$ элементов встречаются в одном из множеств системы;
если два элемента встретились в одном из множеств,
то они не встречаются вместе ни в одном из остальных множеств системы.
Докажем, что $m\ge 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\ge 5$.
Для того чтобы доказательство было более наглядным, мы будем иногда ссылаться на этот пример.
Доказательство. Заметим, что $n\gt 2$ и что достаточно доказать неравенство
$m\ge n$ для системы множеств, содержащих не менее двух элементов.
1.Система состоит не менее чем из двух множеств.
Если бы система состояла из одного множества, то в силу условия 2)
это множество содержало бы сразу все элементы, что противоречит условию 1).
2.Каждый элемент входит не менее чем в два множества системы.
Если бы элемент входил только в одно множество, то в силу 2)
оно должно было бы содержать все $n$ элементов, что противоречит 1).
3.Один и тот же элемент не может входить сразу во все множества системы.
Пусть какой-то элемент, назовём его $x$, входит во все множества системы.
Тогда в силу условия 3) никакие два множества не содержат одинаковых элементов,
за исключением элемента $x$. Следовательно, никакие два элемента, отличные от $x$,
не встречаются ни в одном из множеств, но это противоречит 2).
4. Сопоставим каждому элементу число множеств системы, в которые он входит,
т. е. считаем, сколько раз он повторяется в этой системе.
В примере элементу $a$ сопоставляется число 3, элементу $b$ — 4 и т. д.
Каждому множеству системы сопоставим число элементов, которые оно содержит.
В примере первому множеству сопоставляется число 2, второму — 3 и т. д.
Сумма всех чисел, соответствующих элементам, равна сумме всех чисел,
соответствующих множествам. В примере
$3+4+3+4+3=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\le k_n \lt m$.
Множества, в которые входит $a_n$, обозначим в некотором порядке через
$A_1$, $A_2$, $\ldots$, $A_{k_n}$, а остальные через $A_{k_n+1}$, $\ldots$, $A_m$.
В примере $A_1=(a,b)$, $A_2=(a,c,e)$, $A_3=(a,d)$, $A_4=(b,e)$, $\ldots$, $A_8=(c,d)$.
Рассмотрим первые $k_n$ множеств $A_1$, $A_2$, $\ldots$, $A_{k_n}$.
Рассуждая так же, как в п. 3, мы видим, что никакие два из них не содержат одинаковых элементов,
за исключением $a_n$. Следовательно, мы можем взять по одному элементу каждого из этих множеств
и обозначить их соответственно через $a_1$, $a_2$, $\ldots$, $a_{k_n}$.
Остальные элементы обозначим в некотором порядке через
$a_{k_n+1}$, $a_{k_n+2}$, $\ldots$, $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_1=(a_1,a_2)$, $A_7=(a_3,a_4)$, $A_8=(a_2,a_3)$.
Теперь обозначим числа, соответствующие элементам
$a_1$, $a_2$, $\ldots$, $a_{k_n}$, $\ldots$, $a_{n-1}$ в том же порядке через
$k_1$, $k_2$, $\ldots$, $k_{n-1}$.
Напомним, что элементу $a_n$ соответствует число $k_n$, причём оно наименьшее
из всех чисел $k_1$, $k_2$, $\ldots$, $k_{n-1}$, $k_n$.
Наконец, обозначим числа, соответствующие множествам
$A_1$, $A_2$, $\ldots$, $A_m$ в том же порядке через
$s_1$, $s_2$, $\ldots$, $s_{k_n}$, $\ldots$, $s_m$.
Обратим ещё раз внимание на то, как мы пронумеровали элементы и множества.
Во-первых, $k_n$ наименьшее из чисел $k_1$, $k_2$, $\ldots$, $k_{n-1}$.
Во-вторых, $k_n$ — номер последнего из множеств, в которые входит элемент $a_n$,
и, таким образом, элемент $a_n$ не входит в множества
$A_{k_n+1}$, $\ldots$, $A_m$.
Множество $A_i$ содержит элемент $a_i$, но не содержит элементов $a_j$,
если $1\le i\le k_n$, $1\le j\le k_n$ и $i\ne j$.
Кроме того, согласно п. 4, $k_1+\ldots +k_n=s_1+\ldots+s_m$.
6.Если элемент $a_i$ не принадлежит какому-нибудь множеству $A_j$, то $k_i\ge s_j$.
Действительно, пусть множество $A_j$ не содержит элемента $a$ и состоит из $s_j$
различных элементов. Тогда элемент $a_i$ должен встретиться с каждым из этих элементов
в каком-нибудь из остальных множеств системы.
С другой стороны, никакие два из этих элементов не могут ни разу встретиться в этих множествах,
так как они уже встречались в $A_j$. Следовательно, число множеств, в которые входит элемент $a_i$,
не меньше числа $s_j$.
7. Рассмотрим первые $k_n$ множеств $A_1$, $A_2$, $\ldots$, $A_{k_n}$
и первые $k_n$ элементов $a_1$, $a_2$, $\ldots$, $a_{k_n}$. Они выбраны таким образом,
что каждое множество $A_i$ содержит элемент $a_i$ с тем же номером,
но не содержит элементов с другими номерами, тогда, согласно п. 6,
$s_1\le l_2$, $s_2\le k_1$, если $k_n=2$ и $$
\left.
\begin{alignedat}{3}
s_1&\le k_2,&~s_2&\le k_1,&~\ldots,~s_{k_n}&\le k_1,\\
&&&\dots\\
s_1&\le k_{k_n},&~s_2&\le k_{k_n},&~\ldots,~s_{k_n}&\le k_{k_{n-1}},
\end{alignedat}\right\}~\text{если}~k\gt 2.
$$
В примере $k_n=3$ и $$
\left.
\begin{aligned}
2&=s_1\le k_2=3,~3=s_2\le k_1=4,~3=s_3\le k_1=4,\\
2&=s_1\le k_3=4,~3=s_2\le k_3=4,~3=s_3\le k_2=3.
\end{aligned}
\right\}
$$
8. Складывая все неравенства, мы получаем, что $$
(k_n-1)(s_1+s_2+\ldots+s_{k_n})\le (k_n-1)(k_1+\ldots+k_{k_n})
$$
или $$
s_1+s_2+\ldots+s_{k_n}\le k_1+\ldots+k_n
$$
9. Теперь мы можем доказать требуемое в задаче неравенство $m\ge n$.
Допустим, что $m\lt n$.
Сравним две суммы
$$
S=(s_1+s_2+\ldots+s_{k_n})+s_{k_n+1}+\ldots+s_m
$$
и $$
K=(k_1+k_2+\ldots+k_n)+k_{k_n+1}+\ldots+k_n.
$$
Заметим, что мы так перенумеровали множества, что элемент $a_n$ не принадлежит множествам
$A_{k_n+1}$, $\ldots$, $A_m$; значит, $s_{k_n+1}\le k_n$, $\ldots$, $s_m\le k_n$ и тем более
$s_{k_n+1}\le k_{k_n+1}$, $\ldots$, $s_m\le k_m$, так как $k_n$ — наименьшее из всех чисел $k_i$.
В таком случае, поскольку $m\lt n$, получаем:
$$
k_{k_n+1}+\ldots+k_n=s_{k_n+1}+\ldots+s_m,
$$
но тогда $S\lt K$, а это противоречит п. 4.
Доказательство того, что $m\ge n$, окончено.
10. Попробуем выяснить, в каких случаях возможно равенство.
Если $m=n$, то из пп. 8, 9 и 4 следует:
$$
k_1+\ldots+k_{k_n}+\ldots+k_n=s_1+\ldots+s_{k_n}+\ldots+s_n,
$$
Очевидно, для этого необходимо, чтобы выполнялось равенство
$$
k_1+\ldots+k_{k_n}=s_1+\ldots+s_{k_n}
$$
и все неравенства из п. 8 превратились в равенства.
Поскольку $k_n$ наименьшее из чисел $k_i$, мы имеем
$$
s_{k_n+1}=\ldots=s_n=k_{k_n+1}+\ldots+k_n.
$$
Далее рассмотрим два случая.
(а) $k_n=2$. В этом случае, как нетрудно видеть, возможна такая система множеств (рис. 10):
$(a_n, a_1)$, $(a_n, a_2, a_3,\ldots,a_{n-1})$, $(a_1, a_2)$, $(a_1, a_3)$, $\ldots$, $(a_1, a_{n-1})$.
При любом $n$ она удовлетворяет условию задачи.
(б) $k_n\gt2$. В этом случае получаем, что все неравенства п. 7 должны обратиться в равенства.
Сравнивая все эти равенства, получаем, что $s_1=s_2=\ldots=s_{k_n}=k_1=k_2=\ldots=k_{k_n}$.
И так же, как для случая (a):
$s_{k_n+1}=\ldots=s_n=k_{k_n+1}=\ldots=k_{n-1}=k_n$.
Очевидно, что одно из чисел $s_1$, $s_2$, $\ldots$, $s_{k_n}$ не более одного из чисел
$k_{k_n+1}$, $\ldots$, $k_{n-1}$ и, следовательно,
$s_1=s_2=\ldots=s_n=k_1=k_2=\ldots=k_n=l\gt 2$.
В итоге мы получаем, что в этом случае выполняется такое условие:
каждое множество содержит ровно $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):
Любые два множества из нашей системы имеют общий элемент (очевидно, только один);
другими словами, каждые две прямые пересекаются в одной точке.
Покажем, как построить конечную проективную плоскость порядка
$p$ (с $n=p^2-p+1$), где $p$ — простое число. Для этого нужно использовать «числа»
из $p$-арифметики
(см. статью «Сравнения по модулю и арифметика остатков», «Квант» № 5, стр. 27—33) — арифметики остатков по модулю $p$. В такой арифметике, если $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, серия «Библиотека сборника «Математика»).
