Четырнадцать шахматистов договорились сыграть несколько партий так, чтобы любые два шахматиста играли друг с другом не более одного раза. К некоторому моменту было сыграно 66 партий, причём каждый шахматист сыграл чётное количество партий, а один всё это время был болен, наконец-то поправился и теперь смог принять участие в турнире. Сколькими способами можно провести ещё несколько партий так, чтобы каждый шахматист сыграл нечётное число партий? Способы, отличающиеся только порядком сыгранных партий, считаются одинаковыми.

Предыдущий
вопрос Следующий
вопрос

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

Для того чтобы каждый шахматист сыграл нечетное количество партий, нам нужно добавить только одно ребро к графу каждый раз. Поскольку у нас уже сыграно 66 партий и у каждого шахматиста четное количество партий, то у каждой вершины уже есть четыре инцидентных ребра.

Таким образом, мы можем добавить еще 7 ребер (для сыгрывания 7 дополнительных партий) так, чтобы каждый шахматист сыграл нечетное количество партий. Следовательно, существует 7 способов добавить эти партии.