Results 1 to 2 of 2

Math Help - permutation

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    14

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Permutations

    Hello geo2
    Quote Originally Posted by geo2 View Post
    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

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Why permutation ?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 11th 2010, 11:27 AM
  2. permutation help
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: July 9th 2010, 02:37 PM
  3. Permutation
    Posted in the Statistics Forum
    Replies: 5
    Last Post: October 13th 2008, 05:17 PM
  4. Permutation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 7th 2008, 11:01 AM
  5. Permutation.......
    Posted in the Statistics Forum
    Replies: 5
    Last Post: March 24th 2008, 03:41 AM

Search Tags


/mathhelpforum @mathhelpforum