Задача 096

Построим ориентированный граф, вершинами которого будут числа от 1 до 100 , а каждое из ребер связывает номер места, на котором стоит том с данным номером, с самим этим номером. Поскольку из каждой вершины этого графа выходит ровно одно ребро, и в каждую его вершину входит ровно одно ребро, все его вершины и ребра разбиваются на непересекающиеся ориентированные циклы.

Ответ: 148.

Решение. Пример на 148. Построим ориентированный граф, вершинами которого будут числа от 1 до 100 , а каждое из ребер связывает номер места, на котором стоит том с данным номером, с самим этим номером. Поскольку из каждой вершины этого графа выходит ровно одно ребро, и в каждую его вершину входит ровно одно ребро, все его вершины и ребра разбиваются на непересекающиеся ориентированные циклы. Цикл, в который входит красный том, назовем особым, прочие — обычными. Возьмем любой обычный цикл и добавим в него красный том (пусть его номер равен ): . Затем последовательно поменяем местами красный том со всеми остальными элементами получившегося цикла. В итоге все элементы исходного обычного цикла встанут на предписанные им места, а красный том вернется на исходное место. Проделаем описанную процедуру со всеми обычными циклами длины, не меньшей 2 , а напоследок «прокрутим» особый цикл, после чего все тома окажутся на своих местах, т.е. будут идти в порядке возрастания. При этом на приведение в порядок каждого цикла длины , кроме особого, у нас ушла перестановка, а на особый цикл — перестановка, а всего — перестановки, где — число циклов длины не меньше 2 . Поскольку циклов длины 2 и больше не более 50, мы совершили не больше 148 перестановок. Оценка. Пусть получилось 50 циклов длины 2. На приведение в порядок каждого обычного цикла нужно минимум 3 перестановки: убрать один том, поставить на его место другой и поставить на место другого первый. Еще одна перестановка нужна на особый цикл. Итого .