Математикадан республикалық олимпиада, 2020-2021 оқу жылы, 9 сынып

Энциклопедияның жүз томы 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 операций невозможно.