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, 6 months ago

No vote yet
9 votes

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
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} \)

Comments

Sort by:

Top Newest

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.

Gopinath No - 4 years, 6 months ago

Log in to reply

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]

Gopinath No - 4 years, 6 months ago

Log in to reply

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.

Arthur Mårtensson - 4 years, 6 months ago

Log in to reply

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!

Calvin Lin Staff - 4 years, 6 months ago

Log in to reply

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

Gopinath No - 4 years, 6 months ago

Log in to reply

dude ?!! what is that??? man

Salman Zafar - 4 years, 6 months ago

Log in to reply

dude ?!! what is that??? man

Ryan Soedjak - 4 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...