-1
$\begingroup$

some one ask you to choose number between $1$ and $n$ both inclusively then he shows you some card having one of more element and asks whether the card contains your chosen number or not after showing number of cards he immediately tells the number which you have chosen trick is simple because he just adding the first integer written on the cards that contain the integer you had thought of, and then gives the sum as the answer.

The integers in all the lists are between 1 and N. Note that the same integer may appear in more than one card

Thus his trick will work well in every case. And we can check it easily that the cards are sorted in lexicographical order and two consecutive cards have no common integers.

Required question is find minimum number of cards such that the tricks work in every case??

for example

$n=1$ example 1, only 1 card containing {1} will work.

$n=4$ In example 2, make 3 cards containing {1,4}, {2} and {3,4}.

Assume you thought of 1, then you will select the 1st card {1,4}, then she will correctly figure out the integer you thought being 1.

Assume you thought of 2, then you will select the 2nd card {2}, then she will correctly figure out the integer you thought being 2.

Assume you thought of 3, then you will select the 3rd card {3,4}, then she will correctly figure out the integer you thought being 3.

Assume you thought of 4, then you will select 1st card {1,4} and 3rd card {3,4}, then she will calculate the sum of the first integers of the two card $1 + 3 = 4$, and she will answer it.

some more examples are

$n=1$ ans $= 1$

$n=2$ ans $=2$

$n=3$ ans $=3$

$n=4$ ans $=3$

$n=5$ ans $=4$

$n=6$ ans $=4$

$n=7$ ans $=4$

$n=8$ ans $=5$

$n=9$ ans $=5$

$n=10$ ans $=5$

$\endgroup$
  • 2
    $\begingroup$ For n=4, can't you use the following 2 cards: {2, 4} and {3, 4}? Then if your number is on no card, it's 1, if it's on only the first it is 2, if it's on only the second it is 3, if it is on both it is 4. $\endgroup$ – jschnei Aug 10 '15 at 18:50
  • $\begingroup$ no two consecutive card has any element in common $\endgroup$ – Syed Shibli Aug 10 '15 at 18:53
  • $\begingroup$ Okay, but you can still do 5 with only 3 cards: {2, 5}, {3}, {4, 5} $\endgroup$ – jschnei Aug 10 '15 at 19:03
  • $\begingroup$ It looks like the question was edited again: is there still the restriction that no two consecutive cards have any element in common? $\endgroup$ – jschnei Aug 10 '15 at 19:06
  • $\begingroup$ yes...each and every integer from 1 to n must be in cards but no two number should be same in one card and no two consecutive card has any element in common $\endgroup$ – Syed Shibli Aug 10 '15 at 19:08
1
$\begingroup$

Assuming I'm understanding the question correctly, which is that the cards must be presented

  1. In lexicographic order
  2. Such that no two consecutive cards share any numbers
  3. Such that each number from 1 to $n$ belongs to some card

then the answer is given by $f(n) = \max \{ m \mid F_{m} \leq n\}$ where $F_{m}$ is the $m$th Fibonacci number (with $F_{1}=1$, $F_{2}=2$, $F_{n} = F_{n-1} + F_{n-2}$ for $n \geq 3$).

We can prove this as follows. We'll first show you need at least $f(n)$ cards. Let's assume your trick only needs $c$ cards. Then every set of responses by the person with the number can be represented as a binary string of length $c$ (where the $i$th bit is $1$ if his number is on the $i$th card). Note also that there can be no two consecutive $1$s in this string, since no two consecutive cards are allowed to share any numbers in common. Therefore the number of distinct responses by the person is at most the number of binary strings of length $c$ with no two consecutive $1$s.

Now, the number of binary strings of length $c$ with no two consecutive $1$s is just $F_{c+1}$. To see this, note that if $S_c$ is the set of binary strings of length $c$ with no two consecutive $1$s, then each string in $S_c$ either is a string in $S_{c-2}$ followed by $01$ or a string in $S_{c-1}$ followed by $0$. Therefore $|S_{c}| = |S_{c-1}| + |S_{c-2}|$; since $S_{1} = 2 = F_2$ and $S_{2} = 3 = F_3$, it follows that $|S_c| = F_{c+1}$.

Therefore there are at most $F_{c+1}$ different responses to $c$ cards. In fact, since each number must belong to some card, the all $0$ response is not allowed, so there are at most $F_{c+1} - 1$ different responses to the $c$ cards. It therefore follows that with $c$ cards you can distinguish at most up to $F_{c+1} - 1$ different numbers and therefore that to distinguish the $F_{c+1}$ numbers from $1$ to $F_{c+1}$ you need at least $c+1 = f(F_{c+1})$ cards.

We'll now show that it is possible to distinguish all the numbers up to $F_{c+1} - 1$ with at most $c$ cards. To do this, note that by Zeckendorf's theorem we can write any number $x$ uniquely as a sum $x = \sum_{i\in S} F_{i}$ of Fibonacci numbers such that if $i \in S$ then $i+1 \not \in S$ (i.e. no two consecutive Fibonacci numbers are used). For $x \leq F_{c+1} - 1$, only the first $c$ Fibonacci numbers are used. Therefore, for each $1 \leq x \leq F_{c+1} - 1$, put $x$ on the $i$th card if $F_{i}$ appears in its Zeckendorf representation.

Then given the set $S$ of cards $x$ belongs to, we can recover $x$ simply via $x = \sum_{i\in S} F_{i}$. Moreover, by the property of the Zeckendorf representation $x$ cannot belong to two consecutive cards. Since the smallest number on card $i$ is $F_{i}$, the cards are furthermore in lexicographic order, and additionally one can reconstruct $x$ by summing the smallest number on each of the cards $x$ belongs to. This completes the proof.

$\endgroup$

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.