На однокруговый шахматный турнир приехало $n$ шахматистов из страны $A$ и $n$ шахматистов из страны $B$. Оказалось, что как бы ни разбить шахматистов на пары (чтобы друг с другом играли шахматисты разных стран), найдётся хотя бы одна пара шахматистов, которые уже встречались ранее друг с другом. Докажите, что можно выбрать $a$ шахматистов из страны $A$ и $b$ шахматистов из страны $B$ так, что каждый из выбранных $a$ шахматистов встречался с каждым из выбранных $b$ шахматистов, а $a+b\gt n$.
При $n=1$ утверждение задачи очевидно ($a=b=n=1$). Теперь надо доказать его для $n=k$, предполагая, что оно верно для всех $n\lt k$.
В случае, когда каждый из $k$ шахматистов, прибывших из страны $A$, встречался ранее с каждым, прибывшим из $B$, доказывать нечего ($a=b=k$). Поэтому будем считать, что какие-то два шахматиста — $\alpha$ из $A$ и $\beta$ из $B$ — друг с другом не встречались. Тогда остальные шахматисты удовлетворяют условию задачи для $n=k-1$. (Если составить из них пары и присоединить к ним $(\alpha,\beta)$, то по условию в одну из этих пар, но заведомо не в $(\alpha,\beta)$, попадут встречавшиеся шахматисты.) По предположению индукции можно образовать группу $\mathscr A$ из $a_1$ шахматистов страны $A$ и группу $\mathscr B$ из $b_1$ шахматистов страны $B$ так, что каждый шахматист группы $\mathscr A$ встречался с каждым из $\mathscr B$ и $a_1+b_1\ge k-1$. Если окажется, что $a_1+b_1\gt k$, — всё в порядке ($a=a_1$, $b=b_1$). Остаётся рассмотреть случай $a_1+b_1=k$; рассуждения иллюстрирует рисунок на полях.
В этой «таблице встреч» каждый столбец отвечает шахматисту, прибывшему из страны $A$, а строка — шахматисту из $B$ (здесь $n=6$). Единицы стоят на пересечениях строк и столбцов, отвечающих встречавшимся ранее шахматистам, на остальных местах — нули. Жёлтым цветом отмечены клетки, отвечающие парам выбранных шахматистов, красным — одна из максимальных систем независимых нулей.
Пусть $\overline{\mathscr A}$ — группа из $k-a_1=b_1$ шахматистов из $A$, не вошедших в группу $\mathscr A$, $\overline{\mathscr B}$ — группа шахматистов из $B$, не вошедших в $\mathscr B$. Рассмотрим два новых турнира — для групп $\mathscr A$ и $\overline{\mathscr B}$ ($n=a_1$) и $\overline{\mathscr A}$ и $\mathscr B$ ($n=b_1$). Один из этих турниров (для определённости, с участием групп $\mathscr A$ и $\overline{\mathscr B}$) удовлетворяет условию задачи. (В противном случае можно так составить пары из шахматистов групп $\mathscr A$ и $\overline{\mathscr B}$ и, независимо, групп $\overline{\mathscr A}$ и $\mathscr B$, что ни в одну из этих пар не попадут встречавшиеся шахматисты, а это противоречит условию для «общего» турнира.)
По предположению индукции в группе $\mathscr A$ можно найти $a_2$ шахматистов, каждый из которых встречался с каждым из каких-то $b_2$ шахматистов группы $\overline{\mathscr B}$, причём $a_2+b_2\ge a_1$.
Кроме того, по выбору групп $\mathscr A$ и $\mathscr B$ каждый из этих $a_2$ шахматистов встречался с каждым из $b_1$ шахматистов группы $\mathscr B$. Таким образом, мы можем выбрать $a=a_2$ шахматистов страны $A$ и $b=b_1+b_2$ из страны $B$, каждый из которых встречался со всеми выбранными шахматистами другой страны. При этом $a+b=a_2+b_2+b_1\ge a_1+b_1=k$, что и требовалось.
Приведённый нами рисунок также поясняет, как свести задачу к следующей теореме Д. Кёнига о матрицах (т. е. прямоугольных таблицах), составленных из нулей и единиц:
Назовём линией любую строку или столбец таблицы; два числа в таблице, не лежащие на одной и той же линии, назовём независимыми. Тогда минимальное число линий, содержащих все нули, равно максимальному числу независимых нулей.
В нашем случае число строк и столбцов в матрице (таблице встреч) одинаково (и равно $n$); условие задачи означает, что в любом наборе независимых чисел есть единица, т. е. максимальное число независимых нулей меньше $n$. По теореме Кёнига можно указать меньше $n$ линий, содержащих все нули. Тогда в пересечениях остальных линий — $a$ столбцов и $b$ строк, где $a+b\gt n$, — стоят единицы, а это, по существу, и утверждается в задаче.
Ещё одно эквивалентное утверждение, часто используемое в олимпиадных задачах, — теорема Холла о различных представителях (или «теорема о свадьбах»): пусть каждый из $n$ юношей знаком с некоторыми из $n$ девушек, причём для любых $k$ юношей($k=1$, 2, $\ldots$, $n$) имеется по крайней мере $k$ девушек, знакомых хотя бы с одним из них; тогда их можно разбить на пары так, что в каждой паре будут знакомые девушка и юноша. Эту теорему в разных формулировках и с несколькими доказательствами можно найти в статьях М. И. Башмакова («Квант», 1970, № 4, с. 14) и В. Н. Вагутена («Квант», 1974, № 11, с. 23).
