Problem set 3 This amounts to swapping s1 with S35 and s2 with s34. Each swap changes the parity of the number of inversions so after two swaps there are still an even number of Inversions. suppose that the numbers are rotated one position clockwise around the track. This transforms the permutation S1S2S3S4.S32S33534S3 into the permutation: This reverses the order of exactly 34 pairs of disks, S1 and every other disk. This changes the parity of the number of inversions 34 times, which leaves an even num- ber of inversions Similarly, rotating one position counterclockwise reverses the order of 34 pair again leaving an even number of inversions By induction, the number of inversions is always even. Therefore, the configuration in which 1 and 2 are swapped (which has 1 inversion) is unreachable Problem 3. A regular 52-card deck is arranged as follows A2.A.24..K。A·2·.KA◇2◇..K◇ In a perfect shuffle, the deck is first divided into two piles, one containing the top 26 cards and the other the bottom 26. These two piles are then recombined into a single deck by perfectly interlacing them This interlacing process can be done in two different ways since the new top card could come from the top of either 26-card pile. So over a sequence of perfect shuffles,many different arrangements of the deck can be obtained. Prove that no sequence of perfect shuffles puts the deck in the following order KA◇2◇..◇A◆2。..K Solution. We use induction. Define the cards in the i-th and (52- i)-th positions in the deck to be opposites. Thus, for example, the top card is opposite the bottom card, the second card is opposite the next to last card, and the two cards in the middle of the deckProblem Set 3 3 This amounts to swapping s1 with s35 and s2 with s34. Each swap changes the parity of the number of inversions, so after two swaps there are still an even number of inversions. • Suppose that the numbers are rotated one position clockwise around the track. This transforms the permutation s1s2s3s4 . . . s32s33s34s35 into the permutation: s2s3s4 . . . s32s33s34s35s1 This reverses the order of exactly 34 pairs of disks, s1 and every other disk. This changes the parity of the number of inversions 34 times, which leaves an even num￾ber of inversions. • Similarly, rotating one position counterclockwise reverses the order of 34 pairs, again leaving an even number of inversions. By induction, the number of inversions is always even. Therefore, the configuration in which 1 and 2 are swapped (which has 1 inversion) is unreachable. Problem 3. A regular 52­card deck is arranged as follows: A♥ 2 . . . K♥ A♣ 2♣ . . . K♣ A♠ 2♠ . . . K♠ A♦ 2♦ . . . K♦ In a perfect shuffle, the deck is first divided into two piles, one containing the top 26 cards and the other the bottom 26. These two piles are then recombined into a single deck by perfectly interlacing them: This interlacing process can be done in two different ways since the new top card could come from the top of either 26­card pile. So over a sequence of perfect shuffles, many different arrangements of the deck can be obtained. Prove that no sequence of perfect shuffles puts the deck in the following order: A♥ 2♥ . . . K♥ A♣ 2♣ . . . K♣ A♦ 2♦ . . . K♦ A♠ 2♠ . . . K♠ Solution. We use induction. Define the cards in the i­th and (52 − i)­th positions in the deck to be opposites. Thus, for example, the top card is opposite the bottom card, the second card is opposite the next to last card, and the two cards in the middle of the deck