20
КВАНТ 2016/№4
Футбольные турниры и арифметические прогрессии
В 2012 году на LXXV Московской математической олимпиаде была предложена следующая задача. В однокруговом футбольном турнире (победа – 3 очка, ничья – 1, поражение – 0) участвовали 75 команд. Каков минимально возможный разрыв в очках между первой и последней командами, если никакие две команды не набрали поровну очков? Поскольку минимальный разрыв между командами, занявшими соседние места, равен одному очку, очевидно, что разрыв между первой и последней командами не может быть меньше 74 очков. Однако понять, достижима ли эта оценка, довольно сложно. Чтобы это выяснить, естественно для начала рассмотреть турниры с небольшим числом участников. Перебрав все турниры с 2 или 3 участниками, легко убедиться, что искомых среди них нет. Но для 4 команд такой турнир построить удается (табл.1).
Таблица 1
Успешными оказываются попытки и при нескольких следующих значениях числа команд n. Поэтому возникает предположение, что соответствующие турниры существуют для всех n > 3. Это действительно так, точнее, верно следующее утверждение. Для любого существует круговой турнир из n команд, в котором команды набирают n – 2, n – 1, n, …, 2n – 3 очков. Докажем его по индукции. Для n = 4 искомый турнир мы уже построили. Предположим, что у нас есть такой турнир для n команд, и покажем, как добавить к нему одну новую команду. Упорядочим старые команды по убыванию очков и пусть новая команда выигрывает у первой, проигрывает второй и третьей, выигрывает у четвертой, проигрывает пятой и шестой и т.д. (с периодом 3), пока ей не останется сыграть с одной, двумя или тремя командами (в зависимости от остатка n при делении на 3). В первом случае новая команда играет с последней вничью. Во втором – играет вничью с предпоследней и проигрывает последней, в третьем – играет вничью с последней, проигрывает предпоследней и выигрывает у третьей с конца. Непосредственным вычислением убеждаемся, что во всех трех случаях получится нужное нам распределение очков.
натуральных d набранные командами очки могут образовать арифметическую прогрессию с разностью d? Для полноты можно позволить d быть равным 0, и тогда нужный турнир, очевидно, существует (например, если все игры заканчиваются вничью). При всех n возможен случай d = 3 (если первая команда выигрывает у всех, вторая – у всех, кроме первой, и т.д.). Ясно также, что больше 3 разность быть не может (почему?). Таким образом, далее нам остается исследовать случай d = 2. Начнем опять с малых значений n. При n = 2 и n = = 3 искомых турниров нет, при n = 4 есть (табл.2).
Таблица 2
Но при n = 5 построить турнир не получается. Докажем, что это действительно невозможно. Если набранные очки образуют арифметическую прогрессию с разностью 2, то их сумма делится на 5. Поскольку общее количество игр в турнире пяти команд равно десяти, получаем, что сумма набранных очков равна 30, если все игры завершились победой одной из команд, а каждая ничья уменьшает эту сумму на 1. Следовательно, вничью должно завершиться 0, 5 или 10 игр. Если ничьих нет, то количество очков у каждой команды кратно 3 и разность 2 невозможна, а при 10 ничьих все команды набирают по 4 очка. Рассмотрим случай 5 ничьих. Тогда общая сумма равна 25, т.е. команды должны набрать 9, 7, 5, 3 и 1 очко. Но набрать в четырех играх 9, 7, 5 и 1 очко можно единственным способом: соответственно, три победы и одно поражение; две победы, одна ничья и одно поражение; одна победа, две ничьи и одно поражение; одна ничья и три поражения. Так как суммарное количество побед должно равняться суммарному количеству поражений, у оставшейся команды побед и поражений должно быть поровну, что при 3 очках невозможно. Продолжив рассматривать малые значения n, убеждаемся, что при n = 6, n = 7 и n = 8 искомые турниры существуют (табл. 3, 4, 5).
Таблица 3
Упражнение 1. Проверьте это.
Теперь обобщим задачу и поставим следующий вопрос. М2419. В однокруговом футбольном турнире участвует n команд. За победу команда получает 3 очка, за ничью – 1 очко, за поражение – 0 очков. При каких
Поэкспериментировав еще с несколькими значениями n, можно сформулировать следующую гипотезу. 1) При всех четных n = 2m, , существует турнир, в котором команды набирают m – 1, m + 1, m + 3, …, 5m – 3 очков.
21
ЗАДАЧНИК
«КВАНТА»
Таблица 4
Таблица 5
Таблица 7
Операцию добавления двух команд можно провести для любого нечетного n. Пусть все старые команды, кроме двух последних, набирают против новых по 3 очка, а две последние – по одному, причем если остаток от деления n на 3 равен 0 или 2, то обе эти команды набирают свои очки против одной из новых команд, а если 1, то против разных команд. Тогда можно распределить очки между новыми командами так, что одна из них окажется на первом месте, а другая – на третьем с конца.
Упражнение 3. Докажите это.
- При всех нечетных , существует турнир, в котором команды набирают m – 1, m + + 1, m + 3, …, 5m – 1 очков. Докажем, что это действительно так. Начнем с четного случая. Поскольку мы уже построили турниры для 4, 6 и 8 команд, достаточно показать, как добавить к турниру 2k команд шесть новых команд. Пусть каждая из верхних k старых команд проигрывает первой новой команде и выигрывает у остальных пяти новых, а каждая из нижних k старых, наоборот, выигрывает у первой новой команды и проигрывает остальным пяти новым. Между собой новые команды играют, как в примере для 6 команд. Нетрудно убедиться, что в результате получится нужное распределение очков.
Упражнение 2. Сделайте проверку.
Перейдем к нечетному случаю. Для начала покажем, как добавить к турниру из семи команд еще две. Пусть новые команды играют со старыми так, как показано в таблице 6 (в верхней строчке очки, набранные старыми командами в играх между собой).
Таблица 6
Тогда у старых команд становится 17, 15, 13, 11, 9, 5 и 3 очка, а у новых – 19 и 4 очка. Если теперь первая новая команда A проиграет команде B, то получится искомый турнир для 9 команд. Добавим теперь к этому турниру еще две команды (табл.7). И опять пусть первая новая команда C проигрывает второй новой команде D. В результате получаем искомый турнир 11 команд.
Однако, поскольку у нас уже есть турниры для 7, 9 и 11 команд, проще действовать аналогично четному случаю и добавлять к турниру для 2k + 1 команды еще шесть новых команд. Пусть каждая из верхних k старых команд проигрывает первой новой команде и побеждает остальных, а каждая из k нижних, наоборот, выигрывает у первой новой и проигрывает пяти остальным. Наконец, пусть средняя старая команда проигрывает первым трем новым и выигрывает у трех остальных новых. Между собой новые команды пусть сыграют так, как показано в таблице 8.
Таблица 8
В результате получаем нужное распределение очков. Утверждение полностью доказано.
Упражнение 4. Убедитесь в этом.
Теперь можно подвести итог и дать полный ответ на поставленный вопрос: при d = 0 и d = 3 искомый турнир существует для всех n, при d = 1 – для всех n, кроме 2 и 3, при d = 2 – для всех n, кроме 2, 3 и 5. В заключение предлагаем подумать над тем, как изменится ответ, если вместо футбольных рассматривать турниры по другим видам спорта, например по волейболу, где при победе одной из команд со счетом 3:0 или 3:1 выигравшая и проигравшая команды получают 3 и 0 очков соответственно, а при счете 3:2 – 2 и 1. А.Заславский