Задача М2865‍‍‍

Числа от 1 до $n$‍‍ расставлены в некотором порядке в клетках полоски $1\times n$‍.‍ Будем называть флипом операцию, которая некоторым образом (см. ниже) выбирает две разные клетки полоски и меняет местами числа, записанные в них, но только в том случае, когда большее из этих чисел расположено левее меньшего. Флопом называется набор из нескольких флипов, не содержащих общих клеток, которые выполняются одновременно.

1. Пусть $n=p+q$‍.‍ Клетки для произвольного флипа должны принадлежать разным «половинам» полоски: одна клетка выбирается из первых $p$‍‍ клеток, а другая — из последних $q$‍‍ клеток.

   Докажите, что если в произвольном порядке выполнить все $pq$‍‍ возможных флипов, то все числа от 1 до $p$‍‍ окажутся на первых $p$‍‍ местах, а все числа от $p+1$‍‍ до $n$‍‍ — на последних $q$‍‍ местах.

2. Пусть $n=2025$‍.‍ Клетки, подвергаемые флипу, должны быть соседними.

   Последовательность флопов такова, что для любой исходной расстановки применение к ней этой последовательности флопов приведёт к упорядочиванию чисел слева направо по возрастанию. Какое наименьшее количество флопов может быть в этой последовательности?

3. Пусть $n=2025$‍.‍ Клетки, для которых выполняется флип, могут быть любыми двумя клетками полоски.

   Докажите, что существует такая последовательность из 66 флопов, что при любой исходной расстановке применение к ней этой последовательности флопов приведёт к упорядочиванию чисел слева направо по возрастанию.