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.

### Like this:

Like Loading...

*Related*

This entry was posted on December 4, 2008 at 9:35 am and is filed under problems and solutions. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

December 6, 2008 at 6:55 am

[…] Parity of Permutations By meichenl The question asked you to show that it is possible to permute a list however you like using only successive […]

March 17, 2009 at 1:35 am

[…] Problem: The Rockettes Return By meichenl Recall a previous problem (and its solution) about a line of dancers who come out on stage in a random […]