Задача
COM-B1-M06-P024 Обратный порядок за \(27\) ходов
#24
★★★★★ Уровень 5 из 5
Из строки \(12345678\) разрешено за ход менять местами два соседних символа. Можно ли получить \(87654321\) ровно за \(27\) ходов?
Соседний обмен меняет чётность числа инверсий.
Число инверсий в начале равно \(0\). Каждый соседний обмен меняет чётность числа инверсий. После \(27\) ходов чётность инверсий должна быть нечётной. Но в строке \(87654321\) число инверсий равно \(C(8,2)=28\), оно чётно. Противоречие, значит ровно за \(27\) ходов получить нельзя.
Challenge на составной инвариант: паритет инверсий связан с числом ходов.