# Need help with card problem

We shuffle a line of cards labelled $$a_1, a_2, ..., a_{3n}$$ from left to right by rearranging the cards into the new order $$a_3, a_6, ..., a_{3n}, a_2, a_5, ..., a_{3n-1}, a_1, a_4, ..., a_{3n-2}.$$ For example, if 6 cards are labelled $$1, 2, ...,6$$ from left to right, then shuffling them twice changes their order as follows: $$1, 2, 3, 4, 5, 6 \Rightarrow 3, 6, 2, 5, 1, 4 \Rightarrow 2, 4, 6, 1, 3, 5.$$ Starting with 192 cards labelled $$1, 2, ..., 192$$ from left to right, prove that it is possible to obtain the order $$192, 191, ..., 1$$ after a finite number of shuffles.

Note by Akash K.
4 years, 9 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 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"
MathAppears 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}$$

Sort by:

Observed the following:

We need to find the least 'a' such that

$$3^a \equiv \pm 1 \pmod{3\,n + 1}$$

for the rearrangement to end up in the reversed order or the original order.

If $$3^a \equiv -1 \pmod{3\,n + 1}$$ , the rearrangement ends up in reversed order.

Considering the problem of 192 cards, n=64, and $$3^8 \equiv 192 \pmod{193}$$, which means it requires 8 shuffles to get the result.

- 4 years, 9 months ago

One way is to prove by enumeration. It halts only for some n's, need to know what 'n' are those

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192]

[3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 153, 156, 159, 162, 165, 168, 171, 174, 177, 180, 183, 186, 189, 192, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, 101, 104, 107, 110, 113, 116, 119, 122, 125, 128, 131, 134, 137, 140, 143, 146, 149, 152, 155, 158, 161, 164, 167, 170, 173, 176, 179, 182, 185, 188, 191, 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100, 103, 106, 109, 112, 115, 118, 121, 124, 127, 130, 133, 136, 139, 142, 145, 148, 151, 154, 157, 160, 163, 166, 169, 172, 175, 178, 181, 184, 187, 190]

[9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99, 108, 117, 126, 135, 144, 153, 162, 171, 180, 189, 5, 14, 23, 32, 41, 50, 59, 68, 77, 86, 95, 104, 113, 122, 131, 140, 149, 158, 167, 176, 185, 1, 10, 19, 28, 37, 46, 55, 64, 73, 82, 91, 100, 109, 118, 127, 136, 145, 154, 163, 172, 181, 190, 6, 15, 24, 33, 42, 51, 60, 69, 78, 87, 96, 105, 114, 123, 132, 141, 150, 159, 168, 177, 186, 2, 11, 20, 29, 38, 47, 56, 65, 74, 83, 92, 101, 110, 119, 128, 137, 146, 155, 164, 173, 182, 191, 7, 16, 25, 34, 43, 52, 61, 70, 79, 88, 97, 106, 115, 124, 133, 142, 151, 160, 169, 178, 187, 3, 12, 21, 30, 39, 48, 57, 66, 75, 84, 93, 102, 111, 120, 129, 138, 147, 156, 165, 174, 183, 192, 8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107, 116, 125, 134, 143, 152, 161, 170, 179, 188, 4, 13, 22, 31, 40, 49, 58, 67, 76, 85, 94, 103, 112, 121, 130, 139, 148, 157, 166, 175, 184]

[27, 54, 81, 108, 135, 162, 189, 23, 50, 77, 104, 131, 158, 185, 19, 46, 73, 100, 127, 154, 181, 15, 42, 69, 96, 123, 150, 177, 11, 38, 65, 92, 119, 146, 173, 7, 34, 61, 88, 115, 142, 169, 3, 30, 57, 84, 111, 138, 165, 192, 26, 53, 80, 107, 134, 161, 188, 22, 49, 76, 103, 130, 157, 184, 18, 45, 72, 99, 126, 153, 180, 14, 41, 68, 95, 122, 149, 176, 10, 37, 64, 91, 118, 145, 172, 6, 33, 60, 87, 114, 141, 168, 2, 29, 56, 83, 110, 137, 164, 191, 25, 52, 79, 106, 133, 160, 187, 21, 48, 75, 102, 129, 156, 183, 17, 44, 71, 98, 125, 152, 179, 13, 40, 67, 94, 121, 148, 175, 9, 36, 63, 90, 117, 144, 171, 5, 32, 59, 86, 113, 140, 167, 1, 28, 55, 82, 109, 136, 163, 190, 24, 51, 78, 105, 132, 159, 186, 20, 47, 74, 101, 128, 155, 182, 16, 43, 70, 97, 124, 151, 178, 12, 39, 66, 93, 120, 147, 174, 8, 35, 62, 89, 116, 143, 170, 4, 31, 58, 85, 112, 139, 166]

[81, 162, 50, 131, 19, 100, 181, 69, 150, 38, 119, 7, 88, 169, 57, 138, 26, 107, 188, 76, 157, 45, 126, 14, 95, 176, 64, 145, 33, 114, 2, 83, 164, 52, 133, 21, 102, 183, 71, 152, 40, 121, 9, 90, 171, 59, 140, 28, 109, 190, 78, 159, 47, 128, 16, 97, 178, 66, 147, 35, 116, 4, 85, 166, 54, 135, 23, 104, 185, 73, 154, 42, 123, 11, 92, 173, 61, 142, 30, 111, 192, 80, 161, 49, 130, 18, 99, 180, 68, 149, 37, 118, 6, 87, 168, 56, 137, 25, 106, 187, 75, 156, 44, 125, 13, 94, 175, 63, 144, 32, 113, 1, 82, 163, 51, 132, 20, 101, 182, 70, 151, 39, 120, 8, 89, 170, 58, 139, 27, 108, 189, 77, 158, 46, 127, 15, 96, 177, 65, 146, 34, 115, 3, 84, 165, 53, 134, 22, 103, 184, 72, 153, 41, 122, 10, 91, 172, 60, 141, 29, 110, 191, 79, 160, 48, 129, 17, 98, 179, 67, 148, 36, 117, 5, 86, 167, 55, 136, 24, 105, 186, 74, 155, 43, 124, 12, 93, 174, 62, 143, 31, 112]

[50, 100, 150, 7, 57, 107, 157, 14, 64, 114, 164, 21, 71, 121, 171, 28, 78, 128, 178, 35, 85, 135, 185, 42, 92, 142, 192, 49, 99, 149, 6, 56, 106, 156, 13, 63, 113, 163, 20, 70, 120, 170, 27, 77, 127, 177, 34, 84, 134, 184, 41, 91, 141, 191, 48, 98, 148, 5, 55, 105, 155, 12, 62, 112, 162, 19, 69, 119, 169, 26, 76, 126, 176, 33, 83, 133, 183, 40, 90, 140, 190, 47, 97, 147, 4, 54, 104, 154, 11, 61, 111, 161, 18, 68, 118, 168, 25, 75, 125, 175, 32, 82, 132, 182, 39, 89, 139, 189, 46, 96, 146, 3, 53, 103, 153, 10, 60, 110, 160, 17, 67, 117, 167, 24, 74, 124, 174, 31, 81, 131, 181, 38, 88, 138, 188, 45, 95, 145, 2, 52, 102, 152, 9, 59, 109, 159, 16, 66, 116, 166, 23, 73, 123, 173, 30, 80, 130, 180, 37, 87, 137, 187, 44, 94, 144, 1, 51, 101, 151, 8, 58, 108, 158, 15, 65, 115, 165, 22, 72, 122, 172, 29, 79, 129, 179, 36, 86, 136, 186, 43, 93, 143]

[150, 107, 64, 21, 171, 128, 85, 42, 192, 149, 106, 63, 20, 170, 127, 84, 41, 191, 148, 105, 62, 19, 169, 126, 83, 40, 190, 147, 104, 61, 18, 168, 125, 82, 39, 189, 146, 103, 60, 17, 167, 124, 81, 38, 188, 145, 102, 59, 16, 166, 123, 80, 37, 187, 144, 101, 58, 15, 165, 122, 79, 36, 186, 143, 100, 57, 14, 164, 121, 78, 35, 185, 142, 99, 56, 13, 163, 120, 77, 34, 184, 141, 98, 55, 12, 162, 119, 76, 33, 183, 140, 97, 54, 11, 161, 118, 75, 32, 182, 139, 96, 53, 10, 160, 117, 74, 31, 181, 138, 95, 52, 9, 159, 116, 73, 30, 180, 137, 94, 51, 8, 158, 115, 72, 29, 179, 136, 93, 50, 7, 157, 114, 71, 28, 178, 135, 92, 49, 6, 156, 113, 70, 27, 177, 134, 91, 48, 5, 155, 112, 69, 26, 176, 133, 90, 47, 4, 154, 111, 68, 25, 175, 132, 89, 46, 3, 153, 110, 67, 24, 174, 131, 88, 45, 2, 152, 109, 66, 23, 173, 130, 87, 44, 1, 151, 108, 65, 22, 172, 129, 86, 43]

[64, 128, 192, 63, 127, 191, 62, 126, 190, 61, 125, 189, 60, 124, 188, 59, 123, 187, 58, 122, 186, 57, 121, 185, 56, 120, 184, 55, 119, 183, 54, 118, 182, 53, 117, 181, 52, 116, 180, 51, 115, 179, 50, 114, 178, 49, 113, 177, 48, 112, 176, 47, 111, 175, 46, 110, 174, 45, 109, 173, 44, 108, 172, 43, 107, 171, 42, 106, 170, 41, 105, 169, 40, 104, 168, 39, 103, 167, 38, 102, 166, 37, 101, 165, 36, 100, 164, 35, 99, 163, 34, 98, 162, 33, 97, 161, 32, 96, 160, 31, 95, 159, 30, 94, 158, 29, 93, 157, 28, 92, 156, 27, 91, 155, 26, 90, 154, 25, 89, 153, 24, 88, 152, 23, 87, 151, 22, 86, 150, 21, 85, 149, 20, 84, 148, 19, 83, 147, 18, 82, 146, 17, 81, 145, 16, 80, 144, 15, 79, 143, 14, 78, 142, 13, 77, 141, 12, 76, 140, 11, 75, 139, 10, 74, 138, 9, 73, 137, 8, 72, 136, 7, 71, 135, 6, 70, 134, 5, 69, 133, 4, 68, 132, 3, 67, 131, 2, 66, 130, 1, 65, 129]

[192, 191, 190, 189, 188, 187, 186, 185, 184, 183, 182, 181, 180, 179, 178, 177, 176, 175, 174, 173, 172, 171, 170, 169, 168, 167, 166, 165, 164, 163, 162, 161, 160, 159, 158, 157, 156, 155, 154, 153, 152, 151, 150, 149, 148, 147, 146, 145, 144, 143, 142, 141, 140, 139, 138, 137, 136, 135, 134, 133, 132, 131, 130, 129, 128, 127, 126, 125, 124, 123, 122, 121, 120, 119, 118, 117, 116, 115, 114, 113, 112, 111, 110, 109, 108, 107, 106, 105, 104, 103, 102, 101, 100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

- 4 years, 9 months ago

Now, in the light of your enumeration, since $$192 = 3\cdot 64$$, my immediate guess would be that it halts for either $$n$$ square, or for $$n$$ a power of two. The option that $$n = m^2$$ a square is more tempting, since your enumeration together with the trivial case $$n = 1$$ (with just three cards) suggests that it actually takes $$m$$ shuffles.

Edit: $$n = 4$$ (12 cards) doesn't work, it takes three shuffles to get back to the original order. So both my theories were wrong.

- 4 years, 9 months ago

It's good to always have theories and guessing about how to approach the problem.

We can't always be right, but you never know when your next guess will hit the jackpot!

Staff - 4 years, 9 months ago

That's true! If it wasn't already there in the OEIS, my guess would have taken much more time

- 4 years, 9 months ago

dude ?!! what is that??? man

- 4 years, 9 months ago

dude ?!! what is that??? man

- 4 years, 9 months ago