Conference rusure::math

If anyone wants to investigate part(1), the following MAPLE code will be 
helpful:


riffle := proc () local i, j, deck, n;
# The first argument, assumed to be a permutation of 1..2*n, is shuffled.
# Author: Lynn Yarbrough  4-FEB-1992
    n := nops(args[1])/2;
    deck := array(1..2*n);
    for i from 1 to 2*n do;
	if type(i, odd) then 
	    deck[i] := args[1][n+1 + (i-1)/2]
	else
	    deck[i] := args[1][i/2]
	fi;
    od;
    [deck[j] $ j=1..(2*n)]
end;

Is this a problem in permutations or number theory?  Anyway, I note
that the card at position i is riffled to position 2*i mod (2*n+1).
And the next riffle moves it to to position 4*i mod (2*n+1).

>(1) Riffle shuffle A.


>	[a] what's the smallest n for which f(n) > 19?
>	[b] what's the largest n for which f(n) < 20?
>	[c] more generally, explore the behaviour of f(n) as n increases.


        Some notes on behaviour:- 

	When n is of the form  (2**r) -1 then f(n) = r+1

           (ie original sequence restored after r+1 shuffles
               eg if n= 7 then sequence restored in 4 shuffles
                  if n = 15 then sequence restores in 5 shuffles)

        When n is of the form (2**r) then f(n) = 2*(r+1)

          ( ie original sequence is reversed in r+1 shuffles
               and hence restored in 2(r+1) shuffles

            eg if n=8 then sequence restored in 8 shuffles)


	Also f(n) can never be less than ceil (log (n)) +1 
                                                  2

>	[a] what's the smallest n for which f(n) > 19?


         n= 12

       (impirically)
             
             if n= 12 then  f(n) = 20 


>	[b] what's the largest n for which f(n) < 20?

         n = (2**18)-1 and  f(n) = 19

         There can be no larger n, logic is as follows:

         Suppose we  have 
                       r2 = r1+1
                   and n1 = (2**r1) -1
                   and n2 = (2**r2) -1

        Then f(n1)= r1+1 <  f(N) for all N where  n1 < N <= n2

        Hence it follows f(n1) < f(N) for  all N > n1

             if n = (2**18)-1 then f(n) = 19

Here's Andy's somewhat lengthy analysis of the problem:


From:	HERON::BUCHANAN     "combinatorial bomb squad"  4-FEB-1992 16:02:23.67
To:	CIVAGE::LYNN
Subj:	an answer?

Lynn,

Against my better judgment, I found myself doing some scribbling on the
first problem I sent you today.   The answers I believe are interesting
although I haven't had time to check. 

	Q(1): smallest n such that f(n) > 19 is 12.
	Q(2): largest n such that f(n) < 20 is 2^18-1 (!!!)

I include the incoherent notes that suggested to me the answers to the
above.   I haven't time to tidy them, but they might suggest my approach to
you, if you didn't have the time to address it yourself. 

Regards,
Andrew.

-------------------------------------------------------------------------------

Riffle Shuffle A:

There's an invariant that enables us to simplify the problem substantially.
If card i moves to position j, then card 2n+1-i moves to position 2n+1-j.

So, we only need to keep track of the bottom half of the deck. With twelve
cards, for instance, this means that: 
	1234567890ab	
which moves to
	71829304a5b6
can be recorded as:
	123456
	615243
where any card j moving from the top half of the deck to the bottom half is
denoted by 2n+1-j.   Call such a move a flip.

Thus implicitly we are keeping track of the permutations of *pairs* of
cards, and not individuals. Suppose that we then compute that after g(n)
applications, all the pairs are back in their original positions. We now
need to ask, is any pair "flipped", so that the two cards occupy one
another's position? It's just like the movement of the edge-pieces in
Rubik's cube. 

So, with twelve cards (ie.: n=6) as above, the perm of card-pairs can be
represented as: 
	(163542)
This cycle contains 3 flips (the elements > n/2 in the list). Therefore the
cycle flips each pair in it.  g(n)=6, and hence f(n) here = 2*g(n) = 12. 

It's easy to see that either f(n)=g(n), or f(n)=2*g(n).

For practice, let's derive g(n) and f(n) for some small values of n.
In the following table, the middle columns have the following meanings:

bottom half shuffle:
	representation of the bottom half of the deck, in the notation
	described above. 

cycle rep:
	a re-expression of the permutation as a sequence of disjoint
	cycles. g(n) is the lowest common multiplier of the orders of these
	cycles. 

flipped cycles:
	for each of the cycles in "cycle rep", does the cycle "flip"?
	If the cycle which has greatest 2-arity (2 divides it the max
	number of times) flips, then f(n) = 2*g(n), else f(n) = g(n). 


 n	bottom half shuffle	cycle rep	flipped cycles?	   g(n)   f(n)
-------------------------------------------------------------------------------

 1	1			(1)			y	    1	   2
	1

 2	12			(12)			y	    2	   4
	21

 3	123			(132)			n	    3	   3
	312

 4	1234			(3)(142)		yy	    3	   6
	4132

 5	12345			(15342)			y	    5	  10
	51423

 6	123456			(163542)		y	    6	  12
	615243

 7	1234567			(5)(36)(1742)		yyn	    4	   4
	7162534

 8	12345678		(1842)(3756)		yy	    4	   8
	81726354

 9	123456789		(195763842)		y	    9	  18
	918273645

10	1234567890		(7)(396)(105842)	ynn	    6	   6
	0192837465

11	1234567890a		(1a630597842)		n	   11	  11
	a1029384756

12	1234567890ab		(50)(1b63a79842)	yy	   10	  20
	b1a203948576

13	1234567890abc		(9)(3b6)(1c705a842)	yyy	    9	  18
	c1b2a30495867

14	1234567890abcd		(1d7a905b63c842)	y	   14	  28
	d1c2b3a4059687

15	1234567890abcde		(1e842)(3d7b6)(5c9a0)	nnn	    5	   5
	e1d2c3b4a506978

16	1234567890abcdef	(a)(1f842)(3e9b6)(5d7c0)yyyy	    5	  10
	f1e2d3c4b5a60798

17	1234567890abcdefg	(5e0)(7d)(1g9cab63f842) nyn	   12	  12
	g1f2e3d4c5b6a7089

18	1234567890abcdefgh	(1h9d7eacb63g05f842)	y	   18	  36
	h1g2f3e4d5c6b7a809

19	1234567890abcdefghi	(c)(3h9eb6)(1i05gad7f842)yyn	   12	  12
	i1h2g3f4e5d6c7b8a90

-------------------------------------------------------------------------------

So to answer the first question of the puzzle, 12 is the smallest value of
n for which f(n) > 19. 

Now, let's make some remarks about short cycles.

Let v(j) be the card occupying position j after the riffle has been
performed. (ie, the contents of the row 2, column j of the "bottom half
shuffle", corresponding to n).

	v(j) = i/2 if i is even
	     = n - (i-1)/2 if i is odd

	j is a fixpoint if v(j)=j.
	This happens iff n == 1 mod 3, and in that case j = (2n+1)/3.

	v(j)=k, v(k)=j, j<>k
	This happens iff n == 2 mod 5, and in that case j can be taken to be
(2n+1)/5.

	ie: we can only have limited occurences of cycles of length 1 and 2.
(Note:  when such a short cycle appears, it will always be flipped.)

	We can carry on this game. We can postulate a given cycle length, L,
and then suggest which of the L transformations are flips. This gives us a
linear equation for j which will give us at most one value of j, which will
be valid for certain n. This gives us a limit on the number of small cycles
which can appear for any n.

	So, for instance, for L = 3, we have at most two flip possible flip
patterns.

	j = [n - ((n - (j-1)/2)-1))/2 ]/2
or	j = (n - (j-1)/2)/4

which translate to:
	j = (2n + 1)/7		(for n == 3 mod 7) 
or	j = (2n + 1)/9		(for n == 4 mod 9)

This is confirmed by experiment, and by looking at the table above.
It does suggest a certain pattern, doesn't it?

Suppose we have j = (2n+1)b/a, where a is odd, and 2n == -1 mod a.

	b == j mod 2.   

So if b is even, then v(j) = (2n+1)b'/a, where b' = b/2 While if b is odd,
then v(j) = (2n+1)b"/a, where b' = (a-b)/2.   Thus the shuffle acts as a
bijection on the set { (2n+1)b/a, for b={1,...,a-1} }. 

To turn this on its head, given n, let a be a factor of 2n+1. Then the
shuffle is a bijection of the set of multiples of (2n+1)/a. If a = 2n+1, or
a = 1, then this is a trivial remark. But if a is a non-trivial factor,
then this is useful information. 

This in fact allows us to identify *all* the cycles in the example list
above except: 
	(i) all those containing the card 1.
	(ii) total failure to account for short cycles for n=8,15
	(iii) partial failure to account for short cycles for n=16.

Clearly, when n = 2^t or 2^t-1, there will be a cycle of length t+1
containing the cards: {1,2,4...,2^t} or {1,2,4,...,2^(t-1),2^t-1}. 

Hmm, let's recall v(j)

	v(j) = j/2 if j is even
	     = n+1/2 - j/2 if j is odd.

Now, let's look a cycles of length L, of a particular flip pattern.

We're always going to get something of the form:
	j = p(2n+1)/(2^L�1)

What this suggests is that suppose we take n = 2^18. Then whatever flip
pattern of length 19 we suggest, there will be a value of j that is a
solution. This suggests that f(2^18-1) is incredibly 19. f(2^18) will be 19
as well, but there will be a flip in the fixpoint. 

If n >= 2^19-1, then there is a cycle of length at least 20, so the answer
to the second question lies in {2^18...2^19-2}. 

Put it another way.   Let's say that every pair is back at its start after
L shuffles.   Then in particular 1 is, so 2n+1 | 2^L�1.   A fortiori, 
n =< 2^(L-1) +(0or1), and there's no way that any larger value of n can
work. 

Andrew.

Riffle shuffle B:

Since the cards are originally alternating in color, a single riffle cannot 
produce a sequence of three or more cards of the same color. Since the cut 
is between two cards of the same color, the first and second cards after 
the cut must be opposite. Now we need to prove that the next pair is also
opposite. They cannot be the same as card 2, since that would mean 3 like 
cards in sequence. Can they be the same as card 1? No, because including 
the bottom card we would have, say, B/\BR/BB, which can only be produced 
in one of the following ways:

1) Insert B into BRBB or BBRB
2)   "   BR into BBB
3)   "   RB into BBB
4)   "    R into BB
5)   "  BRB into BB
6)   "   BB into something

And none of these can come from a deck with alternating R&B.

By induction, the third, 4th, ... pairs are also opposites.

	Given: a deck with 2*n cards, and a (particular) riffle that
	permutes the cards.

Lemma 1.
	The card at position i is riffled to position 2*i mod (2*n+1).
	By induction, after r riffles, the card at position i is moved
	to position i*(2**r) mod (2*n+1).

Lemma 2.
	Let f(n) be the minimum (nonzero) number of riffles that restores
	the deck to its original order.
	Then f(n) = the smallest s > 0 for which 2**s mod (2*n+1) = 1.
Proof:	From Lemma 1: a card at i moves to i*(2**s) mod (2*n+1) = i*1 = i.
	Suppose p < s sufficed; then (2**p) mod (2*n+1) = 1, for p < s,
	but s is supposedly smallest.

Pragmatics:
	Note that we need only keep track of *one* card.  A fast algorithm
	for computing f(n) is:
		fn := 0; i := 1;
		repeat fn := fn + 1; i := (2*i) mod (2*n+1) until i = 1;

> [a] what's the smallest n for which f(n) > 19?

	This can be done by hand.  To determine f(n), find the first 2^s-1
	that has 2�n+1 as a factor.  Then f(n) = s.

	In the table below, I needlessly filled in some f(n) for n > 12.

	2^s-1				f(n) = s (2�n+1 is a factor of 2^s-1)
	-------------			---------------------------------------
	2^1-1 = 1			f(0) = 1
	2^2-1 = 3			f(1) = 2 (2�1+1 is a factor of 2^2-1)
	2^3-1 = 7			f(3) = 3 (2�3+1 is a factor of 2^3-1)
	2^4-1 = 15 = 3�5		f(2) = 4 = f(7)
	2^5-1 = 31			f(15) = 5 (this is the only f(n) = 5)
	2^6-1 = 63 = 3�3�7		f(4) = 6 = f(10) = f(31) (that's all)
	2^7-1 = 127			f(63) = 7
	2^8-1 = 255 = 3�5�17		f(8) = 8 = f(25) = f(42) = f(127)
	2^9-1 = 511 = 7�73		f(36) = 9 = f(255)
	2^10-1 = 1023 = 3�11�31		f(5) = 10 = f(16) = f(46) = f(170)
					     = f(511)
	2^11-1 = 2047 = 23�89		f(11) = 11 = f(44) = f(1023)
	2^12-1 = 4095 =  3�3�5�7�13	f(6) = 12 = ...
	2^13-1 = 8191			f(4095) = 13
	2^14-1 = 16383 = 3�43�127	f(21) = 14 = f(64) = f(190) = f(2730)
					      = f(8191)
	2^15-1 = 32767 = 7�31�151	f(75) = 15 = ...
	2^16-1 = 65535 = 3�5�17�257	f(128) = 16 = ...
	2^17-1 = 131071			f(65535=2^16-1) = 17 (the only one)
	2^18-1 = 262143 = 3�3�7�19�73	f(9) = 18 = ...
	2^19-1 = 524287			f(2^18-1) = 19	(the only one)
	2^20-1 = 1048575 = 3�5�5�11�31�41	f(12) = 20 = ...

> [b] what's the largest n for which f(n) < 20?

	For any s > 0, n = 2^(s-1)-1 is the largest value of n that has
	f(n) = s (this is a simple application of reply .6).
	So for f(n) = s < 20, the largest n results from s = 19:
	f(2^18-1) = 19.

	Suppose we have a deck of N cards, and define a "complete shuffle" as one
where every card in the deck moves to a new position.

	ie. If initial state of the deck is

	    1,2,......n,.....N

            Then after a complete shuffle the state of the deck is

            p1,p2,....pn,....pN

            where pn .NE. n for all   n    1<= n <= N
                               

      a) Given N how many complete shuffles are possible?

      b) Show that a repeated sequence of any complete shuffle must always 
         restore the deck in no more than N shuffles.


      c)  Given N how many of the complete shuffles will require a sequence
         of  length exactly N shuffles to restore the deck?

Richard

>      b) Show that a repeated sequence of any complete shuffle must always 
>         restore the deck in no more than N shuffles.

I don't think this is true. let {a..b} be the end-around shuffle -> b,a...
Let N = 15 and consider the permutation 
	{1..3}{4..8}{9..15}
Since the lengths of segments (3,5,7) are relatively prime, the complete 
cycle of permutations is of length 3*5*7 = 105. Each item returns to its 
position in not more than 7 perms, but getting them all together takes 
longer.

Ooops.

I meant N! sorry.

 ( Reasoning  N! to be the upper bound on the number of states
the deck can be in and it is impossible given that the deck is in state SX
for it to transition to a loop SY...SZ,SY...SZ,... where SX does not
occur within SY...SZ.)

Is there, in general, a better upper bound?

Given the problem as stated your counter-example is obviously irrefutable. Thanks
for spotting it so quickly.

Richard. 

 

>Suppose we have a deck of N cards, and define a "complete shuffle" as one
>where every card in the deck moves to a new position.

>	ie. If initial state of the deck is
>	    1,2,......n,.....N
>	Then after a complete shuffle the state of the deck is
>	    p1,p2,....pn,....pN
>	where pn .NE. n for all   n    1<= n <= N

This is called a permutation with no fixed points.

>	a) Given N how many complete shuffles are possible?

The total number of shuffles of all kinds = the number of permutations = N!, 
which is the order of the permutation group on N objects. According to
Bronshtein & Semendayev p. 97, the number of permutations with *at least
one* fixed point is 

	sum(i=1..N)[((-1)^(i+1))*C(k,i)*(k-i)!]
   = 	sum(i=1..N)[((-1)^(i+1))*(k!/i!)]

so the answer to question a is (N! - this sum).

RE: .0

    For what it is worth, both of these riffle shuffles are used in card
    magic.

				    Topher

>      b) Show that a repeated sequence of any complete shuffle must always 
>         restore the deck in no more than N! shuffles.
> Is there, in general, a better upper bound?

Consider a shuffle of N elements with cycles of length c[1], c[2] , ..., c[m]
(for a 'complete' shuffle, none of the c[i] equal 1).  The sum of the c[i]
equals N, the number of elements.  Let r(N) be the number of shuffles necessary
to restore the deck; r(N) = lcm(c[1],c[2],...,c[m]).

Since lcm(a,...,z) <= a�...�z, a better upper bound is:

	r(N) = lcm(c[1],...,c[m]) <= c[1]�...�c[m] <= 3^u � 2^v

where v = 2�N mod 3, and u = (N-2�v) / 3.

   (Reply to note 13)

>Consider a shuffle of N elements with cycles of length c[1], c[2] , ..., c[m]
>(for a 'complete' shuffle, none of the c[i] equal 1).  The sum of the c[i]
>equals N, the number of elements.  Let r(N) be the number of shuffles necessary
>to restore the deck; r(N) = lcm(c[1],c[2],...,c[m]).

Sorry to be obtuse but I do not understand your nomenclature, 

By c[1]....c[m] do you mean c[m] is the minimum number of shuffles required to
restore the mth card in the deck to its original position? In which case,
whilst each for each c[i]
           
                   1 < c[i] <= N

 the sum of the c[i] is, I believe, bounded thus:-

                   N
                  - 
           2N <=  \ c[i]       <= N**2
                  / 
                  -
                  i= 1

which obviously excludes N.

Alternatively do you mean c[i] to be that subset of i cards which restores
in c[i] shuffles??. In which case the sum of the i's would equal N, but that
says nothing about the sum of the c[i]'s. ?? The c[i]'s (number of shuffles
to restore a  subset) are not defined or described which, recursively, gets
back to the original question.

Alternatively do you mean that we can consider the deck as m subsets
where each subset contains c[i] cards (i=1...m) that restore in a given
number of shuffles?? In which case the sum of the c[i] again equals N
but you have not defined or described the number of shuffles required to
restore each subset (which again, recursively, gets back to the original
question).

I would hazard a guess that your upper bound is predicated on the complete
shuffle being in the form of a composite "end-around" shuffle of the type
suggested in reply 9, and your c[i] describe the subsets that are
end-around shuffled, but there may be other types of complete shuffles
which have higher upper bounds.
 
Apolgies in advance if I missed something obvious.

Richard.

    Re .14:
    
    A cycle is a certain kind of permutation.  Suppose you have elements a,
    b, c, d, and e.  Then the cycle (a b c d e) moves a to b, b to c, c to
    d, d to e, and e to a.  In any cycle, each element moves to the next
    position, except the last moves to the front.
    
    It so happens that _every_ permutation can be expressed as a product of
    cycles, in which each cycle contains only elements not contained in the
    other cycles in the product (the cycles are disjoint).  For example,
    the permutation that moves 1 to 3, 2 to 5, 3 to 1, 5 to 4, and 4 to 2
    is the product of the cycles (1 3) and (2 5 4).
    
    So any given shuffle of a deck can be expressed as a product of
    disjoint cycles.  Peter Gilbert was saying that, given a shuffle,
    express it as a product of disjoint cycles, and let c[i] be the length
    of the i-th of these cycles.
    
    Naturally, repeating a cycle of length n n times results in no change.
    
    
    				-- edp

Reply to 14.

Thanks, your description made it very clear.

Here are some values of r(N), the number of shuffles necessary to restore
a deck (here, 1-cycles are allowed).  To give some appreciation for how poor
the bound in .13 is, it gives r(49) <= 57395628, whereas r(49) = 180180.

r(1) = 1
r(2) = 2
r(3) = 3
r(4) = 4
r(5) = r(6) = 6
r(7) = 12
r(8) = 15
r(9) = 20
r(10) = r(11) = 30
r(12) = r(13) = 60
r(14) = 84
r(15) = 105
r(16) = 140
r(17) = r(18) = 210
r(19) = r(20) = r(21) = r(22) = 420
r(23) = r(24) = 840
r(25) = r(26) = 1260
r(27) = 1540
r(28) = 2310
r(29) = 2520
r(30) = r(31) = 4620
r(32) = r(33) = 5460
r(34) = r(35) = 9240
r(36) = r(37) = 13860
r(38) = r(39) = 16380
r(40) = 27720
r(41) = 30030
r(42) = 32760
r(43) = r(44) = r(45) = r(46) = 60060
r(47) = r(48) = 120120
r(49) = r(50) = r(51) = r(52) = 180180
r(53) = 360360