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.
7 years, 8 months ago
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:
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"\(...\)or\[...\]to ensure proper formatting.2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
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]
Log in to reply
Now, in the light of your enumeration, since 192=3⋅64, my immediate guess would be that it halts for either n square, or for n a power of two. The option that n=m2 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.
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!
Log in to reply
That's true! If it wasn't already there in the OEIS, my guess would have taken much more time
Observed the following:
We need to find the least 'a' such that
3a≡±1(mod3n+1)
for the rearrangement to end up in the reversed order or the original order.
If 3a≡−1(mod3n+1) , the rearrangement ends up in reversed order.
Considering the problem of 192 cards, n=64, and 38≡192(mod193), which means it requires 8 shuffles to get the result.
dude ?!! what is that??? man
Log in to reply
dude ?!! what is that??? man