Занятие # 2 (16.05.2011)

• Домашнее задание:
  • Проблема: число "циклов" в турнире можно определить, зная только количество очков, набранное каждым игроком. Если вы хотите самостоятельно решить этот вопрос, советую подойти к нему основательно, за полчаса такую задачу решить трудно.

Занятие # 1 (27.04.2011)

• Домашнее задание. Попробуйте решить следующие задачи
  • Какая максимальная разница в количестве очков возможна для игроков, которые по результатам турнира находятся на соседних местах?
  • Пусть $s_1 \le \ldots \le s_n$ – очки, набранные последним, ..., первым игроком. Тогда эти числа удовлетворяют соотношениям:
    • $s_1 + \ldots + s_n = \frac{n(n-1)}{2}$
    • $s_1 + \ldots + s_k \ge \frac{k(k-1)}{2}$ при $k = 1, \ldots, n$
  • Докажите, что если целые неотрицательные числа $s_1 \le \ldots \le s_n$ удовлетворяют условиям предыдущей задачи, то существует турнир без ничьих, в котором последний набрал $s_1$ очков, ..., первый набрал $s_n$ очков. (Полезно разобрать крайний случай, когда неравенства обращаются в равества. А потом от него двигаться к всё большим отклонениям от крайнего)
  • Докажите, что если $s_1 \le \ldots \le s_n$ – целые или полуцелые неотрицательные числа, удовлетворяющие условиям, то существует соответствующий этим числам турнир с ничьими