New Problem: Parity of Permutations

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.

2 Responses to “New Problem: Parity of Permutations”

  1. Answer: Parity of Permutations « Arcsecond Says:

    […] 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 […]

  2. New Problem: The Rockettes Return « Arcsecond Says:

    […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: