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)$?

$\endgroup$
  • 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 '14 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 '14 at 3:15
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.

$\endgroup$
  • $\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 '14 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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