The old problem is still unanswered, but I decided not to try to post the solution before I figure out what that solution is anyway. I was kind of hoping someone would solve it for me, honestly. In the mean time, here is a new problem:
Suppose you have a bunch of leg-kicking dancing girl things all in a line:
You want to order them for maximum dazzle. You figured out the correct order, but they always come out on stage in some random order. To get them back to the correct positions, you make them swap places, one pair at a time, until they’re where you want them to be.
Prove or provide a counterexample to the following:
1) No matter what order they come out on stage, you can always get them back to the correct order simply by switching two dancers at a time as many times as you wish. You can even make the same dancer switch multiple times, if it helps.
2) There may be many ways to do the switching. Some ways may require more switches than others. However, for any given starting order, the solutions of sets of switches to get the dancers to the correct finish order all have either an even number of switches, or an odd number of switches. You might, for example, be able to solve a problem with 6 or 8 switches, but that problem cannot be done in 7 switches. Or if you can resolve a different problem with 11 switches, you might also do it in 5 or 9, but not 10.