worksheet for REAL lab #13
--------------------------

sorry about the switch, but this exercise
will give you an opportunity to better 
prep for the final (with help from our fine
TAs).

a)  recall that there are two ways to define
the perfect riffle shuffle -- the choice is
in the interleaving step.  in the lectures,
i have worked through the case where the topmost
card (# 1) remains on the top -- your mission 
is to rework everything for the case where the
topmost card goes to the second location.  the
new topmost card comes from the middle (# M+1) 
of the deck.

b)  modify two lines in "w13shuffle.m" so that
it now does this case -- it now takes 52 shuffles
to restore the deck!

c)  adapt the calculation from yesterday's class
to find the number theoretic formula relating the
# of perfect shuffles for restoring the deck (k)
and the # of cards (N=2M).

d)  you can now understand what happens as you 
change "Ncards" and "Nshuffles" in the script.
the following maple commands will be useful:

with(numtheory):
ifactor(2^Nshuffles-1);
order(2,Ncards+1);

e)  the two theorems mentioned (no proof shown) 
at the end of yesterday's class were:

if p is prime, 
               then 2^(p-1) = 1 (mod p)

and

if p is an odd prime, 
                      then 2^((p-1)/2) = +/- 1 (mod p)

these have interpretations for this shuffle technique
as well.