Trivial In-Shuffles

Hi guys, I stumbled into something interesting and I don't know if it's important but I'd like to share it with ya'll :-)

$2^{n+1} -2$ cards can be in-shuffled $n+1$ times to get to identity

For example:

----- 2 -----: 2 Shuffles

----- 6 -----: 3 Shuffles

----- 14 -----: 4 Shuffles

----- 30 -----: 5 Shuffles

----- 62 -----: 6 Shuffles

In shuffles are when you split the card in half and interleave them with the top card becoming the second card from the top.

Here's an example with 14 cards

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

[8, 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7]

[4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11]

[2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13]

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

4 Shuffles

#Combinatorics

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

In general, if you in-shuffle $N$ cards $k$ times, and $2^k \equiv 1$ mod $(N+1),$ you get the original deck back. Your case is $N = 2^{n+1}-2$ and $k = n+1.$

Patrick Corn - 3 years, 4 months ago

Thank you! I stumbled into this special case before knowing the formula. It all makes sense now

Timothy Samson - 3 years, 4 months ago

ok ok thanks

Ayush Jain - 3 years, 3 months ago

This is very interesting. Do you have a proof of this? What happens when the number of cards is not of that form?

Agnishom Chattopadhyay - 3 years, 4 months ago

From Patrick Corn, the number of times k you have to shuffle N cards is $2^{k} = 1 (mod N + 1)$ . What this means: what is the least k such that, when you exponentiate 2 ( $2^{1} , 2^{2}, 2^{3}$ )by k and you divide it by N + 1, will give you a remainder of one.

I might post another thing for a proof of this :-)

Timothy Samson - 3 years, 4 months ago

This shuffle sends the nth card from the top to the "2n mod (N+1)"th position, so it's guaranteed to cycle once the number of shuffles k reaches the order of 2 in the cyclic group of N+1 elements. In general, fewer shuffles than this will be required, but you found a particular set of deck sizes where this k is the minimum.

Fun corollary: since 52+1 is prime, a regular card deck requires the worst case 52 shuffles before it first returns to its starting order. That is, unless you alter the order of interleaving so that the top card stays on top, in which case 8 shuffles suffice.

Dmitriy Khripkov - 3 years, 3 months ago

@Dmitriy Khripkov – ghvhjhjhvjhvghvjg

Ayush Jain - 3 years, 3 months ago

@Ayush Jain – hgvhgvhjv

Ayush Jain - 3 years, 3 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Trivial In-Shuffles

2n+1−22^{n+1} -22n+1−2 cards can be in-shuffled n+1n+1n+1 times to get to identity

Here's an example with 14 cards

Comments

$2^{n+1} -2$ cards can be in-shuffled $n+1$ times to get to identity