ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73695
Темы:    [ Турниры и турнирные таблицы ]
[ Числовые таблицы и их свойства ]
[ Метод спуска ]
[ Линейная и полилинейная алгебра ]
[ Симметрия и инволютивные преобразования ]
[ Четность и нечетность ]
Сложность: 5+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Когда закончился хоккейный турнир (в один круг), оказалось, что для каждой группы команд можно найти команду (может быть, из той же группы), которая набрала в играх с командами этой группы нечётное число очков. Докажите, что в турнире участвовало чётное число команд. (Поражение – 0 очков, ничья – 1 очко, выигрыш – 2 очка.)


Решение

  Пусть число команд равно N. Представим сначала результаты турнира в виде турнирной таблицы N×N. На пересечении i-й строки и j-го столбца поставим число aij очков, набранных i-й командой в матче с j-й командой. Будем считать, что команда в матче "с самой собой" набрала 0 очков, то есть на диагонали будут стоять нули.
  Заметим, что  aij + aji = 2  при  i ≠ j.
  Каждой команде в турнирной таблице соответствуют строка и столбец. Число очков, набранных i-й командой в матчах с группой команд с номерами  j1, ...,  jk,  равно  aij1 + ... + aijk.
  Теперь мы можем сформулировать по-новому задачу на языке таблиц.
  Пусть квадратная таблица N×N, состоящая из целых чисел aij, удовлетворяет следующим двум условиям:
  1) все числа aii, стоящие на её диагонали, чётны, и сумма aij + aji каждых двух чисел, симметричных относительно этой диагонали, тоже чётна;
  2) для каждой группы столбцов найдётся такая строка, что сумма чисел на пересечении этой строки со столбцами этой группы нечётна.
Нужно доказать, что N чётно.
  Допустим, что существует таблица N×N с нечётным N, удовлетворяющая условиям 1) и 2).
  Заменим все чётные числа в таблице на 0, а нечётные – на 1. В полученной таблице условия 1) и 2) также выполнены.
  Введём следующие преобразования таблиц.
  Преобразование I. Меняем местами i-ю строку с j-й и i-й столбец с j-м.
  Преобразование II. i-й столбец заменяем на сумму i-го и j-го столбцов (по модулю 2), а затем i-ю строку на сумму i-й и j-й строк.
  Заметим, что указанные преобразования сохраняют свойства 1) и 2). Для преобразований I это очевидно. Докажем это для преобразования II.
  Если рассматриваемая группа столбцов не содержит i-го столбца и можно указать k-ю строку, удовлетворяющую условию 2), где  k ≠ i,  то и после преобразования k-я строка будет ему удовлетворять.
  Если же эту группу столбцов обслуживает только i-я строка, то для j-й строки соответствующая сумма чётна. Тогда в преобразованной таблице сумма для i-й строки по-прежнему нечётна.
  Пусть i-й столбец входит в рассматриваемую группу. Если в нее не входит j-й столбец, то надо взять строку, "обслуживающую" группу, пополненную j-м столбцом, а если входит, то, наоборот, его надо убрать.
  Рассмотрим последний, N-й столбец этой таблицы. Согласно свойству 2) для него найдётся такая строка, что на их пересечении стоит единица:  akN = 1  и, следовательно,  aNk = 1. 
  Сделаем теперь преобразование I: поменяем местами k-ю строку с (N–1)-й и k-й столбец с (N–1)-м.
  В результате таблица будет иметь следующий вид:

A =  .
  Применив теперь несколько раз преобразование II (используя два крайних столбца и две крайние строки), мы можем привести таблицу к такому виду:
A =  .
  Вычеркнув из этой таблицы последние два столбца и последние две строки, мы получим новую таблицу  (N–2)×(N–2),  удовлетворяющую условиям 1) и 2).
 Из полученной таблицы  (N–2)×(N–2)  аналогично получим таблицу  (N–4)×(N–4),  и так далее. В конце концов мы получим таблицу 1×1, удовлетворяющую условиям 1) и 2). Этого, однако, не может быть, так как для таблицы 1×1 оба условия одновременно не выполняются. Противоречие.

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1972
выпуск
Номер 8
Задача
Номер М160

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .