Разделы 
Дополнительно
Задача по математике - 3695
2019-06-15 
Когда закончился хоккейный турнир (в один круг), оказалось, что для любой группы команд можно найти команду (может быть, из этой же группы), которая набрала в играх с командами этой группы нечетное число очков. Докажите, что в турнире участвовало четное число команд. (Поражение - 0 очков, ничья - 1 очко, выигрыш - 2 очка.)
Решение:
Заменим в таблице турнира все четные числа нулями, нечетные - единицами. Обозначим полученную таблицу через $A$, ее элементы - через $a_{ij}$ ($i, j = 1, 2, \cdots, n$): $a_{ij} = 1$, если $i$-я и $j$-я команды сыграли вничью, $a_{ij} = 0$ - в противном случае. Таблица удовлетворяет условию симметрии и на диагонали стоят нули:
$a_{ij} = a_{ji}, a_{ij} = 0$ для всех $i, j$. (1)
Требование, которое предъявляется к таблице в условии задачи, можно сформулировать так: для любого набора $x = (x_1, x_2, \cdots, x_n$) из нулей и единиц, отличного от $0 = (0, 0, \cdots, 0)$, хоть одно из чисел
$y_i = a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n$ (А)
нечетно. Для каждой группы команд мы строим набор полагая $x_j = 1$, если $j$-я команда входит в группу, и 0, если не входит, при этом $y_i$ равно количеству ничьих $i$-й команды с этой группой. Будем набор ($y_1, y_2, \cdots, y_n)$, полученный из $x$ с помощью таблицы $A$ по правилу $(A)$, обозначать $A_x$. Поскольку нас интересует лишь различие между четными и нечетными числами, удобно упростить арифметику, оставив лишь два числа 0 и 1, и считать, что $0 + 1 = 1 + 0 = 1, 1 + 1 = 0 + 0 = 0$ (правила умножения и все основные законы арифметики при этом сохраняются). Тогда у также будет набором из 0 и 1» При этом основное требование к таблице принимает вид:
если $x \neq 0$, то $y = Ax \neq 0$; (2)
такую таблицу $A$ назовем невырожденной.
Теперь, когда мы от хоккея полностью перешли к алгебре, можно приступить к решению задачи: доказать, что при нечетном $n$ условия (1) и (2) не могут одновременно выполняться. Будем упрощать нашу таблицу $A$, сохраняя эти условия.
Условие (2) не нарушится, если таблицу $A$ изменить, прибавив к первой строке вторую: если $A_x = y = (y_1, y_2, \cdots, y_n)$, то для новей таблицы $A^{ \prime}$ будет $A^{ \prime}x = y^{ \prime} = (y_1 + y_2, \cdots, у_n)$, если $у \neq 0$, то и $y^{ \prime} \neq 0$. Условие (2) не нарушится также, если к первому столбцу $A$ прибавить второй: если $A_x = y$, где $x = (x_1, x_2, \cdots x_n)$, то для новой таблицы $A^{ \prime \prime}$ будет $A^{ \prime \prime}x^{ \prime \prime} = у$, где $x^{ \prime \prime} = (x_1 + x_2, x_2, \cdots, x_n)$; если $x \neq 0$, то и $x^{ \prime \prime} \neq 0$. Разумеется, можно также прибавлять $i$-ю строку к $j$-й или $i$-й столбец к $j$-му; если сделать такие два преобразования одновременно, то новая таблица будет не только невырожденной (2), но также симметричной (1) (при этом правило $1 + 1 = 0$ сохраняет нули на диагонали).
Приступим теперь к упрощению таблицы $A$. Можно считать, что «первые две команды сыграли вничью», т. е. $a_{12} - a_{21} = 1$. Прибавляя первую строку (и первый столбец) к тем строкам (столбцам), где стоят единицы во втором столбце (соответственно строке), мы избавимся от всех этих единиц; точно так же, с помощью второй строки (и второго столбца) мы избавимся от единиц в первом столбце (и в первой строке) и получим таблицу $A_{n-2}$ такого вида, как показано на рис. а. Остающаяся после отбрасывания первых двух строк и столбцов таблица $A_{n-2}$ размера $(n - 2) \times (n - 2)$ по-прежнему удовлетворяет условиям (1) и (2): ведь $A_x \neq 0$ для любого $x = (0, 0, x_1, x_2, \cdots, x_{n-2})$, а остающаяся таблица $A_{n-2}$ преобразует координаты $(x_1, x_2, \cdots, x_{n-2})$ точно так же. Продолжая те же упрощения, переходя к таблицам $A_{n-4}, A_{n-6}, \cdots$, мы в конце концов, если $n$ было нечетно, придем к таблице $3 \times 3$, из которой после упрощений получим таблицу $A_3$, показанную на рис. б. Но она вырождена: если $x = (0, 0,1)$, то $A_3 x = 0$. Получили противоречие.
Содержание этой задачи совпадает с известной специалистам теоремой из линейной алгебры (о том, что кососимметрическая матрица $n \times n$ при нечетном $n$ вырождена), которая над полем из двух элементов 0 и 1 приобретает некоторую дополнительную трудность.
Когда закончился хоккейный турнир (в один круг), оказалось, что для любой группы команд можно найти команду (может быть, из этой же группы), которая набрала в играх с командами этой группы нечетное число очков. Докажите, что в турнире участвовало четное число команд. (Поражение - 0 очков, ничья - 1 очко, выигрыш - 2 очка.)
Решение:
Заменим в таблице турнира все четные числа нулями, нечетные - единицами. Обозначим полученную таблицу через $A$, ее элементы - через $a_{ij}$ ($i, j = 1, 2, \cdots, n$): $a_{ij} = 1$, если $i$-я и $j$-я команды сыграли вничью, $a_{ij} = 0$ - в противном случае. Таблица удовлетворяет условию симметрии и на диагонали стоят нули:
$a_{ij} = a_{ji}, a_{ij} = 0$ для всех $i, j$. (1)
Требование, которое предъявляется к таблице в условии задачи, можно сформулировать так: для любого набора $x = (x_1, x_2, \cdots, x_n$) из нулей и единиц, отличного от $0 = (0, 0, \cdots, 0)$, хоть одно из чисел
$y_i = a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n$ (А)
нечетно. Для каждой группы команд мы строим набор полагая $x_j = 1$, если $j$-я команда входит в группу, и 0, если не входит, при этом $y_i$ равно количеству ничьих $i$-й команды с этой группой. Будем набор ($y_1, y_2, \cdots, y_n)$, полученный из $x$ с помощью таблицы $A$ по правилу $(A)$, обозначать $A_x$. Поскольку нас интересует лишь различие между четными и нечетными числами, удобно упростить арифметику, оставив лишь два числа 0 и 1, и считать, что $0 + 1 = 1 + 0 = 1, 1 + 1 = 0 + 0 = 0$ (правила умножения и все основные законы арифметики при этом сохраняются). Тогда у также будет набором из 0 и 1» При этом основное требование к таблице принимает вид:
если $x \neq 0$, то $y = Ax \neq 0$; (2)
такую таблицу $A$ назовем невырожденной.
Теперь, когда мы от хоккея полностью перешли к алгебре, можно приступить к решению задачи: доказать, что при нечетном $n$ условия (1) и (2) не могут одновременно выполняться. Будем упрощать нашу таблицу $A$, сохраняя эти условия.
Условие (2) не нарушится, если таблицу $A$ изменить, прибавив к первой строке вторую: если $A_x = y = (y_1, y_2, \cdots, y_n)$, то для новей таблицы $A^{ \prime}$ будет $A^{ \prime}x = y^{ \prime} = (y_1 + y_2, \cdots, у_n)$, если $у \neq 0$, то и $y^{ \prime} \neq 0$. Условие (2) не нарушится также, если к первому столбцу $A$ прибавить второй: если $A_x = y$, где $x = (x_1, x_2, \cdots x_n)$, то для новой таблицы $A^{ \prime \prime}$ будет $A^{ \prime \prime}x^{ \prime \prime} = у$, где $x^{ \prime \prime} = (x_1 + x_2, x_2, \cdots, x_n)$; если $x \neq 0$, то и $x^{ \prime \prime} \neq 0$. Разумеется, можно также прибавлять $i$-ю строку к $j$-й или $i$-й столбец к $j$-му; если сделать такие два преобразования одновременно, то новая таблица будет не только невырожденной (2), но также симметричной (1) (при этом правило $1 + 1 = 0$ сохраняет нули на диагонали).
Приступим теперь к упрощению таблицы $A$. Можно считать, что «первые две команды сыграли вничью», т. е. $a_{12} - a_{21} = 1$. Прибавляя первую строку (и первый столбец) к тем строкам (столбцам), где стоят единицы во втором столбце (соответственно строке), мы избавимся от всех этих единиц; точно так же, с помощью второй строки (и второго столбца) мы избавимся от единиц в первом столбце (и в первой строке) и получим таблицу $A_{n-2}$ такого вида, как показано на рис. а. Остающаяся после отбрасывания первых двух строк и столбцов таблица $A_{n-2}$ размера $(n - 2) \times (n - 2)$ по-прежнему удовлетворяет условиям (1) и (2): ведь $A_x \neq 0$ для любого $x = (0, 0, x_1, x_2, \cdots, x_{n-2})$, а остающаяся таблица $A_{n-2}$ преобразует координаты $(x_1, x_2, \cdots, x_{n-2})$ точно так же. Продолжая те же упрощения, переходя к таблицам $A_{n-4}, A_{n-6}, \cdots$, мы в конце концов, если $n$ было нечетно, придем к таблице $3 \times 3$, из которой после упрощений получим таблицу $A_3$, показанную на рис. б. Но она вырождена: если $x = (0, 0,1)$, то $A_3 x = 0$. Получили противоречие.
Содержание этой задачи совпадает с известной специалистам теоремой из линейной алгебры (о том, что кососимметрическая матрица $n \times n$ при нечетном $n$ вырождена), которая над полем из двух элементов 0 и 1 приобретает некоторую дополнительную трудность.
