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][1]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. [1]: https://math.stackexchange.com/questions/667257/number-of-vectors-so-that-no-two-subset-sums-are-equal
