Республиканская олимпиада по математике, 2001 год, 9 класс

Чемпионат среди $n$ футбольных команд организован так, что любые две команды встречаются между собой ровно один раз. Каждый матч проходит в воскресный день, и каждая команда играет не более одного раза в день. Какое наименьшее количество воскресных дней понадобится, чтобы завершить чемпионат?

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

$n(n-1)/2$ = общее количество проводимых матчей.

За одно воскресенье можно отыграть не больше $(n/2)$ или $((n-1)/2)$ матчей при четном или нечетном $n$ соответственно.Иначе, найдется такая команда которому придется отыграть еще один матч за день. Следовательно, всего нам для оканчания чемпионата понадобится $(n-1)/2$ или $n/2$ воскресных дней при четном или нечетном $n$ соответственно.

Каждая команда должна сыграть $n-1$ раз, но в день любая команда играет не более $1$ раза в день, $\Rightarrow$ воскресных дней тоже хотя бы $n-1$, поэтому $(n-1)/2$ - неточная оценка