9
$\begingroup$

I have a deck of 52 cards on the table in front of me, in random order, each one randomly facing either up or down. I place one joker at each end, each of these again randomly facing either up or down, to get a deck of 54 cards.

I then perform a sequence of moves each of the following form.

Choose a random contiguous block of cards (a certain number $\geq1$ of cards, all together in the deck) such that both the top and bottom card are facing up, and flip it over as a single unit.

What is the probability that eventually I can no longer perform such a move, i.e. all the cards are facing down?

$\endgroup$
  • $\begingroup$ I feel like something's missing. What happens to the cards after they are flipped over? $\endgroup$ – dennisdeems Jul 16 '15 at 2:10
  • $\begingroup$ And: is the goal to get all cards facing down or to prove that eventually no move exists? $\endgroup$ – Pieter Geerkens Jul 16 '15 at 6:01
  • $\begingroup$ The statement, "What is the probability that eventually I can no longer perform such a move, i.e. all the cards are facing down?" doesn't appear self-consistent. It is possible to have one, and only one, card facing up, which would make it impossible to perform such a move, but wouldn't fulfill the "...all cards are facing down," statement. Please clarify which is correct, given that the answer you've accepted does not discuss this case. $\endgroup$ – Adam Davis Jul 16 '15 at 13:07
  • $\begingroup$ @AdamDavis A single face-up card constitutes a "contiguous block of cards (a certain number ≥1 of cards, all together in the deck) such that both the top and bottom card are facing up", so a move would be possible. $\endgroup$ – singletee Jul 16 '15 at 16:38
20
$\begingroup$

The probability is

1.

If you

represent all face-up cards as 1 and face-down cards as 0, the binary number representing the deck (concatenating the states from top to bottom) decreases every time. It can never drop below 0, of course, so you have to eventually stop flipping cards.

$\endgroup$
  • $\begingroup$ Exception: The number 1 cannot be reduced, because there is no second card facing up with which to define a flppable block. Likewise for any other pattern that represents a power of two. $\endgroup$ – Pieter Geerkens Jul 16 '15 at 3:55
  • $\begingroup$ Likewise for the pattern 5, or any pattern such as 10, 20, 40, etc., representing a left-shift of 5. $\endgroup$ – Pieter Geerkens Jul 16 '15 at 3:58
  • 1
    $\begingroup$ @PieterGeerkens 5 would work - flip 101 to get 010. And I never said you had to be able to keep flipping until you got to 0 - I just proved that it was impossible to flip infinitely. $\endgroup$ – Deusovi Jul 16 '15 at 4:59
  • $\begingroup$ @PieterGeerkens If you check the OP, I said the block of cards you choose to flip can be only 1 card thick. So when the process stops, all the cards must be face-down. Also, good job Deusovi! $\endgroup$ – Rand al'Thor Jul 16 '15 at 9:39
  • 1
    $\begingroup$ @apm: of course there are plenty of possibilities. You can turn any set of cards you want in that situation. $\endgroup$ – oerkelens Jul 16 '15 at 14:20
0
$\begingroup$

The gap between the first and the last card facing up always narrows or stays the same, without ever going beyond the old gap. Eventually there'll be no usable cards inside a gap between facing-up cards even if we try to avoid moves narrowing it (the time for the widest gap will come), so there will be no cards left. In other words, the answer is 1.

$\endgroup$
0
$\begingroup$

Let's prove the number of move is limited recursively on a group of n cards: n = 1 means you have one move possible, afterward, you are stuck.

Let's suppose the hypothesis true for n >= 1 and let's take n + 1 cards.

There is a limited number of move involving only the n first cards. after a moment, you would either be stuck or would turn the last card. After that, this card would be face down, no moves will be able to involve this last card and you are then limited to the n first cards.

There is therefore, only a finite number of moves possible.

The solution is 1

$\endgroup$

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.