Thread: permutation

please I need help with this,

24 card are put a pile in numerical order with 1 on the top and 24 on the bottom. they are first of all given a riffle shuffle so that the bottom card remains where it is, and then divided into four quarters. the bottom two quarters are left in the place they were in after the shuffle and the top two quarters are swapped over.

1. work out the order of the cads after this combination of suffles has taken place.
2. when this permutation is broken down into disjoint cycles,show that one of the cycles is (3 11 21 18 6 5) and find the other cycles.
3. how many times will this process will have to be repeated to return all the cards to their original order? explain how you arrive at your answer.

Hello geo2

Originally Posted by geo2

please I need help with this,

24 card are put a pile in numerical order with 1 on the top and 24 on the bottom. they are first of all given a riffle shuffle so that the bottom card remains where it is, and then divided into four quarters. the bottom two quarters are left in the place they were in after the shuffle and the top two quarters are swapped over.

1. work out the order of the cads after this combination of suffles has taken place.
2. when this permutation is broken down into disjoint cycles,show that one of the cycles is (3 11 21 18 6 5) and find the other cycles.
3. how many times will this process will have to be repeated to return all the cards to their original order? explain how you arrive at your answer.

In a perfect riffle shuffle, equal numbers of cards are placed into two piles, and then the two piles are combined into one by taking cards alternately from each of the two piles.

So after the first riffle shuffle, since card 24 stays on the bottom, the order is:

1 13 2 14 3 15 4 16 5 17 6 18 7 19 8 20 9 21 10 22 11 23 12 24

The first and second quarters (groups of 6 cards) of this list are now transposed, giving the order:

4 16 5 17 6 18 1 13 2 14 3 15 7 19 8 20 9 21 10 22 11 23 12 24

So that's the answer to part (1).

(2) We can show the new positions of the cards as follows:

New : Old
1 : 4
2 : 16
3 : 5
4 : 17
5 : 6
6 : 18
7 : 1
8 : 13
9 : 2
10 : 14
11 : 3
12 : 15
13 : 7
14 : 19
15 : 8
16 : 20
17 : 9
18 : 21
19 : 10
20 : 22
21 : 11
22 : 23
23 : 12
24 : 24

This shows, for example, that card number 3 is now in 11th position after one shuffling process (permutation). Further, it shows that the card that was in 11th position is now in 21st position. So if the whole process is repeated again and again, card #3 moves first to position 11, then 21, then 18, then 6, then 5 and finally (after 6 permutations) back to position 3.

This, then, is a 'closed' cycle, since card #3 has now returned to its original position.

We can trace the movements of all the other cards in the same way. Clearly cards 3, 11, 21, 18, 6 and 5 have all been dealt with. So let's start at 1 and see what happens. We get the following sequence of positions:

1, 7, 13, 8, 15, 12, 23, 22, 20, 16, 2, 9, 17, 4 and (after 14 permutations) back to 1.

So this is another 'closed' cycle.

We've now dealt with cards 1 through 9, so the next one to try is 10:

10, 19, 14 and (after 3 permutations) back to 10

This has dealt with 23 cards. The only one left is 24 - which, of course, stays where it is at all times.

So these are the 'closed' (i.e. disjoint, or non-overlapping) cycles.

(3) Since card #3 is in a cycle containing 6 cards, in order for card number 3 (or any of the cards in its group) to be returned to its original position, the number of complete permutations must be a multiple of 6.

In the same way, for cards in each of the other groups, the number of permutations will have to be multiples of 14, 3 and 1.

So if all the cards are returned to their original positions, the smallest number of permutations is the LCM of 6, 14, 3 and 1, which is 42.

Grandad