Waste less time on Facebook — follow Brilliant.
×

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 ago

No vote yet
9 votes

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 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 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 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 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 ago

Log in to reply

dude ?!! what is that??? man

Salman Zafar - 4 years ago

Log in to reply

dude ?!! what is that??? man

Ryan Soedjak - 4 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...