Пусть число команд равно $N$. Представим сначала результаты турнира в виде турнирной таблицы $N\times N$. На пересечении $i$-й строки и $j$-го столбца поставим число очков, набранных $i$-й командой в матче с $j$-й командой; будем обозначать его через $a_{ij}$. Будем считать, что команда в матче «с самой собой» набрала 0 очков, тогда на диагонали будут стоять нули ($a_{ii}=0$).
Заметим теперь, что если $a_{ij}=0$, т. е. $i$-я команда проиграла $j$-й, то $a_{ji}=2$, так как в этом случае $j$-я команда выиграла у $i$-й. Точно так же, если $a_{ij}=1$, то и $a_{ji}=1$. Итак, в турнирной таблице обязательно выполняется условие $a_{ij}+a_{ji}=2$.
Каждой команде в турнирной таблице ссответствует строка и столбец. Число очков, набранных $i$-й командой в матчах с группой команд с номерами $j_1$, $\ldots$, $j_k$ равно сумме чисел $a_{i{j_1}}$, $\ldots$, $a_{i{j_k}}$ стоящих на пересечении $i$-й строки со столбцами $j_1$, $\ldots$, $j_k$.
Теперь мы можем забыть про хоккейный турнир, сформулировав по-новому задачу на языке таблиц. Пусть квадратная таблица $N\times N$, состоящая из целых чисел $a_{ij}$, удовлетворяет следующим двум условиям:
- все числа $a_{ii}$, стоящие на её диагонали, чётны, и сумма $a_{ij}+a_{ji}$ каждых двух чисел, симметричных относительно этой диагонали, тоже обязательно чётна;
- 2) для каждой группы столбцов найдется такая строка, что сумма чисел на пересечении этой строки со столбцами этой группы нечётна.
Нужно доказать, что условия 1) и 2) могут выполняться только в том случае, когда $N$ чётно.
Разумеется, решив эту новую задачу, мы решим и задачу М160.
Будем доказывать утверждение задачи от противного. Допустим, что существует таблица $N\times N$ с нечётным $N$, удовлетворяющая условиям 1) и 2). Мы покажем, что тогда можно построить таблицу $(N-2)\times(N-2)$, также удовлетворяющую условиям 1) и 2). Применив это построение $\dfrac{N-1}{2}$ раз, мы получили бы таблицу, coстоящую из единственного числа и удовлетворяющую условиям 1) и 2). Этого, однако, не может быть, так как для таблицы $1\times1$ оба условия одновременно не выполняются. Значит, сделанное предположение окажется кеверным и утверждение задачи будет доказано.
Для того чтобы из таблицы $N\times N$ построить таблицу $(N-2)\times(N-2)$, coxpaнив условия 1) и 2), мы введём следующие преобразозания таблиц:
Преобразование I. Меняем местами $i$-ю строку с $j$-й и $i$-й столбец с $j$-м.
Преобразование II. $i$-й столбец заменяем на сумму $i$-го и $j$-го столбца, а затем $i$-ю строку на сумму $i$-й и $j$-й строки.
Поясним преобразование II; $i$-ю и $j$-ю строки можно рассматривать как наборы $N$ чисел $(a_{i_1}{,}~{\ldots}{,}~a_{i_N})$ и $(a_{j_1}{,}~{\ldots}{,}~a_{j_N})$; суммой строк назвать строку: $(a_{i_1}+a_{j_1}{,}~{\ldots}{,}~a_{i_N}+a_{j_N})$; например,
$$
\colsep{0pt}{\begin{array}{ccccccccc}
&(&0&1&0&1&0&2&)\\[-6pt]
+\\[-6pt]
&(&1&0&1&1&1&0&)\\[+1pt]
\hline\\[-11pt]
&(&1&1&1&2&1&2&)
\end{array}}.
$$
Аналогично определяется сумма $i$-го и $j$-го столбцов.
Прежде всего заменим все чётные числа в таблице на 0, а нечётные — на 1. Получим таблицу, которая симметрична, т. е. $a_{ij}=a_{ji}$, кроме того, $a_{ii}=0$, поэтому условие 1) для неё выполнено. Очевидно, что для неё сохраняется и условие 2). Рассмотрим последний, $N$-й столбец этой таблицы. Согласно свойству 2) для него найдется такая строка, что на их пересечении стоит единица; если $k$ — номер строки, то $a_{kN}=1$ и, следовательно $a_{Nk}=1$ (Здесь мы применили условие 2) к одному столбцу.)
Сделаем теперь преобразование I; поменяем местами $k$-ю строку с $(N-1)$-й и $k$-й столбец с $(N-1)$-м. В результате таблица будет иметь следующий вид:
$$
A=
\begin{vmatrix}
0&{\ldots}&a_{1(N-1)}&a_{1N}\\
a_{21}&{\ldots}&a_{2(N-1)}&a_{2N}\\
a_{31}&{\ldots}&a_{3(N-1)}&a_{3N}\\
\mathrlap{.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.}\\
a_{(N-2)1}&{\ldots}&a_{(N-2)(N-1)}&a_{(N-2)N}\\
a_{(N-1)1}&{\ldots}&0&1\\
a_{N1}&{\ldots}&1&0
\end{vmatrix}.
$$
Применив теперь несколько раз преобразование II (используя два крайних столбца и две крайние строки), мы можем привести таблицу к такому виду:
$$
\tilde A=
\begin{vmatrix}
\tilde a_{11}&{\ldots}&\tilde a_{1(N-2)}&0&0\\
\tilde a_{i1}&{\ldots}&\tilde a_{i(N-2)}&0&0\\
\mathrlap{.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.}\\
\tilde a_{(N-2)1}&{\ldots}&\tilde a_{(N-2)(N-2)}&0&0\\
0&{\ldots}&0&0&1\\
0&{\ldots}&0&1&0
\end{vmatrix}.
$$
Напомним, что число 2 мы заменяем на 0. Вычеркнув из этой таблицы последние два столбца и последние две строки, мы получим новую таблицу $(N-2)\times(N-2)$. Остаётся проверить, что она удовлетворяет условиям 1) и 2).
Преобразования I и II переводят симметричные таблицы в симметричные и не меняют чётности чисел, стоящих на диагонали. Следовательно, новая таблица будет удовлетворять условию 1).
Остаётся проверить, что преобразования I, II сохраняют условия 2). Для преобразований I это совершенно ясно. Остаётся доказать это для преобразования II.
Если рассматриваемая группа столбцов не содержит $i$-го столбца и можно указать $k$-ю строку, удовлетворяющую условию 2), где $k$ не равно $i$, то, очевидно, и после преобразования $k$-я строка будет ему удовлетворять.
Если этого сделать нельзя, т. е. $k=i$ (хотя бы одна строка до преобразования существует!), то для $j$-й строки соответствующая сумма чётна. Отсюда ясно, что в преобразованной таблице сумма для $i$-й строки по-прежнему нечётна.
Аналогично разбираются случаи, когда в группу столбцов входит $i$-й столбец. Если в неё не входит $j$-й столбец, то надо взять строку, «обслуживающую» группу, пополненную $j$-м столбцом, а если входит, то, наоборот, его надо убрать. Мы сумели от таблицы $N\times N$ перейти к таблице $(N-2)\times(N-2)$. Таким образом, наша задача полностью решена.
Оказывается, что наша задача — частный случай такой общей теоремы из линейной алгебры:
если $a_{ij}+a_{ji}=0$, и система уравнений
$$
\left\{
\begin{array}{l}
a_{11}x_1+a_{12}x_2+\ldots+a_{1N}x_N=0,\\
a_{21}x_1+a_{22}x_2+\ldots+a_{2N}x_N=0,\\
.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.\\
a_{N1}x_1+a_{N2}x_2+\ldots+a_{NN}x_N=0
\end{array}
\right.
$$
имеет только нулевое решение, то $N$ чётно.
Эта теорема верна и для обычных чисел, и для «поля» из двух элементов 0 и 1, и для любого другого «поля». Проще всего её доказывать, используя понятие определителя систем линейных уравнений. Так и поступил читатель Э. Туркевич (Черновцы), приславший нам решение задачи М160. Но можно доказывать её и с помощью «элементарных преобразований» таблицы $a_{ij}$, как поступили мы выше.
Постарайтесь самостоятельно доказать эту теорему и вывести из неё решение задачи.
