Задача 035 — Задачи на Графы

10 команд играют турнир. В некоторый момент оказалось, что любые две команды сыграли между собой не более, чем по одному разу, только «»Металлург»» и «»Локомотив»» сыграли дважды. При этом каждая команда сыграла хотя бы один матч. Могло ли так случиться, что в этот момент все команды сыграли различное число игр?

Подсказка

Допустим, есть команда, не сыгравшая ни одного матча. Тогда каждая из оставшихся команд сыграла не больше 9 матчей: с каждой из остальных восьми плюс один повторный.

Решение

Ответ: Нет. Решение. Допустим, есть команда, не сыгравшая ни одного матча. Тогда каждая из оставшихся команд сыграла не больше 9 матчей: с каждой из остальных восьми плюс один повторный. Получается 9 возможностей $(1,2, \ldots, 9$ матчей) на 19 команд. Но тогда эти команды вместе сыграли $(1+2+\ldots+9) / 2=22,5$ матчей, что невозможно.

Теперь допустим, что каждая команда сыграла хотя бы один матч. Тогда для числа сыгранных матчей получается 10 возможностей $(1,2, \ldots, 10$ матчей) на 10 команд. Но тогда эти команды вместе сыграли $(1+2+\ldots+10) / 2=27,5$ матчей, что также невозможно.