\documentclass[11pt]{article}

% корректная обработка переносов, в том числе при поиске и копировании
\defaulthyphenchar=127
\lccode`\-=`\-
\usepackage{cmap}
\newcommand\softhyphen{\char127\relax}
% также в локальную копию файла t2a.cmap внесено изменение:
%  <7F> <002D>   заменено на   <7F> <00AD>

\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{ifthen}

\pagestyle{plain}
\advance\textwidth40mm
\advance\textheight78mm
\advance\voffset-34mm
\advance\hoffset-25mm
\footskip=8mm

%%%%% NEW THEOREMS %%%%%
\newtheorem{thm}{Теорема}
\newtheorem{cor}[thm]{Следствие}
\newtheorem{df}{Определение}
\newtheorem{lm}[thm]{Лемма}
\newtheorem{prop}[thm]{Предложение}

\makeatletter
\renewcommand{\abstractname}{Аннотация}

\newcommand\txt[2]{{#1{\ifthenelse{\equal {#2}{}}{}{ #2}}. }}
\def\example#1.{\txt{\bf Пример}{#1}}
\makeatother

\def\itref#1{{\it (#1)}}

\let\emp\varnothing
\let\emptyset\varnothing
\newcommand\eps\varepsilon
\newcommand\ov\widetilde
\let\ds\displaystyle

\newcommand\eop{\unskip\hfill\penalty150\hfill$\square$\par\smallskip}
\newcommand{\NN}{{\mathbb N}}

\renewcommand\refname{Список литературы}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\Remark#1.{\par\smallskip
\textbf{Замечание\ifx#1\relax\else\ #1\fi.}}


\newcounter{prob}[section]

\makeatletter
\long\def\itemm{%
  \par\medskip\noindent\refstepcounter{prob}%
  \protected@edef\@currentlabel{\thesection.\theprob}%
  \textbf{\thesection.\theprob.} }

\long\def\itemp#1{%
  \par\medskip\noindent%
  \protected@edef\@currentlabel{\thesection.#1}%
  \textbf{\thesection.#1.} }

\long\def\itemmstar{%
  \par\medskip\noindent\refstepcounter{prob}%
  \protected@edef\@currentlabel{\thesection.\theprob}%
  \textbf{\boldmath$\thesection.\theprob^*.$} }
\makeatother

\long\def\stm#1{ {\it #1}\par\smallskip}
\def\newsect{\refstepcounter{section}}

\def\cF{{\mathcal F}}
\def\cG{{\mathcal G}}

\def\cC{{\mathcal C}}
\def\cO{{\mathcal O}}
\def\cN{{\mathcal N}}
\def\cK{{\mathcal K}}
\def\cL{{\mathcal L}}
\def\cS{{\mathcal S}}


\begin{document}

\title{Числа Хелли--Галлаи для конечных и квазиконечных множеств}
\author{И.И.~Богданов, В.Л.~Дольников, Г.Р.~Челноков }
\date{}
\maketitle

\centerline{\Large\bf Решения.}

\vskip\baselineskip

\newsect
\newsect

\itemm \label{first}
\stm{Дан конечный набор отрезков на прямой. Известно, что пересечение всех отрезков
набора пусто. Докажите, что в наборе есть два непересекающихся отрезка.}

Обозначим данные отрезки $[a_1,b_1],\dots,[a_n,b_n]$. Пусть $a_s$ ---
максимальное из всех $a_i$, а $b_t$ "--- минимальное из всех $b_i$ (заметьте,
мы не утверждаем, что $s \neq t$). Если $a_s \le b_t$, то любой отрезок
содержит $a_s$, что противоречит условию. Значит, $a_s > b_t$, поэтому $t \neq
s$, и $s$-й отрезок не пересекается с $t$-м.


\itemm
\stm{Дано дерево (т.е. связный граф без циклов) и конечный набор его поддеревьев
(т.е. подграфов, каждый из которых --- тоже дерево). Известно, что пересечение
всех поддеревьев набора пусто. Докажите, что в наборе есть два непересекающихся
поддерева.}

Заметим, что удаление из дерева любого ребра разбивает его на две компоненты
связности, причём, если ребро не принадлежало некоторому поддереву, то это
поддерево целиком окажется в одной компоненте.

Обозначим поддеревья $G_1, \dots, G_n$. Пусть $k$ --- наибольшее число, такое,
что пересечение поддеревьев $G=G_1 \cap G_2 \cap
\cdots \cap G_k$ непусто (тогда $k<n$ по условию). Пересечение $G$ с поддеревом~$G_{k+1}$ пусто.
Тогда рассмотрим кратчайший путь между подграфами~$G$ и~$G_{k+1}$. Первое ребро
этого пути не принадлежит $G$, а значит, не принадлежит какому-то дереву $G_i$
при $1 \le i \le k$. Если выбросить это ребро, то поддеревья $G_{k+1}$ и $G$
окажутся в разных компонентах, а значит, $G_{k+1}$ и $G_i$ также окажутся в
разных компонентах. Тогда $G_{k+1}$ и $G_i$ не пересекаются.

\itemm
\stm{Рассмотрим конечный набор дуг фиксированной окружности. Пусть любые 1000 из
этих дуг пересекаются. Докажите, что все дуги набора не обязаны пересекаться.}

Построим пример набора, в котором это не выполняется. Разобьем окружность на
1001 дугу, эти дуги назовем
{\em маленькими}. Дополнение каждой из маленьких дуг будем называть
{\em большой} дугой. Нетрудно понять, что набор из всех больших дуг ---
требуемый, ибо пересечение любых 1000 больших дуг непусто, а пересечение всех
больших дуг пусто.

\Remark. Мы считаем, что большие дуги в нашем примере открыты, т.е. не содержат
своих концов. Для получения примера с замкнутыми дугами достаточно чуть-чуть
уменьшить большие дуги.

\itemm \stm{({\sc Теорема Хелли для плоскости}) Пусть $\mathcal C$ --- семейство всех выпуклых множеств на плоскости.
Докажите, что $H({\mathcal C})=3$.}
\label{Helly}

Индукция по числу $n\geq 4$ множеств в семействе $\cG\subset \cC$. Докажем базу
при $n=4$. Рассмотрим выпуклые множества $F_1,F_2,F_3,F_4$. Пусть все эти
множества, кроме~$F_i$, имеют общую точку~$x_i$ ($1\leq i\leq 4$), и применим к
ним следующую лемму.

\begin{lm}[теорема Радона]
Любые 4 точки на плоскости можно разбить на два множества так, что выпуклые
оболочки множеств имеют общую точку.
\end{lm}

\proof Разберите самостоятельно два случая: если точки являются вершинами
выпуклого четырёхугольника, и если нет.
\eop

Итак, пусть, например, выпуклые оболочки множеств $\{x_1,x_2\}$ и $\{x_3,x_4\}$
имеют общую точку~$x$. Тогда $x$ принадлежит множествам $F_3$ и $F_4$,
поскольку в них лежит отрезок $x_1x_2$; аналогично, $x$ принадлежит множествам
$F_1$ и $F_2$. Значит $x$ --- общая точка всех четырех множеств. В остальных
случаях рассуждение аналогично.

\smallskip
Переход. Пусть утверждение доказано для некоторого~$n \ge 4$. Пусть
$\cG=\{F_1,\dots F_{n+1}\}$. Построим новое $n$-элементное семейство из
множеств $F_1'=F_1\cap F_{n+1},\dots,F_n'=F_n\cap F_{n+1}$. По доказанной базе
индукции, любые три множества в новом семействе имеют общую точку. Тогда, по
предположению индукции, все новые множества имеют общую точку. Эта точка
принадлежит всем множествам $F_1,\dots F_{n+1}$.

\itemm \stm{Докажите, что для семейства бесконечных
возрастающих арифметических прогрессий, состоящих из натуральных чисел,
число 2 является числом Хелли.}

Пусть $\cG$ --- конечное семейство прогрессий из условия, любые две из которых
пересекаются. Заметим, что любые две прогрессии из~$\cG$ пересекаются по
бесконечному количеству элементов (а именно, тоже по прогрессии). Значит, можно
считать, что $i$-я прогрессия задаётся условием $x\equiv a_i\pmod {n_i}$ (для
этого достаточно <<забыть>> про некоторый начальный отрезок натурального ряда).

Рассмотрим одну из прогрессий вида $x\equiv a\pmod n$. Это условие равносильно
системе сравнений вида $x\equiv a\pmod {p_j^{\alpha_j}}$, где
$n=p_1^{\alpha_1}\dots p_k^{\alpha_k}$ --- разложение числа~$n$ на простые
множители. Выпишем теперь такую систему для каждой прогрессии из~$\cG$; нам
достаточно показать, что полученная система совместна (т.е. имеет решение).

Заметим, что любые два сравнения из полученной системы совместны (так как они
соответствуют или одной прогрессии, или двум). Далее, пусть в системе есть два
сравнения по модулю степеней одного и того же простого числа (скажем, $x\equiv
a\pmod{p^\alpha}$ и $x\equiv b\pmod {p^\beta}$), причём эти сравнения
совместны. Тогда, если $\alpha\geq \beta$, то второе сравнение следует из
первого, поэтому второе можно выкинуть.

Проделав такие выкидывания, пока это возможно, в конце получим систему
сравнений по модулю степеней различных простых чисел. Она совместна по
китайской теореме об остатках. Это и требовалось доказать.

\Remark. Все $t$-числа Хелли--Галлаи для целочисленных арифметических
прогрессий при $t\geq 2$ бесконечны.

\itemm \stm{Найдите $H(\cO)$, где $\cO$ --- семейство всех окружностей на
плоскости.}

\textbf{Ответ.} $H(\cO)=4$.

Докажем, что 4 является числом Хелли для семейства $\cO$. Рассмотрим конечное
семейство окружностей~$\cG$, такое, что пересечение их всех пусто. Рассмотрим
произвольные две окружности~$O_1,O_2\in\cG$; они пересекаются в не более чем
двух точках; обозначим их~$A$ и~$B$ (если точек пересечения меньше двух, то
рассуждение аналогично). Так как никакая точка не принадлежит всем окружностям,
то, в частности, найдется окружность $O_3\in\cG$, не содержащая точку $A$, и
окружность $O_4\in\cG$, не содержащая точку $B$. Тогда мы нашли 4 окружности
$O_1,O_2,O_3,O_4$, таких, что их пересечение пусто.

Осталось доказать, что 3 не является числом Хелли для~$\cO$. Возьмем 4 точки,
являющиеся вершинами невырожденного невписанного чтырёхугольника. Проведем
через каждые три из них окружность. Мы получили 4 окружности, не имеющих в
совокупности общих точек, но любые три из которых общую точку имеют.


\newsect

\itemm \stm{Пусть $\mathcal S$ --- множество отрезков на фиксированной прямой.

а) Докажите, что 3 является 2-числом Хелли--Галлаи для~$\mathcal S$.

б) Докажите, что $t+1$ является $t$-числом Хелли--Галлаи для~$\mathcal S$.}

Пункт а) является частным случаем б). Поэтому мы приводим только решение пункта
б).

Обозначим рассматриваемые отрезки $[a_1;b_1],\dots,[a_n,b_n]$. Обозначим через
$c_1$ наименьшее из всех $b_i$. Тогда ни один из отрезков не может лежать
строго левее $c_1$, то есть каждый отрезок или содержит $c_1$, или лежит строго
правее неё. Обозначим через $c_2$ наименьшее из всех $b_i$, соответствующих
отрезкам, лежащим правее $c_1$. Из подобных рассуждений получаем теперь, что
каждый отрезок или содержит одну из точек $c_1$, $c_2$, или лежит строго
правее~$c_2$.

Аналогично будем определять $c_3, c_4,\dots$, пока справа от них остаются
отрезки. Пусть процесс оборвался после $k$-го шага. Если $k \le t$, то мы нашли
такие $k$ точек, что каждый отрезок содержит хотя бы одну из них. Пусть теперь
$k \ge t+1$. Тогда мы нашли $t+1$ попарно непересекающийся отрезок (а именно
--- те отрезки, правыми концами которых являются точки $c_1, c_2,\dots ,c_{t+1}$). Эти
$t+1$ отрезок, очевидно, не имеют $t$-трансверсали.

Итак, либо все семейство имеет $t$-трансверсаль, либо найдутся $t+1$ отрезок,
не имеющие $t$-трансверсали. Это и означает, что $t+1$ является числом
Хелли-Галлаи для отрезков на прямой, т.е. $HG_t(\cS)\leq t+1$. Пример,
показывающий, что $HG_t(\cS)>t$, очевиден: достаточно взять $t+1$
непересекающийся отрезок.

\itemm \stm{а) Постройте пример семейства множеств~$\cF$, для которого $H(\cF)=2$, но
$HG_2(\cF)\geq 1000$.

б) Докажите, что существует такое семейство множеств~$\cF$, для которого
$H(\cF)=2$, но $HG_2(\cF)=\infty$.}

а) Положим $k=500$. Наше семейство будет состоять из $2k+1$ множеств $A_1, A_2,
\dots , A_{2k+1}$ (все индексы рассматриваются по модулю $2k+1$, т.е.
$A_{i+2k+1}=A_i$), которые строятся следующим образом. Сначала каждому
подмножества индексов $S \subset
\{1,2,\dots, 2k+1\}$, не содержащего двух индексов с разностью~1
(в частности, не содержащему одновременно $1$ и $2k+1$), сопоставим
элемент $x_S$ (элементы, сопоставленные разным подмножествам, должны быть
различными). Теперь включим в~$A_k$ все элементы~$x_S$, для которых $k\in S$.

Полученное семейство $\cF$ имеет число Хелли 2. В самом деле, пусть
подсемейство $\cG \subset \cF$ имеет пустое пересечение. Пусть $\cG=\{A_i: i\in
I\}$; тогда в $I$ есть соседние индексы, ибо иначе $x_I$ лежит во всех
множествах из~$\cG$. Значит, при некотором~$i$ в $\cG$ нашлись множества $A_i$
и $A_{i+1}$, но они сами имеют пустое пересечение.

Наконец, покажем, что любые $2k$ множеств из $\cF$ имеют 2-трансверсаль, а всё
семейство~$\cF$ не имеет.  Если бы $\cF$ имело 2-трансверсаль $\{x_S,x_T\}$, то
одно из множеств~$S,T$ имело бы хотя бы $k+1$ элемент и потому содержало бы два
соседних индекса, что невозможно. С другой стороны, если из~$\cF$ выкинуть,
скажем, $A_{2k+1}$, то можно положить $S=\{1,3,\dots,2k-1\}$ и
$T=\{2,4,\dots,2k\}$; тогда $\{x_S,x_T\}$ --- трансверсаль всех оставшихся
множеств.

Итак, $HG_2(\cF)=2k+1$.

б) Достаточно для каждого натурального $k$ построить семейство $\cF_k$
вышеописанным способом (так, чтобы множества из разных семейств не
пересекалися), а потом взять объединение всех этих семейств.

\itemm \label{convHG} \stm{Докажите, что $HG_2(\cC)=\infty$. (Напомним, что $\cC$ --- семейство всех выпуклых множеств на
плоскости.)}

Достаточно доказать, что $HG_2(\cC) \ge 2k+1 $ при любом $k$. Рассмотрим
окружность с центром~$O$ и впишем в неё правильный $(2k+1)$-угольник с
вершинами $x_1,x_2,\dots x_{2k+1}$ (индексы опять рассматриваются по модулю
$2k+1$). Обозначим через~$A_i$ выпуклую оболочку точек $x_i, x_{i+1},\dots ,
x_{i+k-1}$. Тогда, очевидно, все множества без любого имеют 2-трансверсаль
(например, для множеств $A_1,A_2,\dots , A_{2k}$ трансверсалью является
множество $\{x_k,x_{2k}\}$).

Покажем, что каждая точка плоскости~$T$ принадлежит не более, чем $k$
множествам. Действительно, если луч~$OT$ пересекает отрезок $x_{i-1}x_i$ (не в
точке~$x_{i-1}$), то $T$ может принадлежать лишь множествам
$A_{i-k+1},\dots,A_i$. Значит, у нашего $(2k+1)$-элементного множества нет
2-трансверсали. Это и требовалось доказать.

\itemmstar \stm{Пусть $\mathcal L$ --- множество всех прямых на плоскости.

а) Докажите, что $HG_t({\mathcal L})\leq t^2+1$ при $t\geq 3$.

б) Насколько можно улучшить эту оценку?}

а) Индукция по~$t$. База при $t=3$ будет разобрана в конце; сначала мы докажем
переход.

Пусть $\cG$ --- конечное семейство прямых, в котором каждые $t^2+1$ (или
меньше) прямые имеют $t$-трансверсаль. Выберем произвольные $t^2+1$ прямые
из~$\cG$; одна из точек их $t$-трансверсали принадлежит хотя бы $t+1$ выбранной
прямой. Обозначим эту точку~$A$, а эти прямые $\ell_1,\dots,\ell_{t+1}$.

Пусть $\cG'$ --- подсемейство в~$\cG$, состоящее из всех прямых, не проходящих
через~$A$. Докажем, что в нём любой поднабор~$D$ из $t^2-t$ (или меньше) прямых
имеет $(t-1)$-трансверсаль. Действительно, набор
$D\cup\{\ell_1,\dots,\ell_{t+1}\}$ имеет $t$-трансверсаль~$X$. Две прямые из
$\ell_1,\dots,\ell_{t+1}$ должны проходить через одну и ту же точку
множества~$X$; значит, эта точка~--- $A$, то есть $A\in X$. Тогда $X\setminus
\{A\}$
--- требуемая трансверсаль для~$D$, ибо прямые из~$D$ не проходят через~$A$.

Заметим, что $t^2-t\geq (t-1)^2+1\geq HG_{t-1}(\cL)$. Из доказанного теперь
получаем, что $\cG'$ имеет $(t-1)$-трансверсаль~$X$. Но тогда $X\cup\{A\}$ ---
требуемая трансверсаль для~$\cG$.

\smallskip
Доказательство базы при $t=3$ дословно повторяет переход, кроме единственного
места, в котором используется предположение индукции. Именно, нам осталось
проверить, что $t^2-t=6\geq HG_2(\cL)$.

Заметим сначала, что $HG_1(\cL)\leq 3$. Действительно, если любые три прямые
из~$\cG$ имеют общую точку, то точка пересечения двух из них обязана
принадлежать всем остальным. Теперь неравенство $HG_2(\cL)\leq 6$ доказывается
дословным повторением перехода (с заменой чисел $t^2+1$ и $t^2-t$ на 6 и 3,
соответственно).

\medskip
б) Мы утверждаем, что $HG_t(\cL)=C_{t+2}^2$. Покажем сначала, что
$HG_t(\cL)\geq C_{t+2}^2$. Выберем некоторые $t+2$ точки $T_1,\dots,T_{t+2}$
общего положения на плоскости и проведём всевозможные прямые, соединяющие пары
этих точек. Нетрудно понять, что исходные точки можно выбрать так, что через
каждую точку, отличную от $T_1,\dots,T_{k+2}$, проходит не более двух
проведённых прямых. Теперь несложно убедиться в том, что полученное множество
прямых не имеет $t$-трансверсали, а любое его собственное подмножество ---
имеет.

\smallskip
Осталось доказать, что $HG_t(\cL)\leq C_{t+2}^2$. Мы будем использовать
следующую лемму.

\begin{lm}
  Пусть $P_1(x,y),\dots,P_k(x,y)$ --- многочлены от двух
  переменных степени $\leq t$, причём $k>C_{t+2}^2$. Тогда существуют такие числа
  $s_1,\dots,s_k$, не равные нулю одновременно, что
  $s_1P_1(x,y)+\dots+s_kP_k(x,y)=0$.
\end{lm}

\proof Условия на числа $s_i$ --- это система из $C_{t+2}^2$
линейных однородных (т.е. без константных слагаемых) уравнений (количество
уравнений --- это количество всевозможных мономов от двух переменных степени
$\leq t$). Поскольку количество переменных больше количества уравнений, эта
система имеет нетривиальное решение.
\qed

Перейдём собственно к решению. Очевидно, достаточно доказать следующее
утверждение: если $n\geq C_{t+2}^2$ и любые $n$ прямых из семейства~$\cG$ имеют
$t$-трансверсаль, то и любые $n+1$ прямая также имеют $t$-трансверсаль.

Предположим противное и рассмотрим $n+1$ прямую, для которых утверждение
неверно. Введём систему координат на плоскости так, чтобы прямые не проходили
через начало координат. Для любого индекса~$j$, уравнение $j$-й прямой~$\ell_j$
можно записать в виде $a_jx+b_jy+1=0$.

Зафиксируем теперь некоторый индекс~$i$. Если выкинуть прямую~$\ell_i$, то
найдутся $t$ точек $(x_1,y_1)$,
\dots, $(x_t,y_t)$ такие, что каждая из оставшихся прямых проходит хотя бы
через одну из них (а $\ell_i$, естественно, не проходит). Это означает, что
$\prod_{k=1}^t (a_jx_k+b_jx_k+1)=0$ при всех $j\neq i$, но не при $j=i$.
Обозначая $P_i(a,b)=\prod_{k=1}^t (ax_k+bx_k+1)$, получаем, что
$P_i(a_j,b_j)=0$ при всех $j\neq i$, но $P_i(a_i,b_i)\neq 0$.

Очевидно, все полученные многочлены имеют степень $t$. По лемме, найдутся числа
$s_1,\dots,s_n$ такие, что $\sum_{i=1}^n s_iP_i(a,b)=0$. При этом можно
считать, что $s_1\neq 0$. Но тогда $\sum_{i=1}^n
s_iP_i(a_1,b_1)=s_1P_1(a_1,b_1)\neq 0$. Противоречие.


\newsect

\itemm \stm{Пусть $\cG$ --- конечный набор множеств, каждое имеет не более~$d$
элементов. Докажите, что если любые $d+1$ множеств из~$\cG$ имеют общий
элемент, то и все множества из~$\cG$ имеют общий элемент. Докажите, что число
$d+1$ нельзя заменить на меньшее.

({\bf Упражнение на понимание.} Переформулируйте эту задачу, используя
терминологию, введённую выше.)}

Условие можно переписать одной формулой $H(\cN_d)=d+1$.

Взяв в качестве~$\cG$ семейство всех $d$-элементных подмножеств
$(d+1)$-элементного множества, мы получаем, что любые $d$ множеств в~$\cG$
имеют общий элемент, а все $d+1$ --- не имеют. Значит, $H(\cN_d)\geq d+1$.

Пусть теперь $\cG\subset \cN_d$ --- семейство, в котором любые $d+1$ множество
имеют общий элемент. При всех $i=1,\dots,\,d+1$ обозначим через $s_i$
минимальное возможное количество общих элементов у некоторых $i$ множеств
из~$\cG$. Очевидно, $1\leq s_{d+1}\leq s_d\leq \dots\leq s_1=d$. Значит,
$s_{j+1}=s_j$ при некотором $j\in[1,d]$.

Пусть $A_1,\dots,A_j\in\cG$ таковы, что $|Q|=s_j$, где $Q=A_1\cap\dots\cap
A_j$. Если $Q\not\subseteq A$ для какого-то $A\in\cG$, то $s_{j+1}=s_j>|Q\cap
A|=|A_1\cap\dots\cap A_j\cap A|$, что противоречит определению~$s_{j+1}$.
Значит, все множества из~$\cG$ содержат непустое множество~$Q$, что и
требовалось доказать.

\itemm \stm{Докажите, что все числа виде $HG_t(\cN_d)$ конечны.}

Естественно, утверждение следует из задачи~\ref{gen-fin}. Мы приведём здесь
более лёгкое доказательство.

Индукция по~$t$. База при $t=1$ доказана в предыдущей задаче. Пусть теперь
существует число $HG_{t-1}(\cN_d)=S$. Покажем, что $HG_t(\cN_d)\leq
T=S+C_{Sd}^t$.

Рассмотрим произвольное конечное $\cG\subset \cN_d$, в котором любые $T$
множеств имеют $t$-тран\-с\-ве\-р\-саль. Если любые $S$ множеств из~$\cG$ имеют
$(t-1)$-трансверсаль, то по предположению индукции~$\cG$ имеет даже
$(t-1)$-трансверсаль. В противном случае существует набор
$\cK=\{A_1,\dots,A_S\}\subset \cG$, не имеющий $(t-1)$-трансверсали. Значит,
любая $t$-трансверсаль набора $\cK$ должна целиком содержаться в множестве
$Q=A_1\cup\dots\cup A_S$. Заметим, что $|Q|\leq Sd$.

Предположим теперь, что $\cG$ не имеет $t$-трансверсали. Значит, для любого
$t$-элементного подмножества $X\subset Q$ найдётся $A_X\in\cG$, не
пересекающееся с~$X$. Рассмотрим, наконец, набор
$$
  \cK'=\cK\cup\left\{A_X\;:\;X\subset Q,\;|X|=t\right\}.
$$
Имеем $|\cK'|\leq S+C_{Sd}^t=T$, так что $\cK'$ должно иметь
$t$-трансверсаль~$Y$. Поскольку $\cK\subset \cK'$, множество~$Y$ должно лежать
в~$Q$. Но тогда в~$\cK'$ есть множество~$A_Y$, не пересекающееся с~$Y$. Это
противоречие завершает доказательство.

\itemm \stm{а) Докажите, что $HG_t(\cN_2)\geq C_{t+2}^2$.

б) Докажите, что $HG_t(\cN_2)= C_{t+2}^2$.}

а) См. задачу 4.4.

б) Следует из следующей задачи.

\itemm \stm{Докажите, что $HG_t(\cN_d)\geq C_{d+t}^t$.}

Достаточно рассмотреть семейство~$\cG$ всех $d$-элементных подмножеств
$(d+t)$-элементного множества~$X$. Тогда любое $t$-элементное подмножество
в~$X$ пересекается со всеми множествами из~$\cG$, кроме одного.

\itemmstar \label{gen-fin}
  \stm{({\sc Основная задача для конечных множеств})
  Докажите, что $HG_t(\cN_d)= C_{d+t}^t$.}

См. следующую задачу.

\itemm
\newcounter{catona}
\setcounter{catona}{\theprob}
\stm{а) ({\sc Задача Катоны})
  Пусть множества $A_1,A_2,\dots,A_n,B_1,\dots,B_n$ таковы, что $|A_i|=d$, $B_i=t$,
  множество $A_i$ пересекается со всеми $B_j$ при $j\neq
  i$, но $A_i\cap B_i=\emptyset$ (при произвольных индексах $1\leq i,j\leq n$).
  Докажите, что $n \le C_{d+t}^t$.

б) Выведите задачу \ref{gen-fin} из задачи Катоны. }

а) Непосредственно следует из задачи~4.7.

б) Предположим противное. Пусть $\cG\subset \cN_d$ --- семейство минимальной
мощности, такое, что любые $\leq C_{d+t}^t$ его подмножеств имеют
$t$-трансверсаль, а само оно $t$-трансверсали не имеет (тогда, конечно же,
$|\cG|>C_{d+t}^t$).

Пусть $\cG=\{A_1,\dots,A_n\}$. Для каждого~$i=1,\dots,n$, семейство
$\cG\setminus\{A_i\}$ имеет $t$-трансверсаль согласно выбору~$\cG$; обозначим
эту трансверсаль~$B_i$. Ясно, что $A_i\cap B_i=\emp$. Тогда система множеств
$A_1,\dots,A_n,B_1,\dots,B_n$ удовлетворяет условиям задачи Катоны,
следовательно, $|\cG|=n\leq C_{d+t}^t$. Противоречие.

\itemm
  \stm{Пусть множества $A_1,A_2,\dots,A_n,B_1,\dots,B_n$ удовлетворяют {\em условиям Катоны},
  т.е. $A_i\cap B_i=\emp$ и $A_i\cap B_j\neq \emp$ при любых $i\neq j$.
  Положим $a_i=|A_i|$, $b_i=|B_i|$. Докажите, что
  $\displaystyle \sum_{i=1}^n \frac1{C_{a_i+b_i}^{a_i}} \le 1$.}

Пусть объединение всех множеств содержит $m$ элементов. Рассмотрим $m!$
способов пронумеровать эти элементы числами от $1$ до $m$. Для $i \in [1;m]$
будем говорить, что некоторая нумерация имеет {\em $i$-й тип}, если номер
любого элемента множества~$A_i$ меньше, чем номер любого элемента
множества~$B_i$.

Заметим, что нумерация не может иметь больше одного типа. В самом деле, пусть
нумерация имеет типы $i$-й и $j$-й типы при $i \neq j$. Пусть $a_i$ и $a_j$
--- максимальные номера элемента из~$A_i$ и элемента из~$A_j$, соответствнно.
Можно считать, что $a_i\leq a_j$. Тогда все элементы в~$B_j$ имеют номера,
большие, чем~$a_j$; значит, среди элементов множества~$B_j$ нет элементов
множества~$A_i$, что противоречит условию.

Далее, посчитаем количество нумераций $i$-го типа. Заметим, что элементы
множества $A_i\cup B_i$ могут располагаться $(a_i+b_i)!$ способами, из которых
подходят $a_i!b_i!$; при этом, очевидно, для каждого такого способа существует
одно и то же количество перестановок всего множества, реализующих этот способ.
Итак, искомое количество равно $\displaystyle m!\cdot
\frac{a_i!b_i!}{(a_i+b_i)!}=m!\cdot \frac1{C_{a_i+b_i}^{a_i}}$.

Наконец, поскольку нумераций, имеющих хоть какой-то тип, не больше, чем всех
нумераций вообще, имеем
$$
  \sum_{i=1}^n \frac{m!}{C_{a_i+b_i}^{a_i}} \le m!,
$$
что и требовалось доказать.

\itemm
  \stm{Докажите, что существуют такие натуральные числа $a_1,\dots,
a_n,b_1,\dots,b_n$, что \\$\displaystyle \sum_{i=1}^n
\frac1{C_{a_i+b_i}^{a_i}} <\frac1{10^{100}}$, но множеств
$A_1,A_2,\dots,A_n,B_1,\dots,B_n$, удовлетворяющих условиям Катоны и таких, что
$|A_i|=a_i$, $|B_i|=b_i$, не существует.}

Пусть $a_1=1,\,a_2=10^{101},\,a_3=10^{101}$ и $b_1=10^{101},\,b_2=1,\,b_3=1$.
Тогда множества $B_2$ и $B_3$ должны пересекаться с $A_1$. Поскольку все три
этих множества одноэлементны, они должны совпадать; но $B_2$ не может совпадать
с~$B_3$.

\newsect

\bigskip

\itemm \stm{Дано семейство множеств~$\cF$. Пусть $|A\cap B|=1$ для любых различных $A,B \in \cF$
  (в частности, $\cF$ --- семейство степени~1).
  Пусть, кроме того, среди любых 4 множеств из $\cF$ найдутся три, имеющих непустое пересечение. Докажите,
  что из~$\cF$ можно выбросить 1 множество так, что все остальные имеют непустое
  пересечение.}

Рассмотрим любые три множества $A,B,C\in\cF$, имеющие общий элемент~$x$.
Предположим, что найдутся два различных множества $D,E\in\cF$, не
содержащие~$x$. Рассмотрим четыре множества $A,B,D,E$. У трёх из них есть общий
элемент~$y$; ясно, что тогда $y\neq x$. Далее, $y$ принадлежит хотя бы одному
из множеств $A$ и $B$, без ограничения общности множеству $A$. Тогда $y$ не
лежит ни в $B$, ни в~$C$, так как они уже имеют общий элемент~$x$ с
множеством~$A$. Тогда $y$ обязан принадлежать обоим множествам $D$ и $E$.

Рассмотрим теперь четверку $B,C,D,E$. Любая тройка множеств из нее содержит или
пару $B,C$, или пару $D,E$. Но единственный общий элемент пары $B,C$ ---
это~$x$, и он не принадлежит ни $D$, ни $E$. Аналогично, единственный общий
элемент пары $D,E$ --- это~$y$,  и он не принадлежит ни $B$, ни $C$. Итак, для
четверки $B,C,D,E$ нет элемента, покрытого тремя множествами --- противоречие.

Значит, наше исходное предположение неверно, и не более чем одно множество
в~$\cF$ не содержит~$x$.

\itemm \stm{Дано семейство множеств~$\cF$. Пусть $|A\cap B|=1$ для любых
различных $A,B \in \cF$, причем в $\cF$ есть хотя бы 17 множеств.
  Пусть, кроме того, среди любых 5 множеств из $\cF$ найдутся три, имеющих непустое пересечение.
  Докажите, что $\cF$ имеет 2-трансверсаль.}

Если среди любых четырех множеств из~$\cF$ есть три, имеющих общий элемент, то
по предыдущей задаче все множества, кроме одного, имеют общий элемент~$x$.
Выбрав из оставшегося множества любой его элемент~$y$, мы получим требуемую
2-трансверсаль~$\{x,y\}$.

Осталось рассмотреть случай, когда нашлись 4 множества $A,B,C,D\in\cF$,
пересечение любых трёх из которых пусто. Если к ним добавить любое другое
множество~$E\in\cF$, то три пересекающихся множества появятся; значит, $E$
содержит (единственный!) общий элемент каких-то двух из исходных четырёх
множеств. Поскольку у нас есть 13 вариантов для выбора~$E$ и 6 возможных пар
множеств~$A,B,C,D$, какая-то из пар появится хотя бы трижды; значит, общий
элемент~$x$ этой пары лежит в пяти множествах из~$\cF$; обозначим их
$X_1,X_2,X_3,X_4,X_5$.

Рассмотрим теперь множества в~$\cF$, не содержащие элемент $x$. Если их не
больше двух, то у них есть общий элемент~$y$, и $\{x,y\}$ --- требуемая
трансверсаль. Пусть их хотя бы три. Пусть любые три из них имеют общий элемент;
тогда легко видеть, что этот элемент~$y$ --- общий для всех, и мы нашли
2-трансверсаль $\{x,y\}$.

Осталось рассмотреть случай, когда найдутся множества $Y,Z,T$, не
содержащие~$x$ и не имеющие общего элемента. Обозначим их попарные пересечения
через $a_1,a_2,a_3$. Каждое $a_i$ принадлежит не более чем одному из множеств
$X_1,X_2,X_3,X_4,X_5$. В самом деле, пусть $a_1$ принадлежит множествам $X_1$ и
$X_2$. Тогда $X_1$ и $X_2$ пересекаются по двум элементам $x$ и $a_1$, что
невозможно.

Итак, из 5 множеств $X_1,X_2,X_3,X_4,X_5$ найдутся два, не содержащие ни одного
элемента из $a_1,a_2,a_3$. Пусть это $X_4$ и $X_5$. Тогда у пятерки множеств
$X_4,X_5,Y,Z,T$ нет тройного пересечения. Противоречие.

\medskip
\textbf{Далее мы сначала приведём доказательства ключевых фактов про
исключительные множества, а именно задач 5.10, 5.12--5.14. Мы будем затем
использовать их в решениях оставшихся задач.}

Во всём последующем тексте мы предполагаем, что $\cG$ ---
$(d;t)$-исключительное семейство.

Заметим сразу, что все множества $X_A$ при $A\in\cG$ различны, ибо при $A\neq
B$ множество $X_A$ пересекает~$B$, но не~$A$, а множество~$X_B$ --- наоборот.
Более того, отсюда же следует, что $X_A\not\subseteq X_B$.

Для решения дальнейших задач будут полезны следующие простые леммы.

\begin{lm}
  \label{dec-t}
  Пусть $\cG$ --- $(d;t)$-исключительное семейство, а $S$ --- некоторое
  множество мощности~$s$. Рассмотрим все такие множества $A\in\cG$, что $S\subseteq X_A$;
  составим из них семейство~$\cF$
  (то есть $\cF=\{A\in\cG: S\subseteq X_A\}$). Тогда $\cF$ является
  $(d,t-s)$-исключительным.
\end{lm}

\proof Если $S\subseteq X_A$, то $S\cap A=\emp$. Значит, для любых различных $A,B\in\cF$
мы имеем $B\cap (X_A\setminus S)=B\cap X_A\neq\emp$. Таким образом, для
семейства~$\cF$ можно все множества~$X_A$ заменить на $X_A\setminus S$, причём
$|X_A\setminus S|\leq t-s$. Тогда ясно, что $\cF$ --- $(d,t-s)$-исключительное.
\qed

\begin{lm}
  \label{dec-d}
  Пусть $\cG$ --- $(d;t)$-исключительное семейство, а $S$ --- некоторое
  множество мощности~$s$. Рассмотрим все множества $A\in\cG$, содержащие~$S$, и составим
  семейство~$\cF$ из всех таких множеств с выкинутым множеством~$S$
  (то есть $\cF=\{A\setminus S: S\subseteq A\in\cG\}$). Тогда $\cF$ является
  $(d-s,t)$-исключительным.
\end{lm}

\proof
Ясно, что для любых двух различных множеств $A,B\in\cG$, содержащих~$S$,
выполняется условие $|(A\setminus S)\cap (B\setminus S)|=|A\cap B|-s\leq d-s$.
Кроме того, мы имеем $X_A\cap S=\emp$; значит, $(B\setminus S)\cap X_A=B\cap
X_A\neq \emp$, что и значит, что $\cF$ --- $(d-s,t)$-исключительное.
\qed

\medskip
\itemp{10} \stm{Докажите, что $b(d;t)\geq a(d;t)$.}

Достаточно доказать, что если $a(d;t)> n$ при некотором~$n$, то и $b(d;t)> n$.

Если $a(d;t)> n$, то существует такое семейство~$\cG$ степени~$d$, что любые
$n$ множеств из~$\cG$ имеют $t$-трансверсаль, а всё семейство --- не имеет. Из
всех подсемейств семейства~$\cG$, не обладающих $t$-трансверсалью, выберем
минимальное по количеству множеств и назовём его~$\cF$. Пусть $k=|\cF|$; ясно,
что $k>n$. Тогда по выбору~$\cF$, любые $k-1$ множеств из~$\cF$ (скажем, все
без некоторого~$A$) имеют $t$-трансверсаль~$X$. Заметим, что $X$ не должна
пересекать~$A$, иначе~$X$ является $t$-трансверсалью для~$\cF$. Значит, $X$
удовлетворяет всем условиям на множество~$X_A$.

Итак, $\cF$ --- $(d;t)$-исключительное семейство, поэтому $b(d;t)\geq k>n$, что
и требовалось доказать.

\Remark. В дальнейшем почти все верхние оценки, получаемые на~$a(d;t)$, на
самом деле будут оценками на~$b(d;t)$. В этих случаях мы будем опускать ссылку
на предыдущую задачу, завершающую доказательство.


\itemp{12} \stm{а) Пусть $t=2$. Докажите, что $h(x)\leq d+2$ для любого $x$.

б) Пусть $t$ произвольно. Докажите, что $h(x)\leq b(d;t-1)$.}

Пункт а) является частным случаем б) ввиду задачи 5.3. Тем не менее, мы
приведём самостоятельное решение пункта а), а уже в решении б) сошлёмся на
нужную лемму.

а) Предположим, что $h(x)\geq d+3$, то есть существуют такие
$A_1,\dots,A_{d+3}\in\cG$, что $X_{A_i}=\{x,x_i\}$ при некоторых
элементах~$x_i$ (эти элементы различны, ибо множества~$X_{A_i}$ различны). Но
тогда $(d+1)$-элементное множество $\{x_1,x_2,\dots,x_{d+1}\}$ лежит и в
$A_{d+2}$, и в $A_{d+3}$. Это невозможно, ибо $|A_{d+2}\cap A_{d+3}|\leq d$.

б) Применив лемму~\ref{dec-t} для множества $S=\{x\}$, получаем, что семейство
$\cF=\{A\in\cG: x\in X_A\}$ является $(d,t-1)$-исключительным, т.е.
$h(x)=|\cF|\leq b(d;t-1)$.


\itemp{13} \stm{Докажите, что $g(x)\leq b(d-1;t)$ для любого~$x$.}

Применив лемму~\ref{dec-d} для множества $S=\{x\}$, получаем, что семейство
$\cF=\{A\setminus \{x\}: A\in \cG, x\in A\}$ является $(d-1,t)$-исключительным,
т.е. $g(x)=|\cF|\leq b(d-1;t)$.

\itemp{14} \stm{Пусть $t=2$; предположим, что $h(x)\leq d$. Докажите, что $|\cG|\leq
g(x)+h(x)+b(d-h(x);2)$.}

Пусть $B_1,\dots,B_h$ --- все такие множества в~$\cG$, что $x\in X_{B_i}$
(тогда $h=h(x)$). Положим $X_{B_i}=\{x,x_i\}$; как обычно, все элементы~$x_i$
различны.

Пусть $A_1,\dots,A_k$ --- все такие множества в~$\cG$, что $x$ не лежит ни
в~$A_i$, ни в~$X_{A_i}$. Поскольку $k=|\cG|-g(x)-h(x)$, достаточно доказать,
что $k\leq b(d-h(x);2)$.

Поскольку $A_i\neq B_j$ при всех $i,j$, мы получаем $\{x,x_j\}\cap
A_i\neq\emp$, а значит, $x_j\in A_i$, поскольку $x\notin A_i$. Итак, всё
множество $Y=\{x_1,\dots,x_h\}$ лежит во всех множествах~$A_i$. Применяя теперь
лемму~\ref{dec-d} к множеству~$S=Y$, получаем $k\leq b(d-h;2)$, что и
требовалось доказать.

\Remark. Утверждение и решение остаются верными и при $h(x)>d$; в этом случае
надо отметить, что $b(d-h;t)=1$ при $d<h$.

\medskip

\textbf{Сначала мы соберём серийные (но не обязательно точные) оценки.
Правда, иногда мы будем пользоваться точными оценками из частных случаев ниже.}

Согласно задаче~5.10, для получения верхних оценок на $a(d;t)$ достаточно
получить такие же оценки на $b(d;t)$. Поэтому в каждом случае ниже мы с самого
начала предполагаем, что выбрано $(d;t)$-исключительное семейство~$\cG$, и
оцениваем его мощность.

\itemp8 \label{genq1} \stm{а) Докажите, что $a(d;t) \ge C_{d+t+1}^t$.

б$)^{**}$ Существуют ли значения $d$, $t$, при которых неравенство в предыдущем
пункте строгое?}

а) Пусть $\cG$ --- семейство всех $(d+1)$-элементных подмножеств некоторого
$(d+t+1)$-элементного множества~$B$. Тогда любые два различных множества
из~$\cG$ пересекаются не более, чем по~$d$ элементам. С другой стороны, любое
$t$-элементное подмножество $X\subset B$ пересекается со всеми множествами
из~$\cG$, кроме одного.

б) Жюри до сих пор не знает ответа на этот вопрос.

\itemp3 \stm{Докажите, что $a(d;1)=d+2$.}

Согласно задачам 5.8а) и 5.10, нам достаточно доказать, что $b(d;1)
\le d+2$. Пусть существует $(d;1)$-исключительное семейство $\cF=\{A_1,A_2,\dots
,A_{d+3},\dots\}$ из не менее чем $d+3$ множеств. По определению
$(d;1)$-исключительного семейства все $X_{A_i}$ одноэлементные (пусть
$X_{A_i}=\{x_i\}$); значит, $x_i \in A_j$ при $i \neq j$. Очевидно, $x_i
\neq x_j$ при $i
\neq j$. Значит, множества $A_1$ и $A_2$ содержат $d+1$ общий элемент $x_3,
\dots,x_{d+3}$, что невозможно.

\Remark. В дальнейшем нам ещё потребуется очевидное равенство
$a(0;t)=b(0;t)=t+1$. Его доказательство мы оставляем читателю.

\medskip
Для удобства введём некоторые обозначения.

\begin{df}
  Для любого элемента~$x$, обозначим $G_x=\{A\in\cG: x\in A\}$ и
  $H_x=\{A\in\cG: x\in X_A\}$.
\end{df}

Для индукционного перехода в следующей задаче будет полезно такое уточнение
задачи 5.12а).

\begin{lm}
  \label{h<=d}
  Пусть $t=2$, и пусть $|\cG|>b(d-1;2)+d+3$. Тогда $h(x)\leq d$ для любого
  элемента~$x$.
\end{lm}

\proof
От противного. Пусть существуют такие $d+1$ множеств $A_1,\dots,A_{d+1}$, что
$X_{A_i}=\{x,x_i\}$ (при различных элементах $x_i$). По задаче 5.13, мы имеем
$g(x)\leq b(d-1;2)$. Значит, в~$\cG$ существуют хотя бы $d+3$ множества, не
содержащие~$x$, и два из них не совпадают с~$A_i$. Пусть это множества~$B$,
$C$. Поскольку~$x\notin B$, но $X_{A_i}\cap B\neq \emp$, получаем
$\{x_1,\dots,x_{d+1}\}\subseteq B$. Аналогично, $\{x_1,\dots,x_{d+1}\}\subseteq
C$. Значит, $|B\cap C|\geq d+1$, что невозможно.
\qed

\Remark. Это доказательство по сути повторяет доказательство задачи~5.14 (точнее, её версии при
$h>d$).

\itemp{5} \stm{а) Докажите, что $a(d;2) \ge C_{d+3}^2$.

б) Докажите, что $a(d;2) \le 2d^2+3$ при $d\geq 2$.}

а) Следует из общего примера из задачи 5.8а).

б) Мы докажем индукцией по $d\geq 2$, что $b(d;2)\leq 2d^2+3$. База будет
включена в переход.

Предположим, что $b(d;2)\geq b(d-1;2)+d+3$. Тогда $h(x)\leq d$ при всех~$x$ по
лемме~\ref{h<=d}. Обозначим $b=|\cG|$.

\smallskip
Для каждого элемента~$x$ обозначим через $n(x)$ количество упорядоченных троек
различных множеств~$(A,B,C)$ из семейства~$\cG$, таких, что $x\in A$, $x\in B$,
и $x\in X_C$. Мы оценим сумму~$\sigma$ всех чисел $n(x)$ двумя способами.

С одной стороны, существует $b(b-1)$ пар различных множеств~$(A,B)$. Для каждой
такой пары есть не более $d$ вариантов выбрать подходящий элемент~$x$ (ибо
$|A\cap B|\leq d$), и для каждого такого~$x$ существует $h(x)\leq d$ вариантов
множества~$C$. Итого, $\sigma=\sum_x n(x)\leq b(b-1)\cdot d^2$.

С другой стороны, рассмотрим произвольное множество~$C$ и положим
$X_C=\{x,y\}$. Каждое из остальных $b-1$ множеств в~$\cG$ содержит либо~$x$,
либо~$y$; пусть, скажем, $s_x$ множеств содержат~$x$ и $s_y$ множеств
содержат~$y$ ($s_x+s_y\geq b-1$). Тогда существует $s_x(s_x-1)$ пар множеств,
пересекающихся по~$x$, и $s_y(s_y-1)$ пар, пересекающихся по~$y$. Итого, тройки
с нашим множеством~$C$ учитываются как минимум $s(C)=s_x(s_x-1)+s_y(s_y-1)$
раз. Из равенства $s_x+s_y\geq b-1$ нетрудно получить, что $s(C)\geq
\frac{(b-1)(b-3)}2$ (оценка становится точной, если $s_x=s_y=\frac{b-1}2$). Итак, $\sigma\geq
b\frac{(b-1)(b-3)}{\mathstrut2}$.

В итоге мы получаем $d^2b(b-1)\geq \sigma\geq \frac12 b(b-1)(b-3)$, откуда
$2d^2\leq b-3$, что и требовалось доказать.

\smallskip
Осталось рассмотреть случай, когда $b(d;2)\leq b(d-1;2)+d+2$. Если $d\geq 3$,
то по предположению индукции мы имеем $b(d;2)\leq
(2(d-1)^2+3)+d+2=2d^2-3d+5\leq 2d^2+3$, что и требовалось. Если же $d=2$, то по
задач 5.4а) мы имеем $b(1;2)=6$, поэтому $b(2;2)\leq 6+2+2=10$, что и
требовалось.

\Remark. Заметим, что оценка в основной части решения допускает улучшения. Так,
верхняя оценка на~$\sigma$ точна только тогда, когда $h(x)=d$ при всех~$x$. В
то же время, из задачи~5.14 можно увидеть, что при этом условии $g(x)$ не может
равняться $\frac{b-1}2$, то есть нижняя оценка неточна. Метод получения более
точных оценок показан в лемме~\ref{price} перед вычислением~$b(1;4)$ и применён
далее.

\itemp7 \stm{а) Докажите, что $a(1;t) \ge C_{t+2}^2$.

б) Докажите, что $a(1;t) \le t^2+1$ при $t\geq 3$.}

а) Следует из общего примера из задачи 5.8а).

б) Решение дословно повторяет решение задачи 3.4а): единственное свойство
прямых на плоскости, которое использовалось в нём (в отличие от 3.4б)!) --- то,
что они образуют семейство степени~1 (проверьте это!).

\itemp{11} \stm{Докажите, что $b(d;t)$ конечно при всех $d$ и $t$.}

Мы докажем оценку $b(d;t)\leq t^{d+1}+(t^{d-1}+t^{d-2}+\dots+t^0)$ индукцией по
$d\geq 1$. База при $d=1$ доказана в задаче 5.7б).

Для перехода допустим, что $d\geq 2$. Рассмотрим произвольное множество
$A\in\cG$; пусть $X_A=\{x_1,\dots,x_t\}$. Тогда все остальные множества в~$\cG$
содержат хотя бы один из элементов $x_1,\dots,x_t$. При этом количество
множеств, содержащих~$x_i$, не превосходит~$b(d-1;t)$ по лемме~\ref{dec-d}.
Значит, $|\cG|\leq 1+tb(d-1;t)=1+t^{d+2}+(t^d+t^{d-1}+\dots+t)$, что и
требовалось доказать.

\Remark. Вместо задачи 5.7б) можно использовать в качестве базы тривиальную
оценку $b(0;t)\leq t+1$. В этом случае получается немного худшая оценка
$b(d;t)\leq t^{d+1}+t^d+\dots+1$.

\itemp9 \stm{а) Докажите, что число $a(d;t)$ конечно при любой паре $(d,t)$.

б) Насколько хорошую оценку сверху на $a(d;t)$ вам удастся получить?}

Решение пункта а) получается из задач 5.10--5.11. Оттуда же получается оценка
$a(d;t)\leq t^{d+1}+(t^{d-1}+t^{d-2}+\dots+t^0)$ при всех $d\geq 1$.

\textbf{Наконец, мы переходим к точным, хотя и частным, результатам из задач~5.4 и~5.6.
Здесь мы не ссылаемся на пункты этих задач, а просто выписываем доказанное
равенство.}

Нижние оценки во всех случаях непосредственно следуют из задачи 5.8а). Для
верхних оценок мы опять предполагаем, что выбрано $(d;t)$-исключительное
семейство~$\cG$, и оцениваем его мощность.

\underline{\boldmath$b(1;2)=6$.}
Предположим, что $|\cG|\geq 7$. Рассмотрим произвольное $C\in\cG$; пусть
$X_C=\{x,y\}$. Тогда каждое из остальных множеств в~$\cG$ содержит~$x$ или~$y$;
следовательно, хотя бы три из них содержат один и тот же элемент из~$X_C$,
скажем, $x\in A_1,A_2,A_3$. Заметим, что $g(x)\leq 3$ по задаче 5.13; значит,
остальные множества в~$\cG$ не содержат~$x$. По нашему предположению, в~$\cG$,
кроме $A_i$, есть ещё хотя бы 4 множества~$C_1,C_2,C_3,C_4$.

Рассмотрим произвольный индекс~$k=1,2,3,4$. Пусть $X_{C_k}=\{x_1,x_2\}$. Два из
множеств~$A_i$ должны содержать один и тот же элемент~$x_j$. Поскольку они
пересекаются только по~$x$ (ведь $\cG$
--- семейство степени 1!), мы получаем, что $x=x_j\in X_{C_k}$. Итак, $x\in C_k$ при всех $k=1,2,3,4$.
Значит, по лемме~\ref{dec-t}, применённой к~$S=\{x\}$, семейство
$\{C_1,C_2,C_3,C_4\}$
--- $(1;1)$-исключительное. Но тогда по задаче~5.3 оно имеет не более 3
элементов. Противоречие.

\Remark.
Проанализировав это решение, мы можем выделить следующую лемму, полезную и в
дальнейшем.

\begin{lm}
  \label{1t}
  Пусть $\cG$ --- исключительное $(1,t)$-семейство, причём $g(x)\geq t+1$ при некотором~$x$. Тогда для любого $B\in\cG$,
  мы имеем $x\in B$ или $x \in X_B$. Кроме того, $g(x)=t+1$, и семейство $\cF=\cG\setminus G_x$ является $(1,t-1)$-исключительным.
\end{lm}

\proof Пусть $g(x)\geq t+1$, и $G_x\supseteq \{A_1,\dots,A_{t+1}\}$.

Предположим, что $x\notin B$ и $x\notin X_B$ при некотором $B\in\cG$. Каждое из
множеств $A_1,\dots,A_{t+1}$ содержит хотя бы один элемент из~$X_B$; поскольку
$|X_B|=t$, два из них должны содержать один и тот же элемент (скажем, $y\in
A_1\cap A_2\cap X_B$). Но тогда $A_1\cap A_2$ содержит (различные!)
элементы~$x$ и~$y$, что невозможно. Значит, такого множества~$B$ не существует.

Далее, $g(x)\leq t+1$ по задаче 5.13, так что $g(x)=t+1$. Второе утверждение
следует теперь из леммы~\ref{dec-t}.
\eop

\medskip
\underline{\boldmath$b(1;3)=10$.}
Предположим, что $|\cG|\geq 11$. Рассмотрим произвольное $C\in\cG$; пусть
$X_C=\{x,y,z\}$. Тогда каждое из остальных множеств в~$\cG$ содержит хотя бы
один из элементов~$x$, $y$ или~$z$, то есть $g(x)+g(y)+g(z)\geq 10$. Значит,
одно из слагаемых больше трёх, скажем, $g(x)\geq 4$. Тогда по лемме~\ref{1t} мы
получаем, что $\cF=\cG\setminus G_x$ является $(1;2)$-исключительным, причём
$|\cF|\geq 7$. Это противоречит тому, что $b(1;2)=6$.

\Remark. Предыдущие два пункта по сути повторяют решение задачи 3.4а). Мы
приводим их здесь для удобства восприятия следующего пункта.

\medskip
Для дальнейшего продвижения мы несколько улучшим главный метод из задачи 5.5.
Именно, мы немого изменим определение суммы~$\sigma$, так, что она будет
допускать несколько лучшие оценки. Смысл следующего определения будет ясен из
дальнейшей леммы.

\begin{df}
  Для каждого элемента $x$, лежащего хотя бы в одном множестве вида~$X_A$,
  назовём его {\em ценой} величину~$\displaystyle
  p(x)=\frac{g(x)(g(x)-1)}{h(x)}$. Для каждого $C\in\cG$
  назовём его {\em ценой} величину $P(C)=\sum_{x\in X_C}p(x)$.
\end{df}

\begin{lm}
  \label{price}
  Пусть $\cG$ --- $(d;t)$-исключительное семейство мощности~$b$.
  Тогда существует множество~$C\in\cG$ такое, что $P(C)\leq d(b-1)$.
\end{lm}

\proof
Опять же, для каждого элемента~$x$ обозначим через $n(x)$ количество
упорядоченных троек различных множеств~$(A,B,C)$ из семейства~$\cG$, таких, что
$x\in A$, $x\in B$, и $x\in X_C$. Однако теперь мы будем оценивать чуть другую
сумму, а именно
$$
  \Sigma=\sum_x \frac{n(x)}{h(x)}
$$
(естественно, сумма берётся по всем элементам, участвующим в множествах
вида~$X_A$).

С одной стороны, существует $b(b-1)$ пар различных множеств~$(A,B)$. Для каждой
такой пары есть не более $d$ вариантов выбрать подходящий элемент~$x$ (ибо
$|A\cap B|\leq d$). Далее, любой элемент $x\in A\cap B$ добавляет ровно единицу
к~$\Sigma$; действительно, существует $h(x)$ вариантов множества~$C$, и каждый
из этих вариантов будет считаться с <<весом>> $1/h(x)$. Итого, получаем
$$
  \Sigma=\sum_{(A,B):\;A\neq B} |A\cap B|\leq d\cdot b(b-1).
$$

С другой стороны, рассмотрим произвольное множество~$C$. Покажем, что тройки
вида $(A,B,C)$ вносят в~$\Sigma$ вклад, равный как раз~$P(C)$. Действительно,
для каждого $x\in X_C$, в числе $n(x)$ посчитаны $g(x)(g(x)-1)$ пар. Учитывая
<<вес>> $1/h(x)$, мы получаем, что <<вклад пары $x,C$>> равен $p(x)$, а тогда
<<вклад>> множества~$C$ равен~$P(C)$, что и требовалось.

Итак, $db(b-1)\geq \Sigma=\sum_{C\in\cG} P(C)$. По принципу Дирихле, одно из
$b$~слагаемых справа не превосходит~$d(b-1)$.
\eop

\medskip
\underline{\boldmath$b(1;4)=15$.}
Предположим, что $|\cG|\geq 16$; выкинув несколько множеств из~$\cG$, можно
считать, что $b=|\cG|=16$. Рассмотрим произвольное $C\in\cG$; пусть
$X_C=\{x_1,x_2,x_3,x_4\}$. Аналогично предыдущему пункту, получаем, что $\sum_i
g(x_i)\geq 15$, причём $g(x_i)\leq 4$ (иначе, используя лемму~\ref{1t}, мы
приходим к противоречию с $b(1;3)=10$).

Итак, $\sum_ig(x_i)=\sum_i|G_{x_i}|\leq 16$, но каждое $A\in \cG$, отличное
от~$C$, должно лежать в одном из $G_{x_i}$. Это означает, что либо все
семейства $G_{x_i}$ не пересекаются, либо пересекаются лишь два из них, причём
по одному элементу. В любом случае, можно считать, что $G_{x_1}$, $G_{x_2}$ и
$G_{x_3}$ не пересекаются и содержат по 4 множества% (а $G_{x_4}$ может
%пересекаться лишь с~$G_{x_3}$ и содержать 3 или 4 элемента)
.

\smallskip
\textbf{Утверждение.} Для любого~$A\in\cG$, отличного от~$C$, множество~$X_A$
не содержит ни одного из элементов~$x_1,x_2,x_3$.

\textit{Доказательство.} Пусть $x_1\in X_A$; тогда, очевидно, $x_1\notin A$. Заметим, что один из двух элементов $x_2,x_3$
также не лежит в~$A$, ибо $G_{x_2}\cap G_{x_3}=\emp$; пусть для определённости
$x_2\notin A$. Предположим, что $x_2\notin X_A$. Обозначим четыре множества,
содержащие~$x_2$, через $B_1,B_2,B_3,B_4$; все они не содержат~$x_1$.
Пересечение любых двух из них есть $\{x_2\}$; значит, все множества $B_i\cap
X_A$ не пересекаются. Таким образом, $X_A$ и состоит из этих четырёх
пересечений (ибо $|X_A|=4$), а они не содержат~$x_1$. Это противоречит тому,
что $x_1\in X_A$.

Итак, мы получили, что $x_1,x_2\in X_A$. Предположим теперь, что $x_3\notin
X_A$. В семействе $G_{x_3}$ есть хотя бы три множества, отличных от~$A$. Тогда
они должны пересекаться с~$X_A$ по различным элементам, отличным от~$x_1,x_2$.
Это опять же невозможно, ибо $|X_A|=4$.

Итак, $X_A=\{x_1,x_2,x_3,y\}$ при некотором~$y\neq x_4$. Рассмотрим теперь два
множества~$B,B'\in \cG$, не лежащее в~$G_{x_i}$ при $i=1,2,3$ и не совпадающие
с $A$, $C$ (такие множества найдутся, ибо $|G_{x_1}|+|G_{x_1}|+|G_{x_1}|+2=
14=|\cG|-2$). Тогда $\emp\neq B\cap X_C$, поэтому $x_4\in B$. Аналогично, $y\in
B$, а также $x_4,y\in B'$. Значит, $|B\cap B'|\geq 2$, что невозможно.
\eop

Итак, мы знаем, что $h(x_1)=h(x_2)=h(x_3)=1$ и $g(x_1)=g(x_2)=g(x_3)=4$.
Значит, $P(C)\geq 3\cdot \frac{12}1+p(x_4)>36$. С другой стороны, по
лемме~\ref{price} существует~$C\in\cG$ такое, что $P(C)\leq db=30<36$. Это
противоречие завершает доказательство.

\medskip
\underline{\boldmath$b(2;2)=10$.}
Предположим, что $|\cG|=11$; тогда из леммы~\ref{h<=d} следует, что $h(x)\leq
2$ при всех $x$, а из задачи 5.13 --- что $g(x)\leq 6$. Тогда из задачи 5.14
следует, что при $h(x)=2$ мы имеем $g(x)=6$. Значит, если $g(x)$ принимает
значение 4, 5 или 6, то величина $p(x)$ не может быть меньше, чем 12, 20 или
$\frac{30}2=15$, соответственно.

По лемме~\ref{price}, существует~$C\in\cG$, для которого $P(C)\leq 2\cdot
10=20$. Пусть $X_C=\{x,y\}$, причём $g(x)\geq g(y)$. Заметим, что
$g(x)+g(y)\geq |G_x\cup G_y|=10$, так что $g(x)\geq 5$, $g(y)\geq 4$. Тогда
$P(C)\geq 15+12=27$. Противоречие.

\medskip
\underline{\boldmath$b(3;2)=15$.}
Пусть $|\cG16$. Действуя аналогично предыдущему решению, мы получаем $h(x)\leq
3$, $g(x)\leq 10$, причём при $h(x)=1,2,3$ мы имеем соответственно $g(x)\geq
5,8,10$.

Далее, из леммы~\ref{price} мы находим $C\in\cG$ такое, что $P(C)\leq3\cdot
15=45$. Пусть $X_C=\{x,y\}$ и $g(x)\geq g(y)$. Тогда $g(x)\geq 8$, поэтому
$p(x)\geq 28$; также $p(y)\geq 20$, ибо $g(y)\geq 5$. Значит, $P(C)\geq 48$.
Противоречие.

\medskip
\underline{\boldmath$b(4;2)=21$.}
Действуя аналогично предыдущим пунктам, находим $C\in\cG$ такое, что $P(C)\leq
84$. Если $X_C=\{x,y\}$ и $g(x)\geq g(y)$, то аналогичное противоречие
получается всегда, кроме случая $g(y)=6$; но тогда должно получиться $g(x)=15$
и $h(x)=4$ (иначе опять $P(C)>84$).

Рассмотрим этот случай отдельно. Поскольку $h(x)=4$, должны существовать
множества $C_1,C_2,C_3,C_4$ такие, что $h(C_i)=\{x,y_i\}$. Тогда есть
$22-g(x)-h(x)=3$ множества $B_1,B_2,B_3$ такие, что $x\notin B_i$ и $x\notin
X_{B_i}$. Из свойств множеств $X_{C_j}$ следует, что
$\{y_1,y_2,y_3,y_4\}\subseteq B_i$. Значит, любые два из множеств~$B_i$ должны
пересекаться ровно по элементам $y_1,y_2,y_3,y_4$.

Наконец, для любого $C\in\cG$, отличного от~$B_i$, множество~$X_C$ пересекает
все $B_i$; значит, один его элемент содержится в двух множествах из~$B_i$.
Значит, в~$X_C$ содержится один из $y_1,y_2,y_3,y_4$. Отсюда следует, что
$\sum_i h(y_i)\geq 22-3=19$; но тогда $h(y_i)\geq 5$ при некотором~$i$. Как мы
уже отмечали выше, это невозможно.

\Remark. Развивая эти методы, авторы смогли доказать равенство
$a(d;2)=b(d;2)=C_{d+2}^2$ для всех $d\leq 7$.

\end{document}


