Question

На полке стоит собрание сочинений Ленина в 55 томах, расставленных в про- извольном порядке. Библиотекарь каждый ход берёт произвольный том, стоящий не на свойм месте, и перемещает его так, чтобы он стоял на своём месте (при этом другие книги могут сдвигаться, не меняя порядок друг относитльно друга). Докажите, что рано или поздно все книги окажутся одновременно на своих местах.

Answer 1

Пхпхпхпхп
Если что перестановки программа первого курса)))

Answer 2

Эта задача является примером принципа Дирихле, который утверждает, что если n+1 объектов размещаются в n контейнерах, то какой-то контейнер обязательно будет содержать хотя бы два объекта.

В данной задаче, каждый "ход" библиотекаря может быть рассмотрен как размещение тома (объекта) в контейнере (позиция на полке). Изначально, все книги находятся вне своих мест, поэтому ни одна книга не стоит на своем месте. Теперь рассмотрим ситуацию, когда библиотекарь делает ход и перемещает том на своё место. После этого хода, этот том стоит на своем месте, но как минимум один другой том стоит не на своем месте.

Продолжая эту логику, на каждом ходе, когда библиотекарь ставит один том на своё место, как минимум один другой том перестаёт стоять на своём месте. Так как всего 55 томов, и каждый ход меняет местами как минимум два тома, мы не можем продолжать так делать больше, чем 55 раз. После 55 ходов каждая книга будет стоять на своем месте.

Итак, с использованием принципа Дирихле, мы можем заключить, что рано или поздно все книги окажутся одновременно на своих местах.