Турниры

Занятие # 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\) – целые или полуцелые неотрицательные числа, удовлетворяющие условиям, то существует соответствующий этим числам турнир с ничьими