Олимпиада имени Леонарда Эйлера2008-2009 учебный год, II тур регионального этапа

В футбольном турнире участвовало 8 команд, причем каждая сыграла с каждой ровно по одному разу Известно, что любые две команды, сыгравшие между собой вничью, набрали в итоге разное число очков. Найдите наибольшее возможное общее число ничьих в этом турнире. (За выигрыш матча команде начисляется 3 очка, за ничью — 1, за поражение — 0.) ( С. Токарев )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. 22.
Решение. Докажем, что ровно по 6 ничьих может быть не более, чем у двух команд. Действительно, любая такая команда имеет либо 6, либо $6 + 3$ очка (в зависимости от того, выиграла или проиграла она свой результативный матч). Если таких команд три, то у двух из них поровну очков, значит, между собой они сыграли не вничью; этого не может быть, ибо они обе либо не выигрывали, либо не проигрывали ни одного матча. Также ясно, что максимум одна команда все свои 7 матчей сыграла вничью. Таким образом, сумма количеств ничьих у всех 8 команд не превосходит $7 + 6 + 6 + 5 + 5 + 5 + 5 + 5 = 44$, а поскольку каждый ничейный матч учитывается дважды, то общее число ничьих в турнире не превосходит 44/2 = 22. Оно может равняться 22, как показано в таблице ниже.