Restoring order in a deck of playing cards (I)
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{
margin-bottom:0;
}
.everyonelovesstackoverflow{position:absolute;height:1px;width:1px;opacity:0;top:0;left:0;pointer-events:none;}
$begingroup$
Michelle has a deck of 52 playing cards, stacked in a pile with their backs facing up. She takes the first 2 cards in the pile, turns them over, and places them at the bottom of the pile. She now takes the next 3 cards in the pile and, once again, turns them over, and places them at the bottom of the pile. She proceeds like this, taking each time the next prime number of cards from the top, turning them over, and placing them at the bottom of the deck. Once she has done this for all all primes up to 47 (the largest prime less than 52), she continues in the same fashion counting in turn 2, 3, 5, etc. cards from the top and placing them at the bottom of the deck.
Will the deck of cards ever have all their backs facing up again?
mathematics combinatorics computer-puzzle
$endgroup$
add a comment
|
$begingroup$
Michelle has a deck of 52 playing cards, stacked in a pile with their backs facing up. She takes the first 2 cards in the pile, turns them over, and places them at the bottom of the pile. She now takes the next 3 cards in the pile and, once again, turns them over, and places them at the bottom of the pile. She proceeds like this, taking each time the next prime number of cards from the top, turning them over, and placing them at the bottom of the deck. Once she has done this for all all primes up to 47 (the largest prime less than 52), she continues in the same fashion counting in turn 2, 3, 5, etc. cards from the top and placing them at the bottom of the deck.
Will the deck of cards ever have all their backs facing up again?
mathematics combinatorics computer-puzzle
$endgroup$
add a comment
|
$begingroup$
Michelle has a deck of 52 playing cards, stacked in a pile with their backs facing up. She takes the first 2 cards in the pile, turns them over, and places them at the bottom of the pile. She now takes the next 3 cards in the pile and, once again, turns them over, and places them at the bottom of the pile. She proceeds like this, taking each time the next prime number of cards from the top, turning them over, and placing them at the bottom of the deck. Once she has done this for all all primes up to 47 (the largest prime less than 52), she continues in the same fashion counting in turn 2, 3, 5, etc. cards from the top and placing them at the bottom of the deck.
Will the deck of cards ever have all their backs facing up again?
mathematics combinatorics computer-puzzle
$endgroup$
Michelle has a deck of 52 playing cards, stacked in a pile with their backs facing up. She takes the first 2 cards in the pile, turns them over, and places them at the bottom of the pile. She now takes the next 3 cards in the pile and, once again, turns them over, and places them at the bottom of the pile. She proceeds like this, taking each time the next prime number of cards from the top, turning them over, and placing them at the bottom of the deck. Once she has done this for all all primes up to 47 (the largest prime less than 52), she continues in the same fashion counting in turn 2, 3, 5, etc. cards from the top and placing them at the bottom of the deck.
Will the deck of cards ever have all their backs facing up again?
mathematics combinatorics computer-puzzle
mathematics combinatorics computer-puzzle
edited May 30 at 13:43
Bernardo Recamán Santos
asked May 27 at 13:43
Bernardo Recamán SantosBernardo Recamán Santos
3,44013 silver badges67 bronze badges
3,44013 silver badges67 bronze badges
add a comment
|
add a comment
|
3 Answers
3
active
oldest
votes
$begingroup$
The cards will again be all face down . . .
. . . after 11700 operations. I'll just show the first 20
0 0000000000000000000000000000000000000000000000000000
2 0000000000000000000000000000000000000000000000000011
3 0000000000000000000000000000000000000000000000011111
5 0000000000000000000000000000000000000000001111111111
7 0000000000000000000000000000000000011111111111111111
11 0000000000000000000000001111111111111111111111111111
13 0000000000011111111111111111111111111111111111111111
17 1111111111111111111111111111111111100000011111111111
19 1111111111111111000000111111111110000000000000000000
23 1111111111000000000000000000001111110000000000000000
29 0111111000000000000000011111111111111111110000000000
31 1111111111100000000000000000011111111111111110000001
37 1111111100000010000000011111111111111111100000000000
41 0000000000000000000000000000011111111011111100000000
43 1000000000000010000000011111111111111111111111111111
47 1111100000000000000000000000011111111011111111111110
2 1110000000000000000000000001111111101111111111111000
3 0000000000000000000000001111111101111111111111000000
5 0000000000000000000111111110111111111111100000011111
7 0000000000001111111101111111111111000000111111111111
11 0111111110111111111111100000011111111111111111111111
But if the rules are changed slightly and the cards are moved from top to bottom in the same (not reversed) sequence, it only takes $56$ operations.
0 0000000000000000000000000000000000000000000000000000
2 0000000000000000000000000000000000000000000000000011
3 0000000000000000000000000000000000000000000000011111
5 0000000000000000000000000000000000000000001111111111
7 0000000000000000000000000000000000011111111111111111
11 0000000000000000000000001111111111111111111111111111
13 0000000000011111111111111111111111111111111111111111
17 1111111111111111111111111111111111111111111111000000
19 1111111111111111111111111110000000000000000000000000
23 1111000000000000000000000000000000000000000000000000
29 0000000000000000000000000001111111111111111111111111
31 1111111111111111111111111111111111111111111111110000
37 1111111111100000000000000000000000000000000000000000
41 0000000000000000000000111111111111111111111111111111
43 1111111111111111111111111111111000000000000000000000
47 0000000000000000000000000000000000001111111111111111
2 0000000000000000000000000000000000111111111111111111
3 0000000000000000000000000000000111111111111111111111
5 0000000000000000000000000011111111111111111111111111
7 0000000000000000000111111111111111111111111111111111
11 0000000011111111111111111111111111111111111111111111
13 1111111111111111111111111111111111111111111111100000
17 1111111111111111111111111111110000000000000000000000
19 1111111111100000000000000000000000000000000000000000
23 0000000000000000000000000000000000000000111111111111
29 0000000000011111111111111111111111111111111111111111
31 1111111111111111111111111111111100000000000000000000
37 0000000000000000000000000000000000000000000000011111
41 0000001111111111111111111111111111111111111111111111
43 1111111111111110000000000000000000000000000000000000
47 0000000000000000000011111111111111111111111111111111
2 0000000000000000001111111111111111111111111111111111
3 0000000000000001111111111111111111111111111111111111
5 0000000000111111111111111111111111111111111111111111
7 0001111111111111111111111111111111111111111111111111
11 1111111111111111111111111111111111111111111100000000
13 1111111111111111111111111111111000000000000000000000
17 1111111111111100000000000000000000000000000000000000
19 0000000000000000000000000000000000000000000000011111
23 0000000000000000000000001111111111111111111111111111
29 1111111111111111111111111111111111111111111111100000
31 1111111111111111000000000000000000000000000000000000
37 0000000000000000000000000000000111111111111111111111
41 1111111111111111111111111111111111111111110000000000
43 0000000000000000000000000000000000000000000000000001
47 0000111111111111111111111111111111111111111111111111
2 0011111111111111111111111111111111111111111111111111
3 1111111111111111111111111111111111111111111111111110
5 1111111111111111111111111111111111111111111111000000
7 1111111111111111111111111111111111111110000000000000
11 1111111111111111111111111111000000000000000000000000
13 1111111111111110000000000000000000000000000000000000
17 0000000000000000000000000000000000000000000000000011
19 0000000000000000000000000000000111111111111111111111
23 0000000011111111111111111111111111111111111111111111
29 1111111111111111111111111111111000000000000000000000
31 0000000000000000000000000000000000000000000000000000
result = 56
Found by C program.
$endgroup$
add a comment
|
$begingroup$
Answer:
Yes.
Reasoning:
Let's call the process of turning 2, then 3, then 5, etc. up to 47 cards a batch. Performing a batch induces some permutation $p$ of the 104 faces of the cards. After $n$ batches, the induced permutation is $p^n$. However, the group of permutations of 104 faces of cards is finite, so $p$ must have finite order, i.e. there must be some $N > 0$ such that $p^N$ is the identity permutation (in this particular case $N$ would be the LCM of all lengths of cycles in $p$). So after $N$ batches, not only do the cards all have their backs facing up again, but they're even in the same order as in the beginning!
Extra:
This same reasoning shows that if you perform any fixed sequence of moves repeatedly on an initially solved Rubik's cube or other non-locking twisty puzzle often enough, you will always return to the solved position.
$endgroup$
add a comment
|
$begingroup$
Others have already got it right, but I'd like to present a more puzzle-like solution:
Going through the numbers 2-47 once produces some deck state $Y$ (some cards face-up, others face-down) from a starting deck state $X$.
Because we're given a clearly defined sequence of reversible operations, it is possible to uniquely determine $X$ given $Y$, and, of course, vice versa.
Therefore, every deck state has a unique successor, and a unique predecessor.
This allows us to imagine that every possible deck state is a snap shackle, so that the openable part (the shackle) ties the state to its successor state's permanently closed part (the ring):
Now, we have quite a bunch ($2^{52}$) of these shackles, and we are going to completely ignore what the actual transformation does. Instead we'll just connect the snap shackles to each other so that
- no ring is left without a shackle (every state has a predecessor)
- no shackle is left without a ring (every state has a successor)
- two shackles cannot connect to the same ring (the predecessor is unique)
- no shackle can connect to more than one ring (the successor is unique)
Since rules 3 and 4 prevent any kind of bifurcation, the only way to fulfil requirements 1 and 2 is to build one or more closed loops. This means that every single shackle has to be a part of a simple chain loop, regardless of what the actual transformation rules are.
Or coming back out of the analogy: If you repeat any transformation (in this case, going through numbers 2-47) many enough times, you are guaranteed to eventually end up in the original deck state.
$endgroup$
add a comment
|
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "559"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f84428%2frestoring-order-in-a-deck-of-playing-cards-i%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The cards will again be all face down . . .
. . . after 11700 operations. I'll just show the first 20
0 0000000000000000000000000000000000000000000000000000
2 0000000000000000000000000000000000000000000000000011
3 0000000000000000000000000000000000000000000000011111
5 0000000000000000000000000000000000000000001111111111
7 0000000000000000000000000000000000011111111111111111
11 0000000000000000000000001111111111111111111111111111
13 0000000000011111111111111111111111111111111111111111
17 1111111111111111111111111111111111100000011111111111
19 1111111111111111000000111111111110000000000000000000
23 1111111111000000000000000000001111110000000000000000
29 0111111000000000000000011111111111111111110000000000
31 1111111111100000000000000000011111111111111110000001
37 1111111100000010000000011111111111111111100000000000
41 0000000000000000000000000000011111111011111100000000
43 1000000000000010000000011111111111111111111111111111
47 1111100000000000000000000000011111111011111111111110
2 1110000000000000000000000001111111101111111111111000
3 0000000000000000000000001111111101111111111111000000
5 0000000000000000000111111110111111111111100000011111
7 0000000000001111111101111111111111000000111111111111
11 0111111110111111111111100000011111111111111111111111
But if the rules are changed slightly and the cards are moved from top to bottom in the same (not reversed) sequence, it only takes $56$ operations.
0 0000000000000000000000000000000000000000000000000000
2 0000000000000000000000000000000000000000000000000011
3 0000000000000000000000000000000000000000000000011111
5 0000000000000000000000000000000000000000001111111111
7 0000000000000000000000000000000000011111111111111111
11 0000000000000000000000001111111111111111111111111111
13 0000000000011111111111111111111111111111111111111111
17 1111111111111111111111111111111111111111111111000000
19 1111111111111111111111111110000000000000000000000000
23 1111000000000000000000000000000000000000000000000000
29 0000000000000000000000000001111111111111111111111111
31 1111111111111111111111111111111111111111111111110000
37 1111111111100000000000000000000000000000000000000000
41 0000000000000000000000111111111111111111111111111111
43 1111111111111111111111111111111000000000000000000000
47 0000000000000000000000000000000000001111111111111111
2 0000000000000000000000000000000000111111111111111111
3 0000000000000000000000000000000111111111111111111111
5 0000000000000000000000000011111111111111111111111111
7 0000000000000000000111111111111111111111111111111111
11 0000000011111111111111111111111111111111111111111111
13 1111111111111111111111111111111111111111111111100000
17 1111111111111111111111111111110000000000000000000000
19 1111111111100000000000000000000000000000000000000000
23 0000000000000000000000000000000000000000111111111111
29 0000000000011111111111111111111111111111111111111111
31 1111111111111111111111111111111100000000000000000000
37 0000000000000000000000000000000000000000000000011111
41 0000001111111111111111111111111111111111111111111111
43 1111111111111110000000000000000000000000000000000000
47 0000000000000000000011111111111111111111111111111111
2 0000000000000000001111111111111111111111111111111111
3 0000000000000001111111111111111111111111111111111111
5 0000000000111111111111111111111111111111111111111111
7 0001111111111111111111111111111111111111111111111111
11 1111111111111111111111111111111111111111111100000000
13 1111111111111111111111111111111000000000000000000000
17 1111111111111100000000000000000000000000000000000000
19 0000000000000000000000000000000000000000000000011111
23 0000000000000000000000001111111111111111111111111111
29 1111111111111111111111111111111111111111111111100000
31 1111111111111111000000000000000000000000000000000000
37 0000000000000000000000000000000111111111111111111111
41 1111111111111111111111111111111111111111110000000000
43 0000000000000000000000000000000000000000000000000001
47 0000111111111111111111111111111111111111111111111111
2 0011111111111111111111111111111111111111111111111111
3 1111111111111111111111111111111111111111111111111110
5 1111111111111111111111111111111111111111111111000000
7 1111111111111111111111111111111111111110000000000000
11 1111111111111111111111111111000000000000000000000000
13 1111111111111110000000000000000000000000000000000000
17 0000000000000000000000000000000000000000000000000011
19 0000000000000000000000000000000111111111111111111111
23 0000000011111111111111111111111111111111111111111111
29 1111111111111111111111111111111000000000000000000000
31 0000000000000000000000000000000000000000000000000000
result = 56
Found by C program.
$endgroup$
add a comment
|
$begingroup$
The cards will again be all face down . . .
. . . after 11700 operations. I'll just show the first 20
0 0000000000000000000000000000000000000000000000000000
2 0000000000000000000000000000000000000000000000000011
3 0000000000000000000000000000000000000000000000011111
5 0000000000000000000000000000000000000000001111111111
7 0000000000000000000000000000000000011111111111111111
11 0000000000000000000000001111111111111111111111111111
13 0000000000011111111111111111111111111111111111111111
17 1111111111111111111111111111111111100000011111111111
19 1111111111111111000000111111111110000000000000000000
23 1111111111000000000000000000001111110000000000000000
29 0111111000000000000000011111111111111111110000000000
31 1111111111100000000000000000011111111111111110000001
37 1111111100000010000000011111111111111111100000000000
41 0000000000000000000000000000011111111011111100000000
43 1000000000000010000000011111111111111111111111111111
47 1111100000000000000000000000011111111011111111111110
2 1110000000000000000000000001111111101111111111111000
3 0000000000000000000000001111111101111111111111000000
5 0000000000000000000111111110111111111111100000011111
7 0000000000001111111101111111111111000000111111111111
11 0111111110111111111111100000011111111111111111111111
But if the rules are changed slightly and the cards are moved from top to bottom in the same (not reversed) sequence, it only takes $56$ operations.
0 0000000000000000000000000000000000000000000000000000
2 0000000000000000000000000000000000000000000000000011
3 0000000000000000000000000000000000000000000000011111
5 0000000000000000000000000000000000000000001111111111
7 0000000000000000000000000000000000011111111111111111
11 0000000000000000000000001111111111111111111111111111
13 0000000000011111111111111111111111111111111111111111
17 1111111111111111111111111111111111111111111111000000
19 1111111111111111111111111110000000000000000000000000
23 1111000000000000000000000000000000000000000000000000
29 0000000000000000000000000001111111111111111111111111
31 1111111111111111111111111111111111111111111111110000
37 1111111111100000000000000000000000000000000000000000
41 0000000000000000000000111111111111111111111111111111
43 1111111111111111111111111111111000000000000000000000
47 0000000000000000000000000000000000001111111111111111
2 0000000000000000000000000000000000111111111111111111
3 0000000000000000000000000000000111111111111111111111
5 0000000000000000000000000011111111111111111111111111
7 0000000000000000000111111111111111111111111111111111
11 0000000011111111111111111111111111111111111111111111
13 1111111111111111111111111111111111111111111111100000
17 1111111111111111111111111111110000000000000000000000
19 1111111111100000000000000000000000000000000000000000
23 0000000000000000000000000000000000000000111111111111
29 0000000000011111111111111111111111111111111111111111
31 1111111111111111111111111111111100000000000000000000
37 0000000000000000000000000000000000000000000000011111
41 0000001111111111111111111111111111111111111111111111
43 1111111111111110000000000000000000000000000000000000
47 0000000000000000000011111111111111111111111111111111
2 0000000000000000001111111111111111111111111111111111
3 0000000000000001111111111111111111111111111111111111
5 0000000000111111111111111111111111111111111111111111
7 0001111111111111111111111111111111111111111111111111
11 1111111111111111111111111111111111111111111100000000
13 1111111111111111111111111111111000000000000000000000
17 1111111111111100000000000000000000000000000000000000
19 0000000000000000000000000000000000000000000000011111
23 0000000000000000000000001111111111111111111111111111
29 1111111111111111111111111111111111111111111111100000
31 1111111111111111000000000000000000000000000000000000
37 0000000000000000000000000000000111111111111111111111
41 1111111111111111111111111111111111111111110000000000
43 0000000000000000000000000000000000000000000000000001
47 0000111111111111111111111111111111111111111111111111
2 0011111111111111111111111111111111111111111111111111
3 1111111111111111111111111111111111111111111111111110
5 1111111111111111111111111111111111111111111111000000
7 1111111111111111111111111111111111111110000000000000
11 1111111111111111111111111111000000000000000000000000
13 1111111111111110000000000000000000000000000000000000
17 0000000000000000000000000000000000000000000000000011
19 0000000000000000000000000000000111111111111111111111
23 0000000011111111111111111111111111111111111111111111
29 1111111111111111111111111111111000000000000000000000
31 0000000000000000000000000000000000000000000000000000
result = 56
Found by C program.
$endgroup$
add a comment
|
$begingroup$
The cards will again be all face down . . .
. . . after 11700 operations. I'll just show the first 20
0 0000000000000000000000000000000000000000000000000000
2 0000000000000000000000000000000000000000000000000011
3 0000000000000000000000000000000000000000000000011111
5 0000000000000000000000000000000000000000001111111111
7 0000000000000000000000000000000000011111111111111111
11 0000000000000000000000001111111111111111111111111111
13 0000000000011111111111111111111111111111111111111111
17 1111111111111111111111111111111111100000011111111111
19 1111111111111111000000111111111110000000000000000000
23 1111111111000000000000000000001111110000000000000000
29 0111111000000000000000011111111111111111110000000000
31 1111111111100000000000000000011111111111111110000001
37 1111111100000010000000011111111111111111100000000000
41 0000000000000000000000000000011111111011111100000000
43 1000000000000010000000011111111111111111111111111111
47 1111100000000000000000000000011111111011111111111110
2 1110000000000000000000000001111111101111111111111000
3 0000000000000000000000001111111101111111111111000000
5 0000000000000000000111111110111111111111100000011111
7 0000000000001111111101111111111111000000111111111111
11 0111111110111111111111100000011111111111111111111111
But if the rules are changed slightly and the cards are moved from top to bottom in the same (not reversed) sequence, it only takes $56$ operations.
0 0000000000000000000000000000000000000000000000000000
2 0000000000000000000000000000000000000000000000000011
3 0000000000000000000000000000000000000000000000011111
5 0000000000000000000000000000000000000000001111111111
7 0000000000000000000000000000000000011111111111111111
11 0000000000000000000000001111111111111111111111111111
13 0000000000011111111111111111111111111111111111111111
17 1111111111111111111111111111111111111111111111000000
19 1111111111111111111111111110000000000000000000000000
23 1111000000000000000000000000000000000000000000000000
29 0000000000000000000000000001111111111111111111111111
31 1111111111111111111111111111111111111111111111110000
37 1111111111100000000000000000000000000000000000000000
41 0000000000000000000000111111111111111111111111111111
43 1111111111111111111111111111111000000000000000000000
47 0000000000000000000000000000000000001111111111111111
2 0000000000000000000000000000000000111111111111111111
3 0000000000000000000000000000000111111111111111111111
5 0000000000000000000000000011111111111111111111111111
7 0000000000000000000111111111111111111111111111111111
11 0000000011111111111111111111111111111111111111111111
13 1111111111111111111111111111111111111111111111100000
17 1111111111111111111111111111110000000000000000000000
19 1111111111100000000000000000000000000000000000000000
23 0000000000000000000000000000000000000000111111111111
29 0000000000011111111111111111111111111111111111111111
31 1111111111111111111111111111111100000000000000000000
37 0000000000000000000000000000000000000000000000011111
41 0000001111111111111111111111111111111111111111111111
43 1111111111111110000000000000000000000000000000000000
47 0000000000000000000011111111111111111111111111111111
2 0000000000000000001111111111111111111111111111111111
3 0000000000000001111111111111111111111111111111111111
5 0000000000111111111111111111111111111111111111111111
7 0001111111111111111111111111111111111111111111111111
11 1111111111111111111111111111111111111111111100000000
13 1111111111111111111111111111111000000000000000000000
17 1111111111111100000000000000000000000000000000000000
19 0000000000000000000000000000000000000000000000011111
23 0000000000000000000000001111111111111111111111111111
29 1111111111111111111111111111111111111111111111100000
31 1111111111111111000000000000000000000000000000000000
37 0000000000000000000000000000000111111111111111111111
41 1111111111111111111111111111111111111111110000000000
43 0000000000000000000000000000000000000000000000000001
47 0000111111111111111111111111111111111111111111111111
2 0011111111111111111111111111111111111111111111111111
3 1111111111111111111111111111111111111111111111111110
5 1111111111111111111111111111111111111111111111000000
7 1111111111111111111111111111111111111110000000000000
11 1111111111111111111111111111000000000000000000000000
13 1111111111111110000000000000000000000000000000000000
17 0000000000000000000000000000000000000000000000000011
19 0000000000000000000000000000000111111111111111111111
23 0000000011111111111111111111111111111111111111111111
29 1111111111111111111111111111111000000000000000000000
31 0000000000000000000000000000000000000000000000000000
result = 56
Found by C program.
$endgroup$
The cards will again be all face down . . .
. . . after 11700 operations. I'll just show the first 20
0 0000000000000000000000000000000000000000000000000000
2 0000000000000000000000000000000000000000000000000011
3 0000000000000000000000000000000000000000000000011111
5 0000000000000000000000000000000000000000001111111111
7 0000000000000000000000000000000000011111111111111111
11 0000000000000000000000001111111111111111111111111111
13 0000000000011111111111111111111111111111111111111111
17 1111111111111111111111111111111111100000011111111111
19 1111111111111111000000111111111110000000000000000000
23 1111111111000000000000000000001111110000000000000000
29 0111111000000000000000011111111111111111110000000000
31 1111111111100000000000000000011111111111111110000001
37 1111111100000010000000011111111111111111100000000000
41 0000000000000000000000000000011111111011111100000000
43 1000000000000010000000011111111111111111111111111111
47 1111100000000000000000000000011111111011111111111110
2 1110000000000000000000000001111111101111111111111000
3 0000000000000000000000001111111101111111111111000000
5 0000000000000000000111111110111111111111100000011111
7 0000000000001111111101111111111111000000111111111111
11 0111111110111111111111100000011111111111111111111111
But if the rules are changed slightly and the cards are moved from top to bottom in the same (not reversed) sequence, it only takes $56$ operations.
0 0000000000000000000000000000000000000000000000000000
2 0000000000000000000000000000000000000000000000000011
3 0000000000000000000000000000000000000000000000011111
5 0000000000000000000000000000000000000000001111111111
7 0000000000000000000000000000000000011111111111111111
11 0000000000000000000000001111111111111111111111111111
13 0000000000011111111111111111111111111111111111111111
17 1111111111111111111111111111111111111111111111000000
19 1111111111111111111111111110000000000000000000000000
23 1111000000000000000000000000000000000000000000000000
29 0000000000000000000000000001111111111111111111111111
31 1111111111111111111111111111111111111111111111110000
37 1111111111100000000000000000000000000000000000000000
41 0000000000000000000000111111111111111111111111111111
43 1111111111111111111111111111111000000000000000000000
47 0000000000000000000000000000000000001111111111111111
2 0000000000000000000000000000000000111111111111111111
3 0000000000000000000000000000000111111111111111111111
5 0000000000000000000000000011111111111111111111111111
7 0000000000000000000111111111111111111111111111111111
11 0000000011111111111111111111111111111111111111111111
13 1111111111111111111111111111111111111111111111100000
17 1111111111111111111111111111110000000000000000000000
19 1111111111100000000000000000000000000000000000000000
23 0000000000000000000000000000000000000000111111111111
29 0000000000011111111111111111111111111111111111111111
31 1111111111111111111111111111111100000000000000000000
37 0000000000000000000000000000000000000000000000011111
41 0000001111111111111111111111111111111111111111111111
43 1111111111111110000000000000000000000000000000000000
47 0000000000000000000011111111111111111111111111111111
2 0000000000000000001111111111111111111111111111111111
3 0000000000000001111111111111111111111111111111111111
5 0000000000111111111111111111111111111111111111111111
7 0001111111111111111111111111111111111111111111111111
11 1111111111111111111111111111111111111111111100000000
13 1111111111111111111111111111111000000000000000000000
17 1111111111111100000000000000000000000000000000000000
19 0000000000000000000000000000000000000000000000011111
23 0000000000000000000000001111111111111111111111111111
29 1111111111111111111111111111111111111111111111100000
31 1111111111111111000000000000000000000000000000000000
37 0000000000000000000000000000000111111111111111111111
41 1111111111111111111111111111111111111111110000000000
43 0000000000000000000000000000000000000000000000000001
47 0000111111111111111111111111111111111111111111111111
2 0011111111111111111111111111111111111111111111111111
3 1111111111111111111111111111111111111111111111111110
5 1111111111111111111111111111111111111111111111000000
7 1111111111111111111111111111111111111110000000000000
11 1111111111111111111111111111000000000000000000000000
13 1111111111111110000000000000000000000000000000000000
17 0000000000000000000000000000000000000000000000000011
19 0000000000000000000000000000000111111111111111111111
23 0000000011111111111111111111111111111111111111111111
29 1111111111111111111111111111111000000000000000000000
31 0000000000000000000000000000000000000000000000000000
result = 56
Found by C program.
edited May 27 at 14:40
answered May 27 at 14:25
Weather VaneWeather Vane
6,4061 gold badge4 silver badges26 bronze badges
6,4061 gold badge4 silver badges26 bronze badges
add a comment
|
add a comment
|
$begingroup$
Answer:
Yes.
Reasoning:
Let's call the process of turning 2, then 3, then 5, etc. up to 47 cards a batch. Performing a batch induces some permutation $p$ of the 104 faces of the cards. After $n$ batches, the induced permutation is $p^n$. However, the group of permutations of 104 faces of cards is finite, so $p$ must have finite order, i.e. there must be some $N > 0$ such that $p^N$ is the identity permutation (in this particular case $N$ would be the LCM of all lengths of cycles in $p$). So after $N$ batches, not only do the cards all have their backs facing up again, but they're even in the same order as in the beginning!
Extra:
This same reasoning shows that if you perform any fixed sequence of moves repeatedly on an initially solved Rubik's cube or other non-locking twisty puzzle often enough, you will always return to the solved position.
$endgroup$
add a comment
|
$begingroup$
Answer:
Yes.
Reasoning:
Let's call the process of turning 2, then 3, then 5, etc. up to 47 cards a batch. Performing a batch induces some permutation $p$ of the 104 faces of the cards. After $n$ batches, the induced permutation is $p^n$. However, the group of permutations of 104 faces of cards is finite, so $p$ must have finite order, i.e. there must be some $N > 0$ such that $p^N$ is the identity permutation (in this particular case $N$ would be the LCM of all lengths of cycles in $p$). So after $N$ batches, not only do the cards all have their backs facing up again, but they're even in the same order as in the beginning!
Extra:
This same reasoning shows that if you perform any fixed sequence of moves repeatedly on an initially solved Rubik's cube or other non-locking twisty puzzle often enough, you will always return to the solved position.
$endgroup$
add a comment
|
$begingroup$
Answer:
Yes.
Reasoning:
Let's call the process of turning 2, then 3, then 5, etc. up to 47 cards a batch. Performing a batch induces some permutation $p$ of the 104 faces of the cards. After $n$ batches, the induced permutation is $p^n$. However, the group of permutations of 104 faces of cards is finite, so $p$ must have finite order, i.e. there must be some $N > 0$ such that $p^N$ is the identity permutation (in this particular case $N$ would be the LCM of all lengths of cycles in $p$). So after $N$ batches, not only do the cards all have their backs facing up again, but they're even in the same order as in the beginning!
Extra:
This same reasoning shows that if you perform any fixed sequence of moves repeatedly on an initially solved Rubik's cube or other non-locking twisty puzzle often enough, you will always return to the solved position.
$endgroup$
Answer:
Yes.
Reasoning:
Let's call the process of turning 2, then 3, then 5, etc. up to 47 cards a batch. Performing a batch induces some permutation $p$ of the 104 faces of the cards. After $n$ batches, the induced permutation is $p^n$. However, the group of permutations of 104 faces of cards is finite, so $p$ must have finite order, i.e. there must be some $N > 0$ such that $p^N$ is the identity permutation (in this particular case $N$ would be the LCM of all lengths of cycles in $p$). So after $N$ batches, not only do the cards all have their backs facing up again, but they're even in the same order as in the beginning!
Extra:
This same reasoning shows that if you perform any fixed sequence of moves repeatedly on an initially solved Rubik's cube or other non-locking twisty puzzle often enough, you will always return to the solved position.
answered May 27 at 14:05
MagmaMagma
4568 bronze badges
4568 bronze badges
add a comment
|
add a comment
|
$begingroup$
Others have already got it right, but I'd like to present a more puzzle-like solution:
Going through the numbers 2-47 once produces some deck state $Y$ (some cards face-up, others face-down) from a starting deck state $X$.
Because we're given a clearly defined sequence of reversible operations, it is possible to uniquely determine $X$ given $Y$, and, of course, vice versa.
Therefore, every deck state has a unique successor, and a unique predecessor.
This allows us to imagine that every possible deck state is a snap shackle, so that the openable part (the shackle) ties the state to its successor state's permanently closed part (the ring):
Now, we have quite a bunch ($2^{52}$) of these shackles, and we are going to completely ignore what the actual transformation does. Instead we'll just connect the snap shackles to each other so that
- no ring is left without a shackle (every state has a predecessor)
- no shackle is left without a ring (every state has a successor)
- two shackles cannot connect to the same ring (the predecessor is unique)
- no shackle can connect to more than one ring (the successor is unique)
Since rules 3 and 4 prevent any kind of bifurcation, the only way to fulfil requirements 1 and 2 is to build one or more closed loops. This means that every single shackle has to be a part of a simple chain loop, regardless of what the actual transformation rules are.
Or coming back out of the analogy: If you repeat any transformation (in this case, going through numbers 2-47) many enough times, you are guaranteed to eventually end up in the original deck state.
$endgroup$
add a comment
|
$begingroup$
Others have already got it right, but I'd like to present a more puzzle-like solution:
Going through the numbers 2-47 once produces some deck state $Y$ (some cards face-up, others face-down) from a starting deck state $X$.
Because we're given a clearly defined sequence of reversible operations, it is possible to uniquely determine $X$ given $Y$, and, of course, vice versa.
Therefore, every deck state has a unique successor, and a unique predecessor.
This allows us to imagine that every possible deck state is a snap shackle, so that the openable part (the shackle) ties the state to its successor state's permanently closed part (the ring):
Now, we have quite a bunch ($2^{52}$) of these shackles, and we are going to completely ignore what the actual transformation does. Instead we'll just connect the snap shackles to each other so that
- no ring is left without a shackle (every state has a predecessor)
- no shackle is left without a ring (every state has a successor)
- two shackles cannot connect to the same ring (the predecessor is unique)
- no shackle can connect to more than one ring (the successor is unique)
Since rules 3 and 4 prevent any kind of bifurcation, the only way to fulfil requirements 1 and 2 is to build one or more closed loops. This means that every single shackle has to be a part of a simple chain loop, regardless of what the actual transformation rules are.
Or coming back out of the analogy: If you repeat any transformation (in this case, going through numbers 2-47) many enough times, you are guaranteed to eventually end up in the original deck state.
$endgroup$
add a comment
|
$begingroup$
Others have already got it right, but I'd like to present a more puzzle-like solution:
Going through the numbers 2-47 once produces some deck state $Y$ (some cards face-up, others face-down) from a starting deck state $X$.
Because we're given a clearly defined sequence of reversible operations, it is possible to uniquely determine $X$ given $Y$, and, of course, vice versa.
Therefore, every deck state has a unique successor, and a unique predecessor.
This allows us to imagine that every possible deck state is a snap shackle, so that the openable part (the shackle) ties the state to its successor state's permanently closed part (the ring):
Now, we have quite a bunch ($2^{52}$) of these shackles, and we are going to completely ignore what the actual transformation does. Instead we'll just connect the snap shackles to each other so that
- no ring is left without a shackle (every state has a predecessor)
- no shackle is left without a ring (every state has a successor)
- two shackles cannot connect to the same ring (the predecessor is unique)
- no shackle can connect to more than one ring (the successor is unique)
Since rules 3 and 4 prevent any kind of bifurcation, the only way to fulfil requirements 1 and 2 is to build one or more closed loops. This means that every single shackle has to be a part of a simple chain loop, regardless of what the actual transformation rules are.
Or coming back out of the analogy: If you repeat any transformation (in this case, going through numbers 2-47) many enough times, you are guaranteed to eventually end up in the original deck state.
$endgroup$
Others have already got it right, but I'd like to present a more puzzle-like solution:
Going through the numbers 2-47 once produces some deck state $Y$ (some cards face-up, others face-down) from a starting deck state $X$.
Because we're given a clearly defined sequence of reversible operations, it is possible to uniquely determine $X$ given $Y$, and, of course, vice versa.
Therefore, every deck state has a unique successor, and a unique predecessor.
This allows us to imagine that every possible deck state is a snap shackle, so that the openable part (the shackle) ties the state to its successor state's permanently closed part (the ring):
Now, we have quite a bunch ($2^{52}$) of these shackles, and we are going to completely ignore what the actual transformation does. Instead we'll just connect the snap shackles to each other so that
- no ring is left without a shackle (every state has a predecessor)
- no shackle is left without a ring (every state has a successor)
- two shackles cannot connect to the same ring (the predecessor is unique)
- no shackle can connect to more than one ring (the successor is unique)
Since rules 3 and 4 prevent any kind of bifurcation, the only way to fulfil requirements 1 and 2 is to build one or more closed loops. This means that every single shackle has to be a part of a simple chain loop, regardless of what the actual transformation rules are.
Or coming back out of the analogy: If you repeat any transformation (in this case, going through numbers 2-47) many enough times, you are guaranteed to eventually end up in the original deck state.
edited May 27 at 18:11
answered May 27 at 16:34
BassBass
37.5k4 gold badges92 silver badges213 bronze badges
37.5k4 gold badges92 silver badges213 bronze badges
add a comment
|
add a comment
|
Thanks for contributing an answer to Puzzling Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f84428%2frestoring-order-in-a-deck-of-playing-cards-i%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown