Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
    
Are a and b distinct from s? Are they distinct from each other? (Otherwise any set that contains 0 satisfies (2).) –  rgrig Aug 14 '10 at 7:03
2  
@rgrig: If S contains 0, you can just take T to be the singleton set. BTW, the problem ought to say "there is a nonempty subset T…". –  ShreevatsaR Aug 14 '10 at 7:34
1  
@SHree: Right. Edited the problem. –  Aryabhata Aug 14 '10 at 14:08
5  
This question was posed in MathOverflow (without the condition that |S| = 15) in March, at mathoverflow.net/questions/16857/existence-of-a-zero-sum-subset . It has still not been answered. –  TonyK Sep 7 '10 at 11:22
8  
I just put a 100 bounty on this question. I have been trying to solve it for 2 days, with minimal progress, and I'm really frustrated! Is this an open problem or is it known that it has a solution? –  Matt Calhoun Sep 8 '10 at 15:34
show 8 more comments

2 Answers

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$.

share|improve this answer
add comment

This is not intended as an answer, but clearly is too long for comments.

Here are some approaches I have been playing around with; I would appreciate any comments, advice, or suggestions.

Clearly the condition si = sj + sk is the key thing about this problem. It seems like in order to state this as a problem (instead of as a conjecture), it must have been solved by someone, otherwise where does |T| $\leq$ 7 come from? Since we don't know for sure if the problem has been solved, I am assuming that |T| $\leq$ 7 is possibly wrong and just trying to work out the consequences of the condition.

This condition is very constrictive, and it's consequences are not at all readily apparent. One question I have is, how many independent elements can a set which satisfies the condition have? The idea of an independent element is not rigorous for a set like this, but the idea is to figure out how to formulate the idea of independent element so it is rigorous. Given a set of integers H, with |H| less than 15, is it possible to add numbers (by combining elements of H) so that H has 15 elements and satisfies the condition; if so, can we say something about the original size of H?

In this direction I have made the following (slightly trivial) observations:

A set which satisfies the condition contains:

  • at least two (distinct) positive numbers
  • at least two (distinct) negative numbers
  • at least two (distinct) numbers which are the sum of a positive and a negative number

This follows from the fact that each such set will contain a largest positive number which must be the sum of only positive numbers (similarly for negative); and the smallest positive number must be the sum of a positive and negative (similar for smallest negative number). I'm not sure how this relates to the (poorly defined) notion of "independent element", but it feels like a start in that direction.

Another idea is that the condition si = sj + sk can be "unpacked" by applying it recursively to sj and sk. My hope is that I can show that there will always be one element which can be "unpacked" so that it is equal to 8 elements in S, one of which is itself. This would of course show that the sum of the other 7 is zero.

si = sj + sk

= sl + sm + sn + sp

= sq + sr + ss + st + su + sv + sw + si

The next idea is to show that any set satisfying the condition will contain what I call a "7 cycle", which is inspired from the totally anti-symmetric unit tensor. A "7 cycle" is a kind of symmetry for the index's of si = sj + sk, I will just write down what a 7 cycle looks like, because that is more clear than explaining it.

s1 = s2 + s3

s2 = s3 + s4

s3 = s4 + s5

s4 = s5 + s6

s5 = s6 + s7

s6 = s7 + s1

s7 = s1 + s2

If it's possible to show that any set satisfying the condition contains a 7 cycle, then it's clear that the sum of s1...s7 will be zero (since it is equal to twice itself).

Another idea is a combinatorial graph theory approach. Clearly, a set satisfying the condition generates a directed graph (as pointed out in the MO link). For clarity, each number in S corresponds to a vertex, and if for example, s1 = s2 + s3, then there will be edges directed from s2 to s1 and from s3 to s1.

A question I have which I can't seem to make progress on, is: what is the minimum possible number of vertex's which have outgoing edges? (a vertex has an outgoing edge if it can be added to an element of S to obtain another element of S, also the assumptions used in the previously given "weaker statement" led to the conclusion that each vertex has an outgoing edge, and this was used to show |T| $\leq$ 7). My hope is that once I know the minimum number of vertex's with outgoing edges, I can use some sort of combinatorial reasoning to show that there will be a closed cycle with a maximum length.

Googling "zero sum subset" quickly leads to references for the EGZ theorem, and by thinking about the problem backwards, it makes sense that since this is one of the best known results for zero sum problems; that if this problem has already been solved this result might be involved in the solution somehow. I can't quite wrap my head around exactly how it will be involved, but since it is a result dealing with the integers mod N, the idea would be to somehow show that the condition forces some (possibly elaborate) modular arithmetic structure on the set S which satisfies it. (my understanding is that EGZ says that given an arbitrary set of 2n - 1 integers in $\mathbb{Z}$ mod n, there will be a subset of n elements whose sum is congruent to 0 mod n)

Yet another idea is to reformulate the problem in terms of polynomials. Given a set S which satisfies the condition, consider the 15th degree polynomial whose roots are the elements of S. Then these roots possess the symmetry that every root is the sum of two other roots; these types of polynomials might have some property which forces the sum of at most 7 elements to be zero.

I don't feel strongly that any of these approaches will ultimately prove successful, but hopefully by making this post I can help keep this question alive and inspire others to work on it.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.