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:
Prove that no matter how you play, you will always reach a stage with
no more valid moves i.e. this sequence must terminate.
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:
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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP