Возможно ли в турнире по круговой системе провести такой момент, когда каждый из девяти шахматистов сыграет ровно
Возможно ли в турнире по круговой системе провести такой момент, когда каждый из девяти шахматистов сыграет ровно три партии? В учебнике ответили, что нет. Можете ли вы объяснить это?
25.11.2023 12:13
Пояснение: В турнире по круговой системе каждый участник играет с каждым другим участником ровно один раз. В данной задаче у нас есть 9 шахматистов, и каждый из них должен сыграть ровно 3 партии.
Предположим, что это возможно. Тогда каждый шахматист должен встретиться с остальными 8 шахматистами по одному разу. Поскольку каждая игра требует двух участников, общее количество партий, которые должны быть сыграны, равно 9 участников умножить на 3 партии на каждого участника, что дает нам 27 партий.
Однако, если мы посчитаем количество возможных партий, то мы заметим, что каждая партия учитывается дважды (например, игра между игроком A и игроком B учитывается в обоих игроках), что значит, что количество партий должно быть делится на 2 без остатка. В нашем случае, 27 партий не делится на 2 без остатка, поэтому это невозможно провести в турнире по круговой системе.
Совет: Чтобы понять почему это невозможно, можно представить участников турнира в виде вершин графа, а партии между участниками в виде ребер. Таким образом, наш вопрос сводится к тому, есть ли эйлеров цикл (цикл, который проходит через каждое ребро графа ровно один раз) в данном графе. Поняв это, мы видим, что в данном случае, количества ребер (партий) недостаточно, чтобы построить эйлеров цикл и удовлетворить всем условиям задачи.
Задача на проверку: Сколько партий будет сыграно в турнире по круговой системе, если в нем будет участвовать 12 шахматистов?