Республиканская олимпиада по математике, 2021 год, 9 класс

На полке стоят в беспорядке 100 томов энциклопедии, занумерованных всеми натуральными числами от 1 до 100. За одну операцию можно взять и любым способом переставить на своих местах любые три тома (т.е. если эти тома стояли в местах $a,b,c$, то после этой операции эти тома также будут стоять в местах $a,b,c$, но возможно в другом порядке). При каком наименьшем $m$ можно утверждать, что $m$ такими операциями удастся расставить все тома по порядку, как бы они ни были расставлены первоначально? (Тома стоят по порядку, если 1-й том стоит на 1-м месте, 2-й том на 2-м, ..., 100-й том на 100-м месте.) ( А. Голованов )

Комментарий/решение

Ответ:50

Заметим что в каком бы не было порядке разбросаны томы, всегда можно взять какой то том, и взять второй том который стоит на должном месте того тома, а третьим образом повторить такое с предыдущим томом и взять третий том, в итоге за один ход можно добиться 2 томов на своих местах. Максимальное количество таких ходов:50.

Надо найти не максимальное, а наименьшее значение, к тому же нет оценки, что 50 - минимальное количество

Максимальное-Имею ввиду что в любой конструкции гарантируется что возможно собрать все обратно.

А насчет оценки да, согласен.

Четностью позиций $i,$ назовем четностью выражения $a_i - i,$ где $a_i$ число стоящее на позиций $i$. Поставим числа таким образом:

$$2,1,4,3,...,100,99$$

Тогда каждая позиция изначально нечетна, а в конце все позиций четные, если было сделано 49 ходов, то очевидно какой то ход поменял сразу 3 нечетные позиций на 3 четные (иначе $49*2 < 100$). Допустим на этом шагу участвовали числа $a, b, c$ с позициями $x,y,z.$ Рассмотрим выражение $a+b+c - (x+y+z),$ которое не зависит от перемещения $a,b,c$ изначально оно нечетно поскольку все три позиций нечетные а после одного шага становится четным, то что невозможно. Пример для 50 сверху,

$Официальное$ $решение$:

Ответ. 50.

Решение. Докажем, что 50 операций всегда достаточно. Одна операция позволяет поставить на место

два тома: если тома с номером a стоит на месте тома $b$ $6= a$, а том $b$ – на месте тома $c$, то при $c$ $6= a$ можно

поставить $a$ и $b$ на свои места, а на место тома $c$ поставить тот, который сейчас стоит на месте $a$. Если

же $c = a$, можно просто поменять местами $a$ и $b$, формально добавив в тройку любой из оставшихся

томов.

Докажем, что расстановку томов 100, 1, 2, . . . , 99 нельзя привести в порядок меньшим числом операций. Для произвольной перестановки томов рассмотрим ориентированный граф, вершинами которого

служат тома, а стрелка от каждого тома идёт к тому, который стоит на его месте. Поскольку в каждой

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

по порядку – граф из 100 циклов (в каждом из которых по одной вершине). Если поменять местами два

тома, то есть поменять местами концы двух стрелок, оставив на месте их начала, количество циклов

изменится на 1 (если стрелки принадлежали одному циклу, он распадётся на два, а если двум разным,

эти циклы объединятся). Любая перестановка трёх томов получается не более, чем двумя обменами

двух томов. Это означает, что наша операция меняет количество циклов не более, чем на 2, и получить

100 циклов из одного менее, чем за 50 операций невозможно.