2022.04.22 MATH 3600 Permutations and Cards

71 days ago by calkin

show(Permutations(52).random_element().cycle_tuples())
 \newcommand{\Bold}[1]{\mathbf{#1}}\left[\left(1, 33, 44, 29, 5, 51, 25, 6, 49, 17, 2\right), \left(3, 36, 8, 10, 7, 47, 42, 21, 32, 38, 13, 28, 39, 22, 26, 34, 9, 31, 48\right), \left(4, 15, 46, 23, 18, 30, 50, 16, 11, 40, 37, 20, 19\right), \left(12, 27, 41, 35, 24, 14, 45, 43, 52\right)\right]
p=Permutations(52).random_element() print(p)
 [45, 29, 20, 32, 5, 9, 31, 13, 38, 11, 25, 14, 22, 24, 34, 3, 49, 44, 43, 51, 10, 23, 17, 4, 27, 33, 52, 1, 19, 47, 8, 26, 39, 15, 37, 50, 2, 41, 21, 30, 46, 48, 12, 16, 42, 6, 35, 18, 7, 40, 36, 28] [45, 29, 20, 32, 5, 9, 31, 13, 38, 11, 25, 14, 22, 24, 34, 3, 49, 44, 43, 51, 10, 23, 17, 4, 27, 33, 52, 1, 19, 47, 8, 26, 39, 15, 37, 50, 2, 41, 21, 30, 46, 48, 12, 16, 42, 6, 35, 18, 7, 40, 36, 28]
show(p.cycle_tuples())
 \newcommand{\Bold}[1]{\mathbf{#1}}\left[\left(1, 45, 42, 48, 18, 44, 16, 3, 20, 51, 36, 50, 40, 30, 47, 35, 37, 2, 29, 19, 43, 12, 14, 24, 4, 32, 26, 33, 39, 21, 10, 11, 25, 27, 52, 28\right), \left(5\right), \left(6, 9, 38, 41, 46\right), \left(7, 31, 8, 13, 22, 23, 17, 49\right), \left(15, 34\right)\right]
q=[ p[i] %13 for i in srange(52)]
print(q)
 [6, 3, 7, 6, 5, 9, 5, 0, 12, 11, 12, 1, 9, 11, 8, 3, 10, 5, 4, 12, 10, 10, 4, 4, 1, 7, 0, 1, 6, 8, 8, 0, 0, 2, 11, 11, 2, 2, 8, 4, 7, 9, 12, 3, 3, 6, 9, 5, 7, 1, 10, 2] [6, 3, 7, 6, 5, 9, 5, 0, 12, 11, 12, 1, 9, 11, 8, 3, 10, 5, 4, 12, 10, 10, 4, 4, 1, 7, 0, 1, 6, 8, 8, 0, 0, 2, 11, 11, 2, 2, 8, 4, 7, 9, 12, 3, 3, 6, 9, 5, 7, 1, 10, 2]

Perfect Shuffles

If we perform an in-shuffle on $2n$ cards, the card in position $k$ is moved to position $2k$ (mod 2n+1).

Since $2n+1$ is odd, 2 and $2n+1$ have no common factors, so $2$ is invertible mod $2n+1$.

Indeed, $2^{-1}=n+1$ (mod $2n+1$).  Hence the sequence $1, 2, 2^2, 2^3, \dots 2^j$ mod $2n+1$, eventually returns to 1.

in_shuffle_52 = [2^j %53 for j in srange(53)]
print(in_shuffle_52)
 [1, 2, 4, 8, 16, 32, 11, 22, 44, 35, 17, 34, 15, 30, 7, 14, 28, 3, 6, 12, 24, 48, 43, 33, 13, 26, 52, 51, 49, 45, 37, 21, 42, 31, 9, 18, 36, 19, 38, 23, 46, 39, 25, 50, 47, 41, 29, 5, 10, 20, 40, 27, 1] [1, 2, 4, 8, 16, 32, 11, 22, 44, 35, 17, 34, 15, 30, 7, 14, 28, 3, 6, 12, 24, 48, 43, 33, 13, 26, 52, 51, 49, 45, 37, 21, 42, 31, 9, 18, 36, 19, 38, 23, 46, 39, 25, 50, 47, 41, 29, 5, 10, 20, 40, 27, 1]

We say that the order of 2 mod 53 is 52.  This means that 2 is a "primitive root" mod 53.

What happens for out-shuffles on 52 cards?  These behave like in-shuffles on 50 cards, so we want to know the order of 2 mod 51.  51 = 3x17.  We can find the order of 2 mod 3 and the order of 2 mod 17, and combine to find the order of 2 mod 51.

The order of 2 mod 3: $2^1 =2, 2^=4 = 1$ mod 3. So, mod 3, the order of 2 is 2.

The order of 2 mod 17: $2^1=2, 2^2=4, 2^3=8, 2^4=16 = -1$ mod 17, so $2^8=1$ mod 17,

so the order of 2 mod 17 is 8.  So the order of 2 mod 51 is 8.

This means that after 8 out-shuffles of a regular deck of 52 cards, the deck is returned  to its original order.

This motivates us to consider the order of 2 mod 2n+1, as $n$ ranges from 1 to infinity.

Some questions to explore:

What happens if 2n+1 is prime?

What happens if 2n+1 is composite?

How often is the order of 2 mod 2n+1 equal to 2n?  This can only happen if 2n+1 is prime.