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 SZ (set of integers) such that

1) |S|=15

2)  sS, a,bS 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|sS} 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 n8. We can let T consists of sisi+1, 1in1.

Attribution
Source : Link , Question Author : Aryabhata , Answer Author : Mariano Suárez-Álvarez

Leave a Comment