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⊂Z (set of integers) such that
1) |S|=15
2) ∀ s∈S,∃ a,b∈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|≤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 ≤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).
Answer
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∈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 s1,⋯,sn=s1 with n≤8. We can let T consists of si−si+1, 1≤i≤n−1.
Attribution
Source : Link , Question Author : Aryabhata , Answer Author : Mariano Suárez-Álvarez
