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