Задача 35181

Темы:    [ Принцип Дирихле (прочее) ] [ Деление с остатком ] [ Перестановки и подстановки (прочее) ] [ Четность и нечетность ]

Сложность: 4 Классы: 8,9,10

Условие

За круглым столом совещались 2n депутатов. После перерыва эти же 2n депутатов расселись вокруг стола, но уже в другом порядке.
Доказать, что найдутся два депутата, между которыми как до, так и после перерыва сидело одинаковое число человек.

Подсказка

Каждому депутату сопоставьте количество мест, на которые он сдвинулся по часовой стрелке после перерыва.
Если условие задачи не выполняется, то все эти числа должны быть различны.

Решение

  Занумеруем депутатов числами  1, 2, ..., 2n  в том порядке (по часовой стрелке), в котором они сидели до перерыва; таким же образом пронумеруем места за столом. Обозначим через a_i количество мест, на которое сдвинулся i-й депутат по часовой стрелке после перерыва. Таким образом, каждое из чисел  a₁, a₂, ..., a_2n  принимает некоторое значение из множества  {0, 1, ..., 2n – 1}.
  Если некоторые два депутата сдвинулись после перерыва на одинаковое число мест, то между ними как до, так и после перерыва сидело одинаковое число человек, то есть утверждение задачи выполнено.
  В противном случае числа  a₁, a₂, ..., a_2n  образуют перестановку чисел  0, 1, ..., 2n – 1.  Число  i + a_i  сравнимо по модулю 2n с номером места, на которое сел после перерыва i-й депутат. Поскольку после перерыва каждое из 2n мест снова занято одним из депутатов, сумма  (1 + a₁) + (2 + a₂) + ... + (2n + a_2n)  сравнима по модулю 2n с суммой номеров всех мест  1 + 2 + ... + 2n.  Отсюда следует, что сумма  a₁ + a₂ + ... + a_2n  делится на 2n. Однако
a₁ + a₂ + ... + a_2n = 0 + 1 + 2 + ... + (2n – 1) = n(2n – 1),  что не делится на 2n. Противоречие.

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

web-сайт

задача