|
|
 |
Условие
В однокруговом футбольном турнире играли n > 4 команд. За победу давалось 3 очка, за ничью 1, за проигрыш 0. Оказалось, что все команды набрали поровну очков.
а) Докажите, что найдутся четыре команды, имеющие поровну побед, поровну ничьих и поровну поражений.
б) При каком наименьшем n могут не найтись пять таких команд?
Решение
а) Если две команды набрали поровну очков, то разность между количествами ничьих у них кратна 3. Количество ничьих у команды находится в пределах от 0 до n – 1. Поэтому количество групп, в каждой из которых команды имеют поровну выигрышей, ничьих и поражений, не
превосходит Значит, найдется такая группа, состоящая не менее чем из
трёх команд.
Предположим, что все группы состоят из трёх или менее команд. Тогда
групп ровно k (иначе n < 3k – 2 и ). Рассмотрим группы A и B с наименьшим и наибольшим количеством ничьих.
Если n = 3k – 2, то у команд из A количество ничьих равно 0, а у команд из B – 3k – 3 = n – 1. Значит, команды из B свели вничью все игры, в том числе с командами из A, у которых ничьих нет. Противоречие.
Если n = 3k – 1 и у команд из A по l ничьих, то у команд из B по l + 3k – 3 ничьих, то есть по 1 – l результативных встреч. Если l = 1, то B может содержать только одну команду, так как две команды сыграли бы вничью с командой из A, у которой только одна ничья. Если же l = 0, то из A может содержать лишь одну команду, так как две команды имели бы результативную игру с командой из B, у которой результативная игра только одна. Таким образом, одна из этих групп содержит лишь одну команду. Но тогда оставшиеся команды нельзя разбить на k – 1 группу, каждая из которых содержит не более трёх команд.
Если n = 3k, то все группы должны содержать ровно по три команды. При этом если у команд из A по l ничьих, то у команд из B по 2 – l результативных игр. Поэтому друг против друга команды этих групп проводят не более чем 3l + 3(2 – l) = 6 игр. Противоречие.
б) Пример. Ниже приведена таблица турнира из 10 команд, три из которых имеют по одной победе и 8 ничьих, четыре – по 2 победы, 2 поражения и 5 ничьих, и еще три – по 3 победы, 4 поражения и 2 ничьих.
Оценка. Так как не все команды имеют поровну побед, ничьих и поражений, найдутся команды, которые выиграли больше встреч, чем проиграли, и команды, которые проиграли больше, чем выиграли. Предположим сначала, что в каждой из этих групп команд количества побед и поражений отличаются на 1, то есть в одной группе команды одержали x побед, потерпели x – 1 поражение и n – 2x встреч завершили вничью, а в другой эти числа равны соответственно y –1, y и n –2. Тогда, приравнивая набранные командами очки, получаем, что x = y – 3. Так как n – 2y ≥ 0, то n – 2x ≥ 6, а поскольку x ≥ 1, получаем, что n = 8.
Пусть теперь есть команды, у которых разность между количеством побед и
поражений по модулю больше 1. Аналогичные рассуждения показывают, что существуют команды, завершившие вничью по крайней мере 9 встреч.
Таким образом, неравенство n ≥ 8 выполнено всегда, а случай n < 10 возможен, только когда разность между количеством побед и поражений у каждой команды по модулю не превышает 1.
Предположим, что n = 8. Как показано выше, есть k команд, у которых побед на одну больше, чем поражений, l команд, у которых побед на одну меньше, чем поражений, и 8 – k – l команд, у которых побед и поражений поровну. При этом k = l, поскольку общее количество побед равно количеству поражений. Кроме того, количество ничьих у команд первой группы на 6 больше, чем у команд второй. Это возможно в единственном случае, когда эти команды имеют одну победу и 6 ничьих. Соответственно, у команд второй группы по 3
победы и 4 поражения. Команды первой группы против команд второй проводят k² встреч, среди которых нет ничейных (команды второй
группы вничью не играли) и не больше чем k результативных (по
одной на каждую команду первой группы). Значит, k² ≤ k, то есть k = 1 и 8 – 2k = 6.
Аналогично доказывается, что k ≤ 2 при n = 9, и n – 2k = 9 – 2k > 4.
Ответ
б) При n = 10.
