Олимпиадная задача по комбинаторике для 9–11 классов о блицтурнире шахматистов

  Назовём шагом шахматиста количество партий между двумя его соседними играми (включая вторую из них). Тогда все шаги не меньше  n + 1.

  Рассмотрим любые  n + 3  последовательные игры  g₁, ..., g_n+3;  в них  2n + 6  участников. Заметим, что только три шахматиста могли участвовать в этих партиях дважды. Действительно, это могло произойти только в парах партий  (g₁, g_n+2),  (g₁, g_n+3)  и  (g₂, g_n+3),  и в каждой паре может быть только один такой участник (иначе два шахматиста сыграют дважды). Значит, чтобы набралось  2n + 6  участников, для каждой из пар должен найтись шахматист, участвовавший в обеих; все же остальные шахматисты должны участвовать в наших партиях по разу. Мы получили, что шаги шахматистов из партии g₁ равны  n + 1  и  n + 2.  Значит, каждый шаг равен либо  n + 1,  либо  n + 2.

  Докажем, что найдётся шахматист, все шаги которого равны  n + 2.  Тогда сумма  2n + 1  его шагов будет равна  (n + 2)(2n + 1) = 2n² + 5n + 2.  Поскольку всего игр было   (2n + 3)(2n + 2) : 2 = 2n² + 5n + 3,   это означает, что он участвовал и в первой, и в последней игре.

 Предположим противное: пусть каждый шахматист делал шаг  n+ 1.  Рассмотрим шахматистаX, который сделал первый такой свой шаг последним; пусть в результате этого шага он встретился с шахматистомYвt-й игре. ТогдаYделал шаг  n+ 1  до этого; пусть последний такой его шаг (доt-й партии) был изq-й партии в (q+n+1)-ю (см. рис.). Тогда все его последующие шаги (доt-й партии) были по  n+ 2,  поэтому  t = q+ (n+ 1) +k(n+ 2).   С другой стороны, все предыдущие шагиXбыли по  n+ 2;  поэтому, если он сделал хотя быkтаких шагов, то за  k+ 1  шаг доt-й партии он участвовал в партии с номером   t– (n+ 1) –k(n+ 2) =q;   следовательно, он встречался сYдважды. Если жеXсделал доt-й партии менее  k+ 1  шага, то его первая партия имела номер, не меньший   t– (n+ 1) – (k– 1)(n+ 2) =q+ (n+ 2) ≥n+ 3.   Этого также не может быть, так как по доказанному все шахматисты участвовали в первых  n+ 2  партиях. Противоречие.

Ответ задачи отсутствует