Математики выяснили, что на спортивных чемпионатах в любом круговом турнире с как минимум пятью участниками найдется ни на что не влияющий матч. Результат своих исследований Марко Фаэлла и Луиджи Сауро из Неаполитанского университета имени Фридриха II обнародовали на 17-й Международной конференции по автономным агентам и многоагентным системам и опубликовали в итоговых материалах конференции, пишет nplus1.
В последнем туре розыгрыша Единой баскетбольной лиги ВТБ сезона 2017/2018 годов состоялся матч "Нижний Новгород" - "Локомотив-Кубань" (92:86). Результат этого матча ни на что не повлиял: если бы он завершился с любым другим счетом, то "Нижний Новгород" все равно остался бы на седьмом месте, а "Локомотив-Кубань" - на третьем. "Локомотив-Кубань" в случае победы не смог бы обойти впереди стоящие команды. Чтобы убедиться в этом, достаточно посмотреть на итоговую турнирную таблицу Лиги без учета этой единственной игры.
Фото: dl.acm.org
Такие матчи, как "Нижний Новгород" - "Локомотив-Кубань", Фаэлла и Сауро называют бессмысленными. Очевидно, что организаторы турнира хотели бы избежать бессмысленных матчей. Но возможно ли это сделать?
Ученые ограничиваются рассмотрением видов спорта, в которых каждый матч заканчивается победой одной из команд (например, к таким видам относятся баскетбол и волейбол). Рассматриваются соревнования по круговой системе, то есть каждая команда играет с каждой по одному разу. Ранжирование команд происходит по числу побед. Что касается стимулов команд, то будем считать, что каждая команда хотела бы занять как можно более высокое место.
В соревновании важную роль играет календарь, определяющий последовательность игр. Обычно на практике календарь фиксируется перед началом соревнования. Предположим, что все игры происходят последовательно (это предположение часто выполняется: телевидение заинтересовано в том, чтобы никакие игры не пересекались).
Турниром называется дерево, в котором каждая вершина соответствует матчу, каждое исходящее ребро соответствует одному из двух возможных результатов соответствующего матча, а каждый путь от корневой вершины до терминальной вершины определяет последовательность матчей и соответствует одному из вариантов полного заполнения турнирной таблицы. Рассмотрим произвольный матч М между командами a и b. Формально матч М называется значимым для команды a, если существует хотя бы один вариант развития следующих за М матчей, при котором команда a в случае победы и в случае поражения в матче М окажется на разных местах по итогам чемпионата. Если матч не является значимым ни для одной из играющих команд, то он называется бессмысленным. Турнир называется значимым в строгом (соответственно, слабом) смысле, если все матчи турнира значимы для обеих участвующих команд (соответственно, хотя бы для одной команды).
Если М - последняя игра чемпионата, то мы получаем ситуацию из матча "Нижний Новгород" - "Локомотив-Кубань", описанную выше. Если М - матч в середине турнира, то существует много вариантов развития событий в оставшихся матчах. Для бессмысленности матча М необходимо, чтобы при любом возможном раскладе в оставшихся матчах матч М уже не мог бы изменить место играющих в матче М команд.
Фаэлла и Сауро доказывают три основных результата. Во-первых, авторы работы демонстрируют, что для любого числа участников турнира N ≥ 5 при фиксированном расписании турнир будет содержать бессмысленные матчи. Идея построения такого матча проста. Рассмотрим развитие событий, при котором в последнем матче турнира встречаются команды a и b, причем команда a выиграла, а команда b проиграла все предыдущие матчи. Кроме того, предположим, что все остальные команды обыгрывали друг друга по кругу так, что все они выиграли примерно половину матчей. Тогда команда aнезависимо от исхода последнего матча займет первое место, а команда b - последнее. Таким образом, матч между a и b будет бессмысленным. А вот если N ≤ 4, то турнир будет значимым в строгом смысле.
При этом оказывается, и это второй важный результат работы, что возможность динамически обновляемого в зависимости от результатов игр расписания позволяет добиться того, что турнир будет значимым в слабом смысле (то есть каждая игра будет значимой по крайней мере для одной из команд). Авторы строят подходящее расписание турнира рекурсивным способом. Недостаток построенного расписания состоит в том, что матчи команды могут быть распределены неравномерно вдоль турнирной дистанции, поэтому воплотить это расписание в жизнь будет проблематично.
Существует ли динамически обновляемое расписание, которое позволяет получить значимый турнир в строгом смысле для произвольного достаточно большого числа команд? Этот вопрос остается открытым. Однако Фаэлла и Сауро доказывают, что если такое расписание и существует, то при N ≥ 6 оно точно не будет сбалансированным, то есть оно не будет разбиваться на туры, в которых каждая команда проводит по одному матчу.
Ранее "Страна" сообщала, что математики из Австрии вычислили фаворитов ЧМ - 2018.