A set of cards from which I can identify and number $n$ with $1\le n\le N$

Question

I am working with a collection of cards. On each card is written a set of numbers $1\le n\le N$ in ascending order.

When I arrange the cards in lexicographic order on the table, no two adjacent cards share a number.

The cards are designed so that when I pick a number $r$, select all the cards containing $r$, and sum the smallest numbers on each of those cards, I get the total $r$.

The idea is that I can ask a friend to choose a number $1\le n\le N$, and ask them to identify the cards containing that number. From that information I can identify the number by doing a simple sum.

For example if $N=4$ the three sets $\{1,4\}, \{2\}$ and $\{3,4\}$ could be written on the cards. They are in lexicographic order, no adjacent cards share a number, and any number $1\le n\le 4$ can be identified.

If you choose $1$ for example, there is a single card lowest value $1$. With $4$ you pick up two cards values $1+3=4$

Given $N$ what is the smallest number of cards I need? Given the number of cards, what is the largest $N$ possible?

In fact any of the five numbers $0\le n\le 4$ can be identified from this set.

---

Solution: [to unedited question] If n is odd then solution is (n+1)/2.
if n is even then solution is n/2+1.

But i am getting this is a wrong answer.Where i have made a mistake?

---

Note the problem appears here and seems to be popular mid August 2015

Answer 1

Do you mean like this:

With four cards the sets $\{1,4,6\}; \{2,7\}; \{3,4\}; \{5,6,7\}$ allow you to distinguish between the integers $1\le n \le 7$ (and you get zero as a bonus).

With five cards I get $\{1,4,6,9,12\}; \{2,7,10\}; \{3,4,11,12\}; \{5,6,7\};\{8,9,10,11,12\}$ which get me to $12$ - that seems better than you have done.

I think the pattern I can see in the lowest elements of these sets will continue - but I'll leave that for you to explore - that would give a different answer from the one you have.

---

To expand a bit. The lowest number on each card is a Fibonacci Number. Every positive integer can be written as the sum of non-consecutive Fibonacci numbers - so we can place every integer on such a card.

Answer 2

I think the answer is

For 13 to 20 The answer is 6
     10 11 and 12  (1,4,6,9,12) (2,7,2) (3,4,11,12) (5,6,7) (8,9,2,11,12)   5
        9    (1,4,6,9) (2,7) (3,4) (5,6,7) (8,9)      5
        8   (1,4,6) (2,7) (3,4) (5,6,7) (8)           5
        7    (1,4,6) (2,7) (3,4) (5,6,7)              4
        6    (1,4,6) (2) (3,4) (5,6)                  4
        5     (1,4) (2) (3,4) (5)                     4
        4     (1,4) (2) (3,4)                         3
        3    (1) (2) (3)                              3
        2   (1) (2)                                   2
        1   (1)                                       1

How to find for n term is still confusing

Answer 3

Suppose with $r$ cards I can reach a total $N_r$. With $1$ card I can reach $1$ and with no cards I can reach $0$.

I add another card. If I want the total $N_r+1$, I have to include it on card $r+1$.

I can get $N_r+2$ by writing it on card $r+1$ and on the cards containing $1$.

I can get $N_r+k$ on card $r+1$ (the lowest value on this card is $N_r+1$) by writing it on all the cards containing $k-1$ and on card $r+1$ to get the total $k-1+N_r+1=N_r+k$

This goes wrong for the for the first value of $k-1$ written on card $r$, and this value is $N_{r-1}+1$ so we are fine up to $k=N_{r-1}+1$

Putting this together we find we can reach $N_{r+1}=N_r+N_{r-1}+1$

---

The lowest number on the next card is the least number which cannot be constructed from the previous cards. It is easy to see that if the sequence falls behind because the early cards are inefficient, it can never catch up.