Олимпиадная задача по комбинаторике для 9–11 классов о блицтурнире шахматистов
В блицтурнире принимали участие 2n + 3 шахматиста. Каждый сыграл с каждым ровно по одному разу. Для турнира был составлен такой график, чтобы игры проводились одна за другой, и чтобы каждый игрок после сыгранной партии отдыхал не менее n игр. Докажите, что один из шахматистов, игравших в первой партии, играл и в последней.
Разобрать решение
Назовём шагом шахматиста количество партий между двумя его соседними играми (включая вторую из них). Тогда все шаги не меньше n + 1.
Рассмотрим любые n + 3 последовательные игры g1, ..., gn+3; в них 2n + 6 участников. Заметим, что только три шахматиста могли участвовать в этих партиях дважды. Действительно, это могло произойти только в парах партий (g1, gn+2), (g1, gn+3) и (g2, gn+3), и в каждой паре может быть только один такой участник (иначе два шахматиста сыграют дважды). Значит, чтобы набралось 2n + 6 участников, для каждой из пар должен найтись шахматист, участвовавший в обеих; все же остальные шахматисты должны участвовать в наших партиях по разу. Мы получили, что шаги шахматистов из партии g1 равны 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 партиях. Противоречие.
Обсуждение
0Комментариев пока нет.