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

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

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

Можете пожалуйста указать авторов задач

Мы пока не знаем. А так сразу сделали бы это.

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

Докажем, что 50 операций всегда достаточно. Одна операция позволяет поставить на место два тома: если тома с номером a стоит на месте тома b = a, а том b – на месте тома c, то при c = a можно поставить a и b на свои места, а на место тома c поставить тот, который сейчас стоит на месте a. Если же c = a, можно просто поменять местами a и b, формально добавив в тройку любой из оставшихся томов. Докажем, что расстановку томов 100, 1, 2, . . . , 99 нельзя привести в порядок меньшим числом операций. Для произвольной перестановки томов рассмотрим ориентированный граф, вершинами которого служат тома, а стрелка от каждого тома идёт к тому, который стоит на его месте. Поскольку в каждой вершине есть по одной входящей и выходящей стрелке, этот граф представляет собой объединение циклов без общих вершин. Перестановке 100, 1, 2, . . . , 99 соответствует граф из одного цикла, а расстановке по порядку – граф из 100 циклов (в каждом из которых по одной вершине). Если поменять местами два тома, то есть поменять местами концы двух стрелок, оставив на месте их начала, количество циклов изменится на 1 (если стрелки принадлежали одному циклу, он распадётся на два, а если двум разным, эти циклы объединятся). Любая перестановка трёх томов получается не более, чем двумя обменами двух томов. Это означает, что наша операция меняет количество циклов не более, чем на 2, и получить 100 циклов из одного менее, чем за 50 операций невозможно.