THE FOLLOWING IS THE SECOND POTM RESULT DISTRIBUTION - IT OUTLINES
THE COLLECTED WISDOM OF THE PARTICIPANTS REGARDING THE PROBLEM!

Thanks to many folks for bits and pieces of this ... including:
  Bob Hall, Daniel Sleator, Tim Tjarks, Lew Mammel, Scott Kennedy
  Kevin Ahrens, Brian Davies, Vincent Goffin, Debbie Brown, and ME!



	1. FF=I		Two consecutive flips result in no change (Identity)
	2. CC=I		Two consecutive cuts result in no change
	3. FC=CF	flips and cuts commute
	4. FS=SF	flips and shuffles commute

	5. Given 3 and 4, any operation can be transformed to an equivalent 
		operation where all flips occur sequentially.
	   Given 1, this single sequence of flips is equivalent to either a 
		single flip or no change.  Therefore: 
	6. we need consider only a single flip in any sequence of operations 
		with no loss of generality.

For the following, consider the deck to be represented by a[i], for
i=0 to 2m-1.  (i.e. for m=3, a deck of six cards, a[i]={0,1,2,3,4,5} )

	7. In a pristine deck, note that a[i] + a[i+2m-1] = 2m-1
	8. FLIPs, CUTs, and SHUFFLEs preserve property 7.
	9. Therefore, any sequence of operations applied to the pristine
		deck will result in a deck with property 7.  Property 7 is
		a necessary condition for solubility of a mixed deck - I
		don't know if it is sufficient.
	10. This shows that not all decks have solutions - cards will always
		be paired - if you know where one of the pair is - you will
		know where the other one has to be.  (e.g. ABCabc has three
		pairs A-c, B-b, and C-a.                -> 123321  <-
		SO, if you have BAabcC, you know there cannot be a solution
		since if B is in the first slot, b has to be in the last slot)
		Although interesting, I guaranteed up front that the deck
		I presented would have a solution!

	11. How many times do you have to shuffle the deck to return it
		to it's starting state?  Well, assuming there are 2m cards,
		the answer turns out to be f, where (2^f)%(2m+1) = 0
		(e.g. if there are 8 cards, then m=4.  we must find a value
			of f such that (2^f)%9 = 0 ...  f=6 will solve this
			and therefore 6 shuffles will return a deck of 8
			cards to where it started!)
		For m=1 through 26, corresponding to even numbered deck sizes
		of 2 through 52, the minimum values of f are given by:
  f(m)=2,4,3,6,10,12, 4,8,18, 6,11,20,18,28, 5,10,12,36,12,20,14,12,23,21, 8,52
		(The proof involves Euler's function - reference on request!)

	12. For some values of m, f/2 shuffles yields a FLIPPED deck.
		The following array shows the minimum number of shuffles
		before the deck is either flipped or restored.  Those numbers
		that are underlined indicate that they achieve a flip.
	1,2,3,3, 5, 6,4,4, 9,6,11,10, 9,14,5, 5,12,18,12,10, 7,12,23,21,8,26
	= =   =  =  =   =  =      ==  = ==   ==    ==    ==  =            ==

	13. A "CS" pair of operations is equivalent to that "other" kind of
		shuffle (where the top card does NOT change).  It is of
		interest to see how many "CS" operations it would take to
		return the deck to where it started.  The answer, for m=1,26
		is g, where (2^g)%(2m) = 0  (note g(m)=f(m-1) from SHUFFLE)
  g(m)=1,2,4,3, 6,10,12,4, 8,18, 6,11,20,18,28, 5,10,12,36,12,20,14,12,23,21, 8
	                  --                         --                      --
  f(m)=2,4,3,6,10,12, 4,8,18, 6,11,20,18,28, 5,10,12,36,12,20,14,12,23,21, 8,52
		Note that in three cases, m=9,18,26 fewer operations are
		required to restore the deck using CS operations than S alone!
		What exactly to DO with this information I'm not sure.
		In case it comes up, we'll define it as a HUFFLE, h[i]:

	14. Can a shuffle, cut, or flip be represented as a series of the
		other two operations?  Sometimes!  
		a) since FC=CF, and CC=I and FF=I, there are only four
			unique permutations that can be made from Cs and Fs:
			C, F, CF, and FC.  Except for 2-card decks, there are
			clearly more shuffled decks than 4.  Therefore a
			shuffle cannot be represented by Cs and Fs.
		b) For some deck sizes, a flip is equivalent to some shuffles!
			also to some number of CS operations (see 12,13 above)

	15. How many permutations are possible after N moves .... here's an
		estimate (just a tad high since I removed CC and FF moves,
		but did not apply the F commutivity to remove all but one F):
		(also interesting because it shows you how the 
			sequence searcher works!)
		Bottom line, after 22 operations there are a little over
		318,000,000 different operation sequences (not necessarily
		decks).  (By the way - if this is wrong, I don't want to know!)

this is the number of distinct sequences of operations of length N
after removing all operations containing CC and FF ... also
represented as 3**N minus those with CC or FF in them
 
Result of looking up  3 7 17 41 99 239 577 1393 3363 8119 19601  :

%I A1333 N1064
%S A1333 1,3,7,17,41,99,239,577,1393,3363,8119,19601,47321,114243,275807,
%T A1333 665857,1607521,3880899,9369319,22619537,54608393,131836323,318281039
%N A1333 $a(n) = 2a(n-1) + a(n-2)$.
%R A1333 MQET 1 9 16. AMM 56 445 49.
%O A1333 0,2
%C A1333 njas

References (if any):

[AMM] =    American Mathematical Monthly .
[MQET] =    Mathematical Questions and Solutions from the Educational Times .

And that's all she wrote for now ... stay tuned for the techniques used by
the contestants!!!!

=======================================================================

Special thanks to Neil Sloane for making the following neat little
 tool available - this tool enabled me to come up with the formulas
 (and a reference or two) for the number of shuffles that return a
 deck to its original state (see items 11 and 13 above!)

>>   To lookup sequences in the On-Line Encyclopedia of Integer Sequences,
>>   	(and lots of derived sequences)  send mail to:
>>   
>>   	superseeker@research.att.com
>>   
>>   containing 1 line like
>>   lookup 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37
>>   
>>   Start at the beginning, give lots of terms.  Minus signs are OK.
>>   The program will try VERY hard to find an explanation.
>>   
>>   Only one request may be submitted at a time, and (since this
>>   program does some serious computing), only one request per user
>>   per hour.  If there is no lookup line you will get the help file.
>>   
>>   Neil Sloane, njas@research.att.com












Make your own free website on Tripod.com