TransWikia.com

20 cards facing down

Puzzling Asked by prog_SAHIL on September 1, 2020

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.

6 Answers

Correct answer by Deusovi on September 1, 2020

I'm not sure this is a puzzle.

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.

Answered by Matt Stevens on September 1, 2020

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.

Answered by Bass on September 1, 2020

Answered by Acccumulation on September 1, 2020

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.

Answered by Drooga on September 1, 2020

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.

Answered by phlexicon on September 1, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP