2022.04.22 MATH 3600 Permutations and Cards

71 days ago by calkin

show(Permutations(52).random_element().cycle_tuples()) 
       
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()) 
       
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.