Eight teams participated in a soccer tournament, and each pair of teams have played exactly once. It appeared that if two teams and played a draw then the resulting numbers of points of and are different. Find the greatest possible number of draws in this tournament. (Each win is worth 3 points, each draw is worth 1 point, and each lose is worth 0 points.) (S. Tokarev)
Solution
Докажем, что ровно по 6 ничьих может быть не более, чем у двух команд. Действительно, любая такая команда имеет либо 6, либо очка (в зависимости от того, выиграла или проиграла она свой результативный матч). Если таких команд три, то у двух из них поровну очков, значит, между собой они сыграли не вничью; этого не может быть, ибо они обе либо не выигрывали, либо не проигрывали ни одного матча.
Также ясно, что максимум одна команда все свои 7 матчей сыграла вничью.
Таким образом, сумма количеств ничьих у всех 8 команд не превосходит , а поскольку каждый ничейный матч учитывается дважды, то общее число ничьих в турнире не превосходит . Оно может равняться 22, что показано на рисунке (команды обозначены буквами A, B, C, D, E, F, G и H).
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.