Задача 2.1. Судьи теннисного турнира

Сколько матчей сыграно при 10 игроках

Каждый из $10$ игроков сыграл с каждым из остальных $9$. Выпишем для каждого игрока список его соперников — получится $10\cdot9=90$ записей. Но каждый матч попал в списки дважды: матч игроков $1$ и $2$ есть и у игрока $1$, и у игрока $2$. Поэтому матчей вдвое меньше:

Проверим способ на турнире из $4$ игроков: $4\cdot3:2=6$, и правда — это матчи $1\text{–}2$, $1\text{–}3$, $1\text{–}4$, $2\text{–}3$, $2\text{–}4$, $3\text{–}4$.

То же видно в турнирной таблице (рисунок ниже). Над диагональю в строке $1$ стоят $9$ клеток — матчи игрока $1$ с игроками $2, 3, \ldots, 10$; в строке $2$ — ещё $8$ новых матчей, и так далее до строки $9$ с одним матчем $9\text{–}10$. Всего $9+8+\ldots+1=45$.

Зачем считать матчи: в каждом матче ровно один судья, поэтому число матчей — это и число всех судейств, которые надо раздать участникам.

Пункт а): 45 судейств на 10 человек

Запишем для каждого из $10$ участников, сколько матчей он судил, и сложим эти числа. Каждый матч попадёт в эту сумму ровно один раз — у своего судьи. Значит, сумма равна числу матчей, то есть $45$, как бы ни распределили судейство.

Пусть все судили поровну — каждый по $k$ матчей. Тогда сумма равна $10\cdot k$. Но произведение $10\cdot k$ оканчивается нулём, а $45$ — пятёркой, поэтому равенство $10\cdot k=45$ невозможно ни при каком целом $k$. Иначе говоря, поровну пришлось бы по $45:10=4{,}5$ матча на человека, а судить полматча нельзя.

Ответ на пункт а): не могло.

Пункт б): подсчёт не мешает, но нужен пример

При $9$ игроках матчей $9\cdot8:2=36$, и поровну выходит $36:9=4$ матча на каждого: подсчёт из пункта а) теперь не мешает. Но это ещё не ответ: делимость лишь не запрещает равенство — нужен ещё пример. Условие так и требует: привести расписание, то есть для каждого из $36$ матчей назвать судью, который в нём не играет, так, чтобы у всех вышло ровно по $4$.

Как придумать такое расписание? Подбирать судей наугад для $36$ матчей долго, и легко запутаться. Хочется, чтобы все игроки были в одинаковом положении: тогда и судейств у всех будет поровну. Посадим игроков по кругу на равных расстояниях, как цифры на циферблате, и пронумеруем по часовой стрелке от $1$ до $9$. Правило выбора судьи сформулируем только через места на круге — тогда оно одинаково для всех.

Правило: судит тот, кто сидит посередине

Возьмём любой матч. Остальные $7$ игроков сидят на двух дугах между соперниками: одни встретятся, если идти от одного соперника к другому по часовой стрелке, другие — если идти против. Число $7$ нечётное, поэтому на одной дуге игроков нечётное число, а на другой — чётное (там может не оказаться никого: ноль — тоже чётное число). На «нечётной» дуге есть ровно один игрок посередине — он и судит этот матч.

Два примера (рисунок ниже):

• матч $1\text{–}5$: на одной дуге игроки $2, 3, 4$ — трое, на другой $6, 7, 8, 9$ — четверо. Судит средний из трёх — игрок $3$;
• матч $1\text{–}2$: на одной дуге никого нет, на другой семеро — с $3$-го по $9$-й. Судит средний из семи — игрок $6$.

Такой судья есть у каждого матча, и он один: «нечётная» дуга одна, и середина у неё одна. В своём матче он не играет — он сидит строго между соперниками. И он одинаково далёк от обоих: в первом примере игрок $3$ отстоит на $2$ места и от игрока $1$, и от игрока $5$.

Как до этого догадаться: судья должен быть беспристрастным, а на круге беспристрастнее всех тот, кто одинаково далеко от обоих соперников.

Почему каждый судит ровно 4 матча

Посмотрим на игрока $1$. Какие матчи он судит? Те, в которых он сидит посередине, то есть соперники отстоят от него на одинаковое число мест по разные стороны. По каждую сторону от игрока $1$ всего $4$ места, поэтому таких пар ровно четыре: $9$ и $2$ — по одному месту, $8$ и $3$ — по два, $7$ и $4$ — по три, $6$ и $5$ — по четыре.

Проверим, что каждую из этих пар действительно судит игрок $1$. Дуга между соперниками, которая проходит через игрока $1$, содержит $1$, $3$, $5$ или $7$ игроков — нечётное число, и игрок $1$ ровно в её середине. Значит, игрок $1$ судит ровно $4$ матча: $9\text{–}2$, $8\text{–}3$, $7\text{–}4$, $6\text{–}5$. На рисунке это четыре параллельных отрезка, перпендикулярных пунктирной оси через игрока $1$.

Для любого другого игрока рассуждение такое же: с любого места круг выглядит одинаково. Значит, каждый из $9$ игроков судит ровно $4$ матча, а всего судейств $9\cdot4=36$ — столько же, сколько матчей.

Всё расписание

Так же, как для игрока $1$, выпишем матчи каждого судьи — пары, которые сидят от него на одинаковом числе мест по разные стороны:

В таблице $9\cdot4=36$ записей, и все они — разные матчи: у каждого матча ровно один игрок посередине, поэтому матч попадает ровно в одну строку. Значит, здесь все $36$ матчей турнира, у каждого есть судья, который в нём не играет, и каждый участник судит ровно $4$ матча.

Ответ на пункт б): да, ответ изменится — при $9$ игроках такое расписание существует.