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

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