# 20 cards facing down

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.

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.

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.

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.

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.

• 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. – Dr t Apr 9 '19 at 23:02
• @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. – Rubio Apr 9 '19 at 23:56

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.

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.

• 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. – Adarain Feb 10 '18 at 11:15
• There is no option for turning 'U' cards to 'D'. – Matt Stevens Feb 10 '18 at 11:29
• 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. – Matt Stevens Feb 10 '18 at 11:33
• 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. – Adarain Feb 10 '18 at 11:49