2
$\begingroup$

There are $N$ cards, numbered from $1$ to $N$. Every card has each number from $1$ to $M$ written on it.

Some numbers exist on the front side of the card and some on the back side. No number exists on both the sides of a card at the same time. These cards are placed on the table in a row such that only one side is visible. We are allowed to flip them any number of times.

We want to flip the some sets of cards such that all numbers from $1$ to $M$ should be visible at least once.

Total Number of Arrangments = $ 2^{N}$

if $ 2^{N} > M$ , then it always possible to do this. Can someone please prove this , I can't figure out why it's always possible.

$\endgroup$
  • $\begingroup$ @5xum : everycard has every number (including 2) written on one of its sides. $\endgroup$ – Evargalo Jul 25 '17 at 13:36
  • $\begingroup$ We assume $n=N$ ? It is a strong result, with only ten cards it is possible to show all the numbers from 1 to 1000, which might not be intuitive ! $\endgroup$ – Evargalo Jul 25 '17 at 13:37
2
$\begingroup$

We can prove it by induction on $N$. Take the first card. All $M$ numbers are on it either on the front or on the back, so one of the two sides has at least half the $M$ numbers. Put that side up. Now we have $N-1$ cards left, and we have at most $M/2$ numbers left to get (whichever ones aren't showing on the first card). $2^{N-1}>M/2$, so we can do this.

The base case is $N=1$, i.e if $M<2$ we can do it with one card. This is trivial.

$\endgroup$
  • $\begingroup$ $2^{N-1}>M/2$, so we can do this ? Explain this why it's possible ? you have just stated my problem in your answer $\endgroup$ – Marvel Jul 25 '17 at 13:47
  • $\begingroup$ That's the induction hypothesis. We assume the result is true for $N-1$, and prove that it must be true for $N$ too. Then, since it's true for $N=1$, it's true for any $N$. $\endgroup$ – Especially Lime Jul 25 '17 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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