Consider all $10$-tuple vectors each element of which is either $1$ or $0$. It is very easy to select a set $v_1,\dots,v_{10}= S$ of $10$ such vectors so that no two distinct subsets of vectors $S_1 \subset S$ and $S_2 \subset S$ have the same sum. Here $\sum_{v \in S_i} v$ assumes simple element-wise vector addition where element addition takes place over $\mathbb{R}$. For example, if we take the vectors that are the columns of the identity matrix as $S$ this will do.

What is the maximum number of vectors one can choose that has this property?

I previously asked this question on MSE . An explicit construction of $17$ vectors was given by Oleg567 using computer search and an upper bound of $45$ was given by jpvee simply using the observation that $\sum_{k=1}^{17} {46 \choose k} > (17+1)^{10}$ implies that $46$ vectors is impossible.

Lower bound improved to $18$ by Oleg567. Upper bound still stuck at $45$ although it seems implausible the true value is far from the current lower bound.

Upper bound of $36$ given by Seva.

**Conjecture Feb 24, 2014**. I conjecture the optimal solution size is $\lfloor \frac{1}{2} (n+1) \log_2(n+1) \rfloor$. For $n=2\dots 15$ this is $2, 4, 5, 7, 9, 12, 14, 16, 19, 21, 24, 26, 29, 32$.

New lower bound of $19$ by Brendan McKay.

New upper bound of $30$ by Brendan McKay.

notmodulo 2. $\endgroup$5more comments