Квадратная таблица размером $n\times n$
заполнена неотрицательными числами так, что как сумма чисел
любой строки, так и сумма чисел любого столбца равна 1.
Докажите, что из таблицы можно выбрать $n$ положительных чисел,
никакие два из которых не стоят ни в одном столбце, ни в одной строке.
Заметим сначала, что если мы будем переставлять между собой строки (или
столбцы) нашей таблицы, то это не повлияет ни на условие задачи, ни на то, что нам требуется доказать. Предположим, что перестановками строк и столбцов
мы собрали в правый верхний угол размером $m\times k$ одни нули (рис. 7).
Докажем, что $m+k$ всегда не больше $n$. Подсчитаем сумму чисел, стоящих в куске, обозначенном на рисунке буквой $C$. Ясно, что сумма чисел, стоящих в куске $B$, равна $m$ ($m$ столбцов, в каждом из которых сумма равна 1).
Аналогично сумма чисел в куске $A$ равна $k$ ($k$ строк). Так как общая
сумма всех чисел в таблице равна $n$, то на долю куска $C$ остаётся $n-m-k$.
Это число неотрицательное, так как по условию в таблице все числа
неотрицательны. Итак, $n-m-k\ge 0$, т. е. $m+k\le n$, что мы и утверждали.
Теперь мы можем переформулировать задачу так: в таблице $n\times n$ стоят
числа, и известно, что никакой перестановкой строк и столбцов нельзя
выделить в ней угол из нулей размером $m\times k$ такой, что $m+k\gt n$;
доказать, что можно выбрать $n$ отличных от нуля чисел, никакие два из которых не стоят ни в одном столбце, ни в одной строке. (Для нас теперь не важно, что числа положительные и что суммы по строкам и столбцам равны 1.
Эти условия мы уже использовали. В дальнейшем мы различаем только «нули» и «не нули».)
Таблица знакомствРис. 8
Если вы читали статью М. И. Башмакова «Паросочетания и транспортные сети»
в № 4 нашего журнала, то вы легко сообразите, что наша новая формулировка
задачи есть просто запись на языке «таблиц» теоремы о сватовстве.
Действительно, запишем в строки таблицы $n\times n$ юношей, а в столбцы —
девушек (пусть и тех и других по $n$). На пересечении $s$-й строки и $t$-го
столбца поставим «не-нуль» (звёздочку), если $s$-й юноша знаком с $t$-й
девушкой, и «нуль», если незнаком. Получим таблицу (как говорят математики,
«матрицу») знакомств.
Возьмём произвольную группу из $k$ юношей. Поставим соответствующие им строки первыми. Если с какой-то девушкой ни один из этих юношей не знаком,
то в соответствующем столбце в первых $k$ строках стоят нули. Если все столбцы, соответствующие всем таким девушкам, мы переставим последними
(пусть их число равно $m$), то мы получим угол из нулей размером $m\times k$
(рис. 8). В каждом из первых $m-n$ столбцов есть хотя бы один «не-нуль» в первых строках, так как соответствующая девушка имеет друзей из числа
выбранных нами $k$ юношей. Так как $m+k\le n$, то $n-m\ge k$, т. е. таких
девушек не меньше $k$. Мы видим, что данные задачи полностью совпадают с данными «теоремы о сватовстве». Выбор $n$ невест для всех юношей — это и есть выбор $n$ «не-нулей», стоящих в разных строках и столбцах.
Теперь вы можете прочесть простое (по индукции) доказательство «теоремы о сватовстве», которое и даёт полное решение задачи. Конечно, сводить задачу к этой теореме вовсе не обязательно. Индуктивное рассуждение можно проводить и сразу — переставляя строки и столбцы (так поступил, например, читатель
Д. Григорьев из г. Ленинграда). При этом получается новое
доказательство «теоремы о сватовстве».
