2
$\begingroup$

Suppose you have a deck of $n$ cards; e.g., $n{=}12$: $$ (1,2,3,4,5,6,7,8,9,10,11,12) \;. $$ Cut the deck into $k$ equal-sized pieces, where $k|n$; e.g., for $k{=}4$, the $12$ cards are partitioned into $4$ piles, each of $m=n/k=3$ cards: $$ \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \\ \end{array} \right) \;. $$ Now perfectly shuffle them by selecting the top card from stack $1$, the top card from stack $2$, and so on, walking down the columns of the matrix above, resulting in this shuffled deck of cards: $$ (1,4,7,10,2,5,8,11,3,6,9,12) \;. $$ Continue in this manner until the deck of cards returns to its initial sorting: $$ \left( \begin{array}{cccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 1 & 4 & 7 & 10 & 2 & 5 & 8 & 11 & 3 & 6 & 9 & 12 \\ 1 & 10 & 8 & 6 & 4 & 2 & 11 & 9 & 7 & 5 & 3 & 12 \\ 1 & 6 & 11 & 5 & 10 & 4 & 9 & 3 & 8 & 2 & 7 & 12 \\ 1 & 5 & 9 & 2 & 6 & 10 & 3 & 7 & 11 & 4 & 8 & 12 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \end{array} \right) \;. $$ Here, for $n{=}12$ cards partitioned into $k{=}4$ parts, it requires $s{=}5$ perfect shuffles to cycle. Let us say that $f(n,k)=s$, i.e., $f(12,4)=5$. Similarly I can calculate that $$ f(8,2)=3,\; f(18,3)=16,\; f(33,3)=8, \; f(52,2)=8, $$ etc. The last represents a perfect "outer-shuffle" of a standard $52$-card deck, which is known to take $8$ shuffles to cycle. It seems likely this function is known to combinatorialists:

Q. What is $f(n,k)$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Seems to be the order of $k$ mod $n-1$. (This is well known for the usual perfect outer shuffle, and seems numerically to work in your other examples.) $\endgroup$
    – Lucia
    Nov 22, 2014 at 3:08
  • $\begingroup$ If you label the cards $0$ to $n-1$ then your shuffle corresponds to multiplying card $i$ by the inverse of $k$ modulo $n-1$. Thus it returns to the original configuration in the order of $k^{-1}$ mod $n-1$ steps. But this is the same as the order of $k$ mod $n-1$. $\endgroup$
    – Lucia
    Nov 22, 2014 at 3:15

1 Answer 1

Reset to default
5
$\begingroup$

This is just my comment above, which seems to answer the question. Label the cards from $0$ to $n-1$. Then, with $m=n/k$, the shuffle in the question corresponds to multiplying card $i$ by $m$ (taken mod $n-1$). Thus repeating the shuffle $r$ times amounts to multiplying by $m^r \pmod{n-1}$, which returns us to the original configuration after the order of $m \pmod{n-1}$ times. Since $mk\equiv 1\pmod{n-1}$, this is also the order of $k \pmod{n-1}$. For more information on perfect shuffles see Diaconis, Graham, Kantor.

Improve this answer
$\endgroup$
1
  • $\begingroup$ So for $k{=}4$ and $n{-}1=11$, $4^2 \equiv 5$, $4^3 \equiv 9$, $4^4 \equiv 3$, $4^5 \equiv 1$. So $f(12,4)=5$. Nice! $\endgroup$
    – Joseph O'Rourke
    Nov 22, 2014 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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