About cookies

The NCETM site uses cookies. Read more about our privacy policy

Please agree to accept our cookies. If you continue to use the site, we'll assume you're happy to accept them.

 

Personal Learning Login






Sign Up | Forgotten password?
 
Register with the NCETM

Secondary Magazine - Issue 63: Focus on


This page has been archived. The content was correct at the time of original publication, but is no longer updated.
Created on 22 June 2010 by ncetm_administrator
Updated on 06 July 2010 by ncetm_administrator

 

Secondary Magazine Issue 63playing cards
 

Focus on...perfect shuffles

There are some magic tricks that use pretty elaborate mathematics...and…magicians can perfectly shuffle a deck of cards.
Persi Diaconis, Professor of Mathematics at Stanford University, August 2003

orange circles

To perform a perfect riffle shuffle, known as a faro or weave shuffle, you split an ordered arrangement of objects into two halves, or into two parts as nearly equal as possible, and then alternatively interleave, in order, the objects from the two parts.

Suppose the ‘objects’ are students standing in a row in the order of numbered cards that they are holding:

cards one to eight

Let’s see what happens when they perfectly shuffle themselves!

Because eight is an even number the students can move apart into two rows each containing the same number of students:

cards in two groups, one to four and five to eight

Now they can decide to do an out-shuffle, or to do an in-shuffle.

If they interleave themselves so that after the shuffle the ‘first’ and ‘last’ students, holding respectively 1 and 8, are still ‘first’ and ‘last’, they do an out-shuffle. But if the first student becomes second while the last student becomes second from last, they do an in-shuffle:

out-shuffle

out-shuffle


in-shuffle

in-shuffle

Suppose the number of students is odd, say that there are five students. Because the five students cannot move apart into two rows each containing the same number of students, they have to decide whether to split apart before or after the centre of the row.

If they split after the centre, they will then have to do an out-shuffle. But if they split before the centre they can then only do an in-shuffle:

out-shuffle   in-shuffle
out-shuffle with five cards   in-shuffle with five cards


Of course the objects that are being shuffled are often playing cards. Because the number of cards in a normal pack is an even number, 52, the pack may be cut into two piles each containing 26 cards, and then out-shuffled or in-shuffled.

a pack of 52 playing cards may be either out-shuffled or in-shuffled

YouTube has a videoclip where you can learn how to do a perfect shuffle of a pack of playing cards.
 

green circles

It is natural to ask what will happen if we repeatedly perfectly shuffle an ordered arrangement of objects. Will we ever get back to the original order?

Surprises are in store!

If the eight students do out-shuffles repeatedly, this is what happens:

If eight students do out-shuffles repeatedly, this is what happens

After only three out-shuffles the original order is restored!

Will the students also be back in their original order after three in-shuffles?

Will the students be back in their original order after three in-shuffles?

The students have done three in-shuffles, but they are NOT back in their original order!

So they carry on:

Three more shuffles have restored the original order

Three more shuffles have restored the original order!

If you experiment with other numbers of students in the row your findings may surprise you. For example, with 13 students in the row the original order is restored after 12 out-shuffles or 12 in-shuffles. But with three more students, that is with 16 students in the row, it takes only four out-shuffles or eight in-shuffles!

You will see that with any odd number of students you first return to the original order after the same number of in-shuffles as out-shuffles. With even numbers of students this is not the case.

If you and your students persevere with this exploration you may eventually alight upon some extraordinary generalisations, three of which can be summarized as follows:

To restore the original order,
          when the number of objects is odd,
            the number of shuffles of the same kind required is:
              the power to which you must raise the number 2 to make a number that has a remainder of 1 when divided by the number of objects.
  when the number of objects is even,
    the number of out-shuffles required is:
      the power to which you must raise the number 2 to make a number that has a remainder of 1 when divided by one less than the number of objects;
    the number of in-shuffles required is:
      the power to which you must raise the number 2 to make a number that has a remainder of 1 when divided by one more than the number of objects.

Try out these generalisations!
 

purple circles

Other naturally occurring questions about perfect shuffles, that magicians and mathematicians have asked themselves, have also lead to very surprising links in mathematics. For example, an unexpected connection emerges when you explore answers to the following question:

Given any number of objects, is it possible, by repeatedly doing perfect shuffles, to get the first object (the top card) to any particular position?

For example, suppose that there are seven students. Can we get the first student, holding ‘1’, to the fifth position?

Can we get the first student holding 1, to the fifth position

Alex Elmsley, a Cambridge University graduate with one of the most inventive brains in magic, was exploring ways of getting the top card to a particular position in the pack. He happened to start jotting down in his notes ‘I’ to represent an in-shuffle and ‘O’ to represent an out-shuffle.

Then he noticed something quite amazing! He saw that, by writing as a binary number the number of the position immediately before the position that he wanted to reach, the required shuffles were just presented to him ‘on a plate’!!

Let’s explain. We are trying to get the first student to position 5. The number of the position immediately before position 5 is 4, and 4 written as a binary number is 100. If we do the sequence of shuffles that Alex jotted down as IOO, that is an in-shuffle, then an out-shuffle, then another out-shuffle

Sequence of shuffles that moves the first student to position five

...we've done it!

Try out this amazing finding on other examples!
 

blue circles

Magicians often check the results of a sequence of perfect shuffles (which, with playing cards, is usually difficult and clumsy to do) by undoing the sequence. They do, backwards, the sequence of reverse shuffles. They call the reverse of an in-shuffle an in-sort, and the reverse of an out-shuffle an out-sort. Sorts of playing cards are much easier to do than shuffles.

This is how the eight students do a reverse shuffle, or a sort.
 
Alternate students move away from the other students to form a new row:

Alternate students move away to form a new row

Then the half-rows move together to form a new row of all eight students. If they form the new row so that the student who was originally first (the student holding ‘1’) is again first, they will have done an out-sort.

Students form a new row, so that the student who was originally first is again first.

But if the half-rows join together so that the student who is now first is the student who was originally second, they will have done an in-sort.

If the half-rows join together so that the student who is now first is the student who was originally second, they will have done an in-sort.

red circles

Some conjuring tricks depend on the magician being able to get a playing card that is at a particular position in a stack of any size up to the top of the stack. Because this problem is the reverse of the problem of getting the first card to a particular position, it is sensible to explore it using sorts rather than shuffles.

Alex’s Elmsley’s amazing discovery about the unlikely link with binary numbers again gives magicians a simple procedure to follow in any such situation. For example, suppose that you have a stack consisting of the first ten diamonds arranged in size order, and that you want to get the four of diamonds to the top.

The card that you want to move is at position 4. Subtract 1 from 4, to get 3, then write the decimal number 3 in binary as ‘11’. Now do, backwards, the sequence of sorts represented by I, I, which is in-sort, in-sort
 

Sequence of sorting the card at position four to move to the top

...the four of diamonds is at the top of the stack!

Generally, just subtract 1 from the number giving the present position of the card, and write the result as a binary number. Then follow, backwards, the sequence indicated by the binary number, doing perfect sorts rather than perfect shuffles.
 

orange circles

Here is one more surprising phenomenon. When you move the top card of a deck consisting of an even number of cards, to the nth position from the top, the bottom card of the deck automatically goes to the nth position from the bottom!

For example, when you follow the binary number procedure to get the top card in an eight-card deck to the sixth position from the top, the bottom card automatically goes to the sixth position from the bottom!

Sequence showing the move of the top card of a deck of even numbers to the nth position from the top, with bottom card moing to the nth position from the bottom

And the cards that were originally at the top and bottom are at symmetrical positions at every stage!

You might like to investigate whether the same symmetry exists whenever you move a card at a particular position up to the top.

You can explore these card moving procedures effortlessly using this Faro shuffle simulator from natedog.com.

 
This article can be downloaded as a separate PDF document.
 
 
 View this issue in PDF format
 
 Visit the Secondary Magazine Archive
 
 About Magazine feeds
 

 
 
 
 
Secondary Magazine Issue 63 - download as a PDF
 
 
Magazine Feed - keep informed of forthcoming issues
 
Departmental Workshops - Structured professional development activities
 
Explore the Secondary Forum
 
Contact us - share your ideas and comments 

Comment on this item  
 
Add to your NCETM favourites
Remove from your NCETM favourites
Add a note on this item
Recommend to a friend
Comment on this item
Send to printer
Request a reminder of this item
Cancel a reminder of this item

Comments

 


There are no comments for this item yet...
Only registered users may comment. Log in to comment