8
$\begingroup$

Michelle has a deck of 52 playing cards 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 primes up to 47 (the largest prime less than 52), she continues counting in the same fashion with the next primes, 53, 59, 61,..., but taking them module 52 (the residue after dividing by 52), that is 1, 7, 9, etc.

Will the deck of cards ever have all their backs facing up again?

$\endgroup$
  • 2
    $\begingroup$ I take it the only real point of the first question was to prepare the way for this one... $\endgroup$ – Gareth McCaughan May 30 at 14:03
  • $\begingroup$ @GarethMcCaughan Or this is the obvious foil to the answer of the first. You can no longer find a pattern with which to make a set. $\endgroup$ – Trenin May 30 at 14:11
  • $\begingroup$ @BernardoRecamánSantos can you please clarify the last sentence of the question, which is different from Part I? Here is says "all the cards face up again" but the cards have never been all face up. $\endgroup$ – Weather Vane May 30 at 16:20
  • $\begingroup$ @WeatherVane You are right. I meant, as in original puzzle, "all their backs facing up again". I will edit accordingly. Thanks and sorry. $\endgroup$ – Bernardo Recamán Santos May 30 at 16:43
6
$\begingroup$

Basically, what we are asking here is if a sum of primes (modulo 52) will ever result in a sum that is a multiple of 104. Intuitively I believe this should occur, but I actually ran a simple script to see if this is the case and:

I found that this first occurs when adding the 49th prime number, 227, your resulting sum is 1144, equal to 104*11, so a total of 11 cycles have occurred and you have returned to a deck with all cards facing up. This later occurs when adding 449 (sum of 2080), 653 (sum of 3016), 739 (sum of 3328), and 1063 (sum of 4680).

$\endgroup$
  • 2
    $\begingroup$ I think this is answering a slightly different question than that which is asked. The procedure is "take the pile, flip them over, place at the bottom". This means that the order of the pile is reversed. Contrast the two procedures in Weather Vane's accepted solution for the previous answer: puzzling.stackexchange.com/a/84433/18422 $\endgroup$ – hexomino May 30 at 15:31
  • $\begingroup$ But the question doesn't ask whether the pile will ever again have the cards in the original order and face up. It just asks whether they'll ever all be face up again. $\endgroup$ – Gareth McCaughan May 30 at 15:48
  • 1
    $\begingroup$ Oh, no, wait, I misunderstood @hexomino's point, which is that because you're reversing the order when you do this you aren't always just flipping (so to speak) a sliding window over the cycle of 52 cards. $\endgroup$ – Gareth McCaughan May 30 at 15:49
  • $\begingroup$ I see, I interpreted taking 2 cards and flipping them over as turning them over individually. This definitely gets a lot more complicated when the whole stack is turned over. I'll look into trying this out as well. $\endgroup$ – Michael Moschella May 30 at 16:20
  • $\begingroup$ @MichaelMoschella I made that mistake in Part I at first, when the deck was quickly restored. But the sequence of the cards is reversed when moving them to the bottom of the deck. $\endgroup$ – Weather Vane May 30 at 16:29
4
$\begingroup$

So far:

Using the same techniques as the Part I puzzle, but generating the primes.
I have run a code with $50847534$ operations, using primes $\lt 10^9$.
The deck was not restored.

Investigations proceed. . .

Update:

I have run a code with $189961812$ operations, using primes up to $4 \times 10^9$.
The deck was not restored.

Edit:

I have run a revised code with $1300005926$ operations, using primes up to $3 \times 10^{10}$.
The deck was not restored.

This is the limit (for now) of what I can do with the Visual C compiler which gives a program less than 2 Gb memory to use. I got this far by implementing the sieve of Eratosthenes with bit fields. The running time was 17 minutes.

So it appears that a mathematical or deductive proof is needed.

$\endgroup$
3
$\begingroup$

There seems to be a typo in the post, or an intentional fakeout. The setup says the cards are

in a pile with their backs facing up

meaning the deck is facing down, but the question asks whether it

will ever have all the cards face up again?

The deck has not previously been facing up, so I'll err on the side of caution and take it that the question asks whether the pile will face up more than once when shuffled in the described manner and starting face down.

EDIT: The following up to and including the C++ code has been proven wrong.

Since we are drawing cards in order, whenever the sum of cards flipped is a multiple of 52, the entire deck will be either facing up or down. The deck starts face down, so it will be face down again only when we've flipped a multiple of 104 cards. Ergo it faces up when the number of cards flipped is divisble by 52 but not 104.

I wrote a short, somewhat optimized C++ snippet to determine when the desired states are reached. Here are the highlights of the output:

All cards are facing down after 49 primes! (last prime: 227)
All cards are facing down after 87 primes! (last prime: 449)
All cards are facing up after 117 primes! (last prime: 643)
All cards are facing down after 119 primes! (last prime: 653)
All cards are facing down after 131 primes! (last prime: 739)
All cards are facing down after 179 primes! (last prime: 1063)
All cards are facing down after 203 primes! (last prime: 1237)
All cards are facing up after 319 primes! (last prime: 2113)

And here the code:

#include <iostream>
// Returns whether the given number n > 3 is a prime.
bool isPrime(long n) {
    if(n%2 == 0 || n%3 == 0) return false;
    for(int i = 6; (i-2)*i + 1 <= n; i += 6) {
        if(n % (i-1) == 0) return false;
        if(n % (i+1) == 0) return false;
    }
    return true;
}
// Returns the closest prime larger than the given number.
int nextPrime(int n) {
    while(!isPrime(++n)) { continue; }
    return n;
}

int main() {
    const short DECK_SIZE = 52;
    short faceUp = 5;
    unsigned int steps = 2;
    long prime = 3;
    unsigned short timesDeckWasFaceUp = 0;
    while(timesDeckWasFaceUp != 2) {
        do { // Run until all cards are facing up again.
            prime = nextPrime(prime);
            ++steps;
            // Number of cards to flip this turn.
            short flips = prime % DECK_SIZE;
            std::cout << "Face up: " << (faceUp > DECK_SIZE ? (DECK_SIZE << 1) - faceUp : faceUp) << "\nPrime: " << prime << "\nFlipping: " << flips << " cards.\n\n";
            faceUp = (faceUp + flips) % (DECK_SIZE << 1);
            if(faceUp % DECK_SIZE == 0) { // Entire deck faces in one direction
                if(faceUp) {
                    std::cout << "All cards are facing up after " << steps << " primes! (last prime: " << prime << ")\n";
                    ++timesDeckWasFaceUp;
                    break;
                } else {
                    std::cout << "All cards are facing down after " << steps << " primes! (last prime: " << prime << ")\n";
                }
            }
        } while(faceUp % (DECK_SIZE << 1) != 0);
    }
    return 0;
}

EDIT: Here the revised code that accounts for the fact that the order of the flipped cards gets reversed.

#include <iostream>
#include <deque>
// Checks if the given number > 3 is a prime.
bool isPrime(unsigned long long n) {
    if(n%2 == 0 || n%3 == 0) return false;
    for(unsigned long long i = 6; (i-2)*i + 1 <= n; i += 6) {
        if(n % (i-1) == 0) return false;
        if(n % (i+1) == 0) return false;
    }
    return true;
}
// Returns the nearest prime larger than the given number.
unsigned long long nextPrime(unsigned long long n) {
    while(!isPrime(++n)) { continue; }
    return n;
}

void flipCards(int flips, std::deque<bool>& cards, unsigned short& counter) {
    // Flip the order of the top cards
    std::reverse(cards.begin(), cards.begin() + flips);
    // Turn each card around
    std::deque<bool> flipped(cards.begin(), cards.begin() + flips);
    for(bool& card : flipped) {
        counter += (card) ? -1 : 1;
        card = !card;
    }
    // Remove the cards from the top
    std::deque<bool>(cards.begin()+flips, cards.end()).swap(cards);
    // Add them to the bottom
    cards.insert(cards.end(), flipped.begin(), flipped.end());
}

int main() {
    const short DECK_SIZE = 52;
    // Keep track of how many cards are facing down.
    unsigned short faceUp = 0;
    std::deque<bool> cards(52);
    // Flip the first two primes (2 + 3).
    flipCards(5, cards, faceUp);
    // Keep track of the number of primes flipped.
    unsigned int steps = 2;
    unsigned long long prime = 3;
    unsigned short timesFaceUp = 0;
    while(timesFaceUp != 2) {
        // Run until no more cards are facing down.
        while(true) {
            prime = nextPrime(prime);
            ++steps;
            // Number of cards to flip this turn.
            unsigned short flips = prime % 52;
            flipCards(flips, cards, faceUp);
            if(faceUp % 52 == 0) {
                if(faceUp) {
                    std::cout << "All cards are facing up after " << steps << " primes! (last prime: " << prime << ")\n";
                    ++timesFaceUp;
                    break;
                } else {
                    std::cout << "All cards are facing down after " << steps << " primes! (last prime: " << prime << ")\n";
                }
            }
        }
    }
    return 0;
}

I'm afraid Weather Vane's answer may be correct.

$\endgroup$
  • 1
    $\begingroup$ Good spot, I have been working on the same conditions as Part I puzzle. Here it says "ever have all the cards face up again" but they were never all face up... $\endgroup$ – Weather Vane May 30 at 16:17
  • 4
    $\begingroup$ I think this answer has the same problem that @hexomino pointed out with Michael Moschella's. We start with all cards face down. After 2+3+5+7+11+13 flips we have transferred 41 to the bottom, so we have 11 face down and then 41 face up. Now we pick up 17 cards, 11 face down and 6 face up. We flip them, getting 6 face down on top of 11 face up. Then we put them on the bottom ... and now we have 35 face up, then 6 face down, then 11 face up. Now we pick up 19, flip them over, and put them on the bottom: 16U, 6D, 11U, 19D. It isn't just a matter of counting flipped cards: the order matters. $\endgroup$ – Gareth McCaughan May 30 at 16:33
2
$\begingroup$

I'll go with

Yes, because given infinite time, every possible deck state will repeat indefinitely many times.

That's because

1. There are infinitely many primes
2. There are finitely many deck states, and
3. There are no patterns in the primes (mod 52) that would exclude one state or another.

The first two points are pretty easy to prove:

1: If there were finitely many primes, one of them would be the largest prime, and we could call it the Big-P. Now, multiplying all the primes together and adding one, we would get a new number Bigger-X. It is larger than Big-P, and not divisible by any prime smaller than (or equal to) Big-P. That means that either Bigger-X is prime, or Bigger-X is divisible by some prime(s) bigger than Big-P. This is a contradiction, which means that Big-P cannot exist, and therefore "there's always a bigger prime".

2: Since we don't care about the actual order of the cards, only whether they are face-up or not, the deck has $2^{52}$ possible states, which is a big number (abt. 4.5 quadrillion (US reckoning)), and very definitely finite.

The third proposition is a lot harder to prove, but here's my go:

All but the first two primes are of the form $6n\pm1$. Because 52 is not divisible by 6, taking modulo 52 of such numbers makes every odd number between 1 and 51 possible, and equally likely over a long period of time, even if there were a hitherto unknown secret pattern in the huge primes.

Since the number of flipped cards is always odd, the number of face-up cards in the deck switches between odd and even every time, making each kind equally likely.

Therefore no particular deck state is preferred over another, and each state will occur equally likely in a given (even-length) sequence of states.

This is enough to show the result, because

The probability of any given state occurring in some sequence of two consecutive states is non-zero ($2^{-51}$ actually, because of the abovementioned parity issue), so given infinitely many of these sequences, every state will occur infinitely many times.

$\endgroup$
1
$\begingroup$

Yes, though it would probably take a bit.

Once we really start getting into the big primes we know that # mod 52 is going to be effectively random... but always odd. The idea that random card-moves will get you back to all cards face-down isn't a crazy notion... there are some really big numbers under infinity. But the restriction of using only odd-moves presents a potential problem. We did, after all, make an even-card move initially since 2 is prime.

It ends up being not that important. I played around with it and I can show that any state of cards being up/down can become any other state of cards being up/down. It's not even that hard, honestly. Here's an example of 8 cards, where the first move was 2 cards and the remaining moves were odd.

enter image description here

That example is really trivial but with the right goals in mind you can always improve your standing in a move or two. I would therefore say any state of 52 cards could become face-down within 104 moves. Of course, the actual output from our prime sequence isn't going to agree with what we wanted... usually. The idea is that at any given point, you want a particular sequence to get back to all face-down and it will take a while but somewhere down the number-line you will eventually get it. Solvable by computer? I suspect not. 2^52 possible states is a bit much, and I see no reason one would be more likely than another.

$\endgroup$
  • $\begingroup$ I don't get your flip sequence. For an 8-card deck, shouldn't it be 2 (2 % 8), 3 (3 % 8), 5 (5 % 8), 7 (7 % 8), 3 (11 % 8), 5 (13 % 8), 1 (17 % 8), 3 (19 % 8), 7 (23 % 8) ...? The situation isn't improved after a move or two, because the face/back sequence becomes fragmented. $\endgroup$ – Weather Vane May 30 at 18:04
  • $\begingroup$ I wasn't saying I can do it for a particular known prime sequence. I was imagining a prime sequence on the distant number-line. I just need to show that effectively random moves could conceivably solve a given state of cards. $\endgroup$ – Dark Thunder May 30 at 18:09
  • $\begingroup$ Oh I see - effectively random number of cards flipped as the game proceeds. $\endgroup$ – Weather Vane May 30 at 18:10
  • $\begingroup$ @DarkThunder Prime number isn't random. You just heuristically suggest that the answer is probably yes. $\endgroup$ – Akangka yesterday
  • $\begingroup$ @Akangka I don't claim to be a mathematician but my understanding is that "sufficiently large prime numbers mod 52" would be effectively random. If you can prove otherwise I'd very much like to see it. $\endgroup$ – Dark Thunder 19 hours ago
-1
$\begingroup$

I am going to be the first to say that the answer is no, the deck will never again be in order.

I have no real proof other than the following intuition. The frequency of primes is generally known, but only for very large numbers, and it is only a guide, not exact. Thus, the difference modulo 52 will be mostly random. As a result, we are randomly flipping subsets of cards, so unless we manage to be very fortuitous, we will never get back to in-order.

However, I could be dead wrong - we are dealing with an infinite number of flips.

$\endgroup$
  • 4
    $\begingroup$ Your deck has a finite number of states. We want to know when one specific state happens. Unless there's a good reason otherwise, a random walk will eventually find it. $\endgroup$ – Dark Thunder May 30 at 14:24
  • $\begingroup$ @DarkThunder Good point. The in-order configuration is just as likely as any other configuration. $\endgroup$ – Trenin May 30 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.