Let $P$ denote some arrangement of the numbers $1,2, \ldots, n$. A move on $P$ consists of exchanging the position of element 1 with the position of another element. For example, if $P=[3,1,4,2]$, then by making one move we can get either $P=[1,3,4,2]$, $P=[3,4,1,2]$ or $P=[3,2,4,1] . P$ is said to be sorted if the numbers are in increasing order. Which of the statements are true?
A) The arrangement $[9,1,2,3,4,5,6,7,8]$ can be sorted in 8 moves and no fewer. B) $[1,3,4,5,6,7,8,9,2]$ can be sorted in 8 moves and no fewer. C) $[1,3,4,2,9,5,6,7,8]$ cannot be sorted by any number of moves.
D) There exists an arrangement of 99 numbers, i.e. 1 to 99 , that cannot be sorted by any number of moves.
-
What i thought was that to check by doing myself if the given arragemne is sorted or not , i was able to solve A sequence in 14 moves first interchanging 1 and 8 , then $(9-1), (1-7),(8-1),(1-6),(7-1),(1-5),(6-1),(1-4),(5-1),(1-3),(4-1),(1-2),(3-1)$. But i dont know how to show that whether this is minimum or not ? Is there a strategic way we can minimize it ? For B one i managed to do it in 9 moves $(1-9),(9-1),(8-1),(7-1),(6-1),(5-1),(4-1),(3-1),(2-1)$ is the 8 moves possible ? The C part i was able to do it in 12 moves , so its wrong . From these all i thought that we can manage to do every possible sequence but is it true in case of 99 ?
Note: i was able to realize it has something to do with parity odd , even number of moves and the initial total numbers there , but couldnt progress after that at all.