# A zero sum subset of a sum-full set

I had seen this problem a long time back and wasn’t able to solve it. For some reason I was reminded of it and thought it might be interesting to the visitors here.

Apparently, this problem is from a mathematics magazine of some university in the United States (sorry, no idea about either).

So the problem is:

Suppose $S \subset \mathbb{Z}$ (set of integers) such that

1) $|S| = 15$

2) $\forall ~s \in S, \exists ~a,b \in S$ such that $s = a+b$

Show that for every such $S$, there is a non-empty subset $T$ of $S$ such that the sum of elements of $T$ is zero and $|T| \leq 7$.

Update (Sep 13)

Here is an approach which seems promising and others might be able to take it ahead perhaps.

If you look at the set as a vector $s$, then there is a matrix $A$ with the main diagonal being all $1$, each row containing exactly one $1$ and one $-1$ (or a single $2$) in the non-diagonal position such that $As = 0$.

The problem becomes equivalent to proving that for any such matrix $A$ the row space of $A$ contains a vector with all zeroes except for a $1$ and $-1$ or a vector with all zeroes except $\leq 7$ ones.

This implies that the numbers in the set $S$ themselves don’t matter and we can perhaps replace them with elements from a different field (like say reals, or complex numbers).

A weaker statement, where we allow elements in $T$ to be repeated, can be proved as below:
Since we can look at the set $\{-s | s\in S \}$ we may assume there are at most $7$ positive numbers in $S$. Let each positive number be a vertex, from each vertex $s$ we draw an arrow to any vertex $a$ such that $s=a+b$. Since if $s>0$, one of $a,b$ must be positive, there is at least one arrow from any vertex. So there must be a cycle $s_1,\cdots,s_n=s_1$ with $n\leq 8$. We can let $T$ consists of $s_i-s_{i+1}$, $1\leq i\leq n-1$.