12
$\begingroup$

You have a row of $20$ cards facing down.

A 'move' consists of the following actions performed in sequence:

  1. Pick a face-down card and flip it face-up
  2. If there is one, also flip the next card on the right, no matter its initial state

Prove that no matter how you play, you will always reach a stage with no more valid moves i.e. this sequence must terminate.

Improve this question
$\endgroup$

6 Answers 6

Reset to default
12
$\begingroup$

Treat the cards as binary, with 1 being face-down and 0 being face-up. The binary number given by these cards never increases, and each move decreases it by at least 1. The number also cannot be negative, so there must be finitely many moves.

Improve this answer
$\endgroup$
3
$\begingroup$

Here’s another proof, this time by induction:

Induction Hypothesis: (Not necessarily true yet) Among any card set of N cards, every move sequence terminates after a finite number of moves.

Using the Induction Hypothesis, prove the Induction Hypothesis for N+1:

Induction Step: The leftmost card of any set cannot be flipped back, once it has been flipped face-up, so it can be flipped at most once. Therefore, the maximal sequence in a set of N+1 cards cannot be longer than "maximal sequence among the N rightmost cards + flip the leftmost card + another maximal sequence among the N rightmost cards". Particularly, using the Induction Hypothesis, every move sequence among a set of N cards terminates, and therefore every move sequence among a set of N+1 cards also terminates.

Base case: Any set consisting of only 1 card allows for only terminating sequences. Proof: the possible sets are "face up" and "face down", which terminate after 0 and 1 moves, respectively.

Now, the Base Case proves that the Induction Hypothesis is true for N=1, and the Induction Step proves that if the Induction Hypothesis is true for some N, it is also true for N+1.

Conclusion: Therefore, by induction, for all integers N >= 1, the Induction Hypothesis is true.

Improve this answer
$\endgroup$
3
$\begingroup$

Let X be the leftmost card that you can flip an infinite number of times. Each time you flip it, you can't flip it again until you flip the card to the left. Since you can flip X an infinite number of times, you must be able to flip the card to its left an infinite number of times. But that contradicts the definition of X, so X does not exist. So assuming the cards are well-ordered (not, e.g., in a circle), there are no cards that you can flip an infinite number of times. Since there are a finite number of cards, and each one can be flipped a finite number of times, the total number of flips is finite.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "But that contradicts the definition of X, so X does not exist." What definition of X are you talking about ? $\endgroup$
    – Hemant Agarwal
    Aug 31, 2022 at 19:13
  • $\begingroup$ @HemantAgarwal I define X as the leftmost card that you can flip an infinite number of times. Then I prove that the card to its left can be flipped an infinite number of times. But if the card to X's left can be flipped an infinite number of times, then X is not the leftmost card that you can flip an infinite number of times. $\endgroup$
    – Acccumulation
    Sep 17, 2022 at 19:40
2
$\begingroup$

Every move does 1 of 2 things:

  1. decreases the number of face-down cards, or
  2. moves a face-down card to the right.

Since there is a boundary on the right and a minimum number of face-down cards [0], the process must terminate for any finite number of cards ordered left to right.

Improve this answer
$\endgroup$
0
$\begingroup$

Starting with the leftmost card, number them consecutively from 1 to 20. If the sequence fails to terminate then there is at least one card with number m say which changes its state infinitely many times. But then there must a card with number n< m which also changes its state infinitely many times. But as card 1 only changes its state once, this process cannot continue.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The problem statement says nothing about cards changing their state. It only says that the player will begin with 20 cards all facing down. If the left most card is flipped (step 1) then the next step is to flip the card to it's right (step 2) and so on and so forth until all the cards have been flipped. I'm not sure how this post got 6 up votes. $\endgroup$
    – Dr t
    Apr 9, 2019 at 23:02
  • $\begingroup$ @Drt I think you've mischaracterized the problem. (As an aside, you also mentioned this answer having 6 upvotes when in fact it has never been upvoted.) The card to the right of the card chosen for a move will change its state by being flipped, whether it was face up or down; that could, in theory, lead to a specific card being flipped repeatedly as play goes on, which Drooga here alludes to. Note that these flips would be infinite if play never terminated. Having said all this, Drooga's answer is generally equivalent to Bass's with n,m being different levels of induction. $\endgroup$
    – Rubio ♦
    Apr 9, 2019 at 23:56
-1
$\begingroup$

I'm not sure this is a puzzle.

There are a finite number of cards and can only "call a move" on each card once. Therefore there is a finite number of moves.

There is an assumption being made, not provided by the OP, that the cards are ordered, for example, in a line as opposed to a circle. A circle is an example where the favored answer would be incorrect.

The definition of a move is stated by the OP as;

I call a 'move' turning a face down card up and turning the card to its immediate right.

Improve this answer
$\endgroup$
4
  • $\begingroup$ That’s not right. Let’s say “D” stands for face down and “U” for face up, then you can go DDDD → DUUD → UDUD, at which point you can flip the second card again. $\endgroup$
    – Sascha Baer
    Feb 10, 2018 at 11:15
  • $\begingroup$ There is no option for turning 'U' cards to 'D'. $\endgroup$
    – Matt Stevens
    Feb 10, 2018 at 11:29
  • $\begingroup$ lol, you are interpreting 'turn the card to its right' as 'flip the card on the right' as opposed to turn the card you just flipped, to the right. $\endgroup$
    – Matt Stevens
    Feb 10, 2018 at 11:33
  • 2
    $\begingroup$ wait, how are you interpreting it? Like, physically rotating the card by 90 degrees for no reason whatsoever? I’m gonna stick with my interpretation of a move being to flip card n as well as card n+1, but only if n is turned down. $\endgroup$
    – Sascha Baer
    Feb 10, 2018 at 11:49

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.