Версия для печати
Убрать все задачи

---

На плоскости расположено [ n] прямоугольников со сторонами, параллельными осям координат. Известно, что любой прямоугольник пересекается хотя бы с n прямоугольниками. Доказать, что найдется прямоугольник, пересекающийся со всеми прямоугольниками.

   Решение

---

В блицтурнире принимали участие  2n + 3  шахматиста. Каждый сыграл с каждым ровно по одному разу. Для турнира был составлен такой график, чтобы игры проводились одна за другой, и чтобы каждый игрок после сыгранной партии отдыхал не менее n игр. Докажите, что один из шахматистов, игравших в первой партии, играл и в последней.

   Решение

Темы:    [ Турниры и турнирные таблицы ] [ Сочетания и размещения ] [ Доказательство от противного ]

Сложность: 5 Классы: 9,10,11

Прислать комментарий

Условие

В блицтурнире принимали участие  2n + 3  шахматиста. Каждый сыграл с каждым ровно по одному разу. Для турнира был составлен такой график, чтобы игры проводились одна за другой, и чтобы каждый игрок после сыгранной партии отдыхал не менее n игр. Докажите, что один из шахматистов, игравших в первой партии, играл и в последней.

Решение

  Назовём шагом шахматиста количество партий между двумя его соседними играми (включая вторую из них). Тогда все шаги не меньше  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  партиях. Противоречие.

Источники и прецеденты использования