Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In this question, a certain algorithm was presented:

Start with a deck of $n$ cards.

  1. Take the top card off and set it on the table on top of any cards already there

  2. Move the new top card to the bottom of the deck

  3. Go to step 1 if there are still cards in the deck. When there are no more cards in the deck, one round has passed

  4. Pick up the cards from the table; this is the new deck. If the new deck is in the original order, we are done. Otherwise, repeat from step 1.

As I show in my answer to that question, there are a few peculiarities.

  1. Powers of two go through few rounds before the cards are in the original order. For example, while the numbers around $64$ take $60+$ rounds before returning to their original state, $64$ takes only $12$ rounds. It appears that every power of two other than two results in $4m$ rounds where $m\in\Bbb N$.
  2. Prime numbers go through an unusually large number of rounds. For example, while the numbers around $31$ all take less than $100$ rounds, $31$ takes $210$ rounds.
  3. There are doubtless other interesting properties of this algorithm

What is significant about this algorithm that causes prime numbers and powers of two to have peculiar output?


In response to Victor Engel's comment, here is a proof that the algorithm will always return the deck to the starting case:

  1. We know that each round is a one-to-one function from a deck ordering to another deck ordering (this should be clear from the way it is set up; it is reversible).
  2. We know that there are a finite number of deck orderings.

Assume that there is a case where the algorithm does not go back to the starting ordering.

$\implies$ In that case, either there are an infinite number of orderings, or there is a loop somewhere in the sequence.

But we know that there are a finite number of orderings (see 2.).

$\implies$ there is a loop somewhere in the sequence.
$\implies$ either it loops back to the starting ordering or it loops to another ordering in the sequence.

But we know that it doesn't loop back to the starting ordering because that contradicts our assumption that it doesn't.

Thus, the sequence loops to another ordering in the sequence.

$$\implies\Longleftarrow$$

This is a contradiction. In order for the sequence to loop to another ordering in the sequence, the function would have to be not one-to-one because two elements in the domain would map to the same element in the range.

$\therefore$ We conclude that repeated applications on the algorithm always leads back to the original case.

As a side note, this same proof works for proving that the repeated application of a certain algorithm on a rubix cubes always leads back to the original rubix cube

share|improve this question
1  
What do you want? A formula for how many times it will take to revert back to its original? Do you want us to explain your findings? I'm not convinced that there's anything "mathematically significant" in this algorithm, but I'm sure we could do the best to explain any questions you had about the nature of this algorithm. –  Soke Feb 9 at 5:29
1  
The algorithm can be modeled as a permutation of the cards. The number of rounds needed is the order of the permutation as an element of the group, and this can be calculated easily once you know the cycle structure of the permutation. If you write down the permutations corresponding to various values of the size of the deck, you may see enough patterns to figure out what's going on in general. –  Gerry Myerson Feb 9 at 5:39
    
@user92774 Why do primes go through so many more rounds? Why do I observe such properties of the algorithm? –  Quincunx Feb 9 at 6:10
1  
Sorry; you don't find what clear? –  Gerry Myerson Feb 9 at 7:53
1  
It doesn't seem that primes having unusually high values holds up. The sequence of numbers that have a new high number of rounds is (according to my calculations, be sure to check yourself) 1, 2, 3, 5, 6, 11, 14, 24, 31, 52, 54, 61, 63, 81, 82... (this isn't in the OEIS). Only 6 of those 15 are prime, and 82 is particularly unusually big (55440). There are also primes like 79 (24) which are very small compared to their surroundings. –  Joseph Geipel Feb 10 at 20:06

2 Answers 2

up vote 1 down vote accepted
+100

Just some elements that might help for a better understanding.

As noticed already, if we have $n$ cards a round correspond to a permutation of $n$ elements. We try to understand this permutation, and in particular we want to know the order of this permutation (i.e. the number of times we should repeat this permutation to obtain the original order). We can write a permuations in 2 differente ways. $$\{1,2,3,4,5,6,7,8\}\rightarrow\{8,4,6,2,7,5,3,1\} $$ or $$(1,8)(2,4)(3,6,5,7).$$ The last representation means, $1$ and $8$ swap, $2$ and $4$ swap, $3$ becomes $6$, $6$ becomes $5$, $5$ becomes $7$ and $7$ becomes $3$. We call it cyclic representation. The order of the permutation is the smallest comon multiple of the length of the circles.

About the case of a power of two: We can proove by induction that for any $n$, $$\{1,\ldots,2^n\}\rightarrow\{2^n;2^{n-1};2^{n-2}.3,2^{n-2}.1;\ldots;2^{n-k}.(2^k-1),2^{n-k}.(2^k-3),\ldots,2^{n-k}.3,2^{n-k}.1;\ldots;2^n-1,2^n-3,\ldots,5,3,1\}.$$ Notice the use of semicolon $;$ here is just to stress some special groups of numbers of length $1$, $1$, $2$,...,$2^{k-1}$,...,$2^{n-1}$.

With this description, one can see that for any $k\leq n$, $2^k$ and $2^{n-k}$ swap. More generally we can see that for any $k\leq n$ and any $l$ such that $2l+1\leq 2^{n-k}$, we have that $2^{n-k}-l$ becomes $2^k(2l+1)$, but I did not figure out how that could help.

In the following I give the cyclic representation of the permutations when we have $2^n$ cards, for $1\leq n\leq 7$:

  1. $(1,2)$
  2. $(1,4)$
  3. $(1,8)(2,4)(3,6,5,7)$
  4. $(1,16)(2,8)(3,12,9,15)(5,14)(6,10,13,7)$
  5. $(1,32)(2,16)(3,24,17,31)(4,8)(5,28,9,30)(6,20,25,15)(7,12,18,29)(10,26,13,14)(11,22,21,23,19,27)$
  6. $(1,64)(2,32)(3,48,33,63)(4,16)(5,56,17,62)(6,40,49,31)(7,24,34,61)(9,60)(10,52,25,30)(11,44,41,47,35,59)(12,36,57,15)(13,28,18,58)(14,20,50,29)(19,54,21,46,37,55)(22,42,45,39,51,27)(23,38,53)$
  7. $(1,128)(2,64)(3,96,65,127)(4,32)(5,112,33,126)(6,80,97,63)(7,48,66,125)(8,16)(9,120,17,124)(10,104,49,62)(11,88,81,95,67,123)(12,72,113,31)(13,56,34,122)(14,40,98,61)(15,24,68,121)(18,116,25,60)(19,108,41,94,69,119)(20,100,57,30)(21,92,73,111,35,118)(22,84,89,79,99,59)(23,76,105,47,70,117)(26,52,50,58)(27,44,82,93,71,115)(28,36,114,29)(37,110)(38,106,45,78,101,55)(39,102,53,46,74,109)(42,90,77,103,51,54)(43,86,85,87,83,91,75,107)$

Edit I am adding here some grphique obtained with mathematica. In the two following picture we observe the irregularity of the order of the permutation when the number of cards varies. The first picture show the orders when we have up to $100$ cards. The second show the same thing up to $2000$ cards.

Orders for $n$ elements with $1\leq n\leq 100 enter image description here

On the other hand the following diagram seem to show some kind of regularity of the order when we consider $2^k$ cards (with $1\leq k\leq 16$).

enter image description here

More precisely, here are the value $o_k$ of the order of the permutation when we consider $2^k$ cards:

  • $o_1=o_2=2$
  • $o_3=o_4=4=2^2=2o_2$
  • $o_5=o_6=12=2^2.3=3o_4$
  • $o_7=o_8=24=2^3.3=2o_6$
  • $o_9=o_{10}=o_{11}=o_{12}=120=2^3.3.5=5o_8$
  • $o_{13}=o_{14}=840=2^3.3.5.7=7o_{12}$
  • $o_{15}=o_{16}=1680=2^4.3.5.7=2o_{14}$
  • $o_{17}=o_{18}=5040=2^4.3^2.5.7=3o_{16}$

It seems that we have $o_{2l+1}=o_{2l}$ and that they divide $o_{2k+2}$. Maybe this is provable by induction but I did not find it yet.

share|improve this answer

Partial answer: Here is powers of two:

Let's investigate the first few powers of two. Let the left-to-right order denote the top-to-bottom permutation of the cards. Here goes:

$\{ a_1, a_2\} \rightarrow \{a_2, a_1\}$

$\{a_1, a_2, a_3, a_4\} \rightarrow \{a_4, a_2, a_3, a_1\}$

$\{a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8\} \rightarrow \{a_8, a_4, a_6, a_2, a_7, a_5, a_3, a_1\}$

In this last case, there are a few things going on:

First cycle: $1 \rightarrow 8 \rightarrow 1$

Second cycle: $2 \rightarrow 4 \rightarrow 2$

Third cycle: $3 \rightarrow 7 \rightarrow 5 \rightarrow 6 \rightarrow 3$

So to find the number of cycles required, find the LCM of the cycle lengths.

This is how you would make sense of the pattern: If we read right to left, first we deal with the odds in an increasing order, and then our set of $2^n$ cards is reduced to a set of $2^{n-1}$ cards in the form of $\{2, 4, 6, \dots, 2^n\}$. So then, the "odds" of this set (congruent to $2 \pmod 4$) are picked out, giving us $2^{n-1}$ cards in the form $\{4, 8, 12, \dots, 2^n\}$. Then $4 \pmod 8$ are picked out in increasing order and so forth until we run out of cards. I'm not sure yet if we can make a closed form generalization for any $2^n$ cards (though it's apparent that the first and last cards will switch places).

Another example:

$\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16\} \rightarrow \{16, 8, 12, 4, 14, 10, 6, 2, 15, 13, 11, 9, 7, 5, 3, 1\}$

$1 \to 16$

$2 \to 8$

$3 \to 15 \to 9 \to 12$

$4 \to 4$

$11 \to 11$

$5 \to 14$

$6 \to 7 \to 13 \to 10$

Again, the number of cycles would be $4$.

In a deck of $2^n$ cards, the numbers $2^{n-1}$ and $2$ swap positions, as well as the numbers $2^n$ and $1$.

Some examples of prime numbers:

$\{1, 2, 3, 4, 5, 6, 7\} \rightarrow \{6, 2, 4, 7, 5, 3, 1\}$

Which gives the permutation $(17436)$

$\{1, 2, 3, 4, 5, 6, 7, 8, 9, A, B\} \rightarrow \{6, A, 2, 8, 4, B, 9, 7, 5, 3, 1\}$

(For the sake of cycle notation I am using $A = 10, B = 11$)

Which gives the permutation $(1B6)(23A)(45978)$, so the required number of cycles would be $3 \times 5 = 15$

share|improve this answer
    
Next step is to write these as permutations, in cycle notation. –  Gerry Myerson Feb 9 at 7:54
    
@user92774 "In a deck of 2n cards, the numbers 2n−1 and 2 swap positions, as well as the numbers 2n and 1." After doing some computations I actually find more generally that $2^k$ and $2^{n-k}$ swap positions for any $0\leq k\leq n$. –  Gilles Bonnet Feb 14 at 20:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.