10
$\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?

Improve this question
$\endgroup$
4
  • $\begingroup$ I feel like something's missing. What happens to the cards after they are flipped over? $\endgroup$
    – dennisdeems
    Jul 16, 2015 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, 2015 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, 2015 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, 2015 at 16:38

3 Answers 3

Reset to default
21
$\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.

Improve this answer
$\endgroup$
6
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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.

Improve this answer
$\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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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