Thread: zero-sum subset problem

Hello everyone.

I have been working on a math problem for some time now, but I can not finish the proof. In other words, I'm stuck. I hope someone here can solve it for me or perhaps we could make it into a joint effort. The problem is taken from a monthly math magazine, which features 3 math problems each month.

I am not sure whether this goes under number theory or set theory. Admins, feel free to move it around if you think it's necessary.

Here's the problem:

--------------------------------------------------------------------------------
Consider a set with and the following property:

, such that .

Proof that for every such , there exists a non-empty subset with of which the elements sum up to zero.
--------------------------------------------------------------------------------


I have come up with a few observations that might be useful, but I think it's best to wait and see how things go. If noone has an idea how to approach the problem or if someone asks me for the info, then I will give it.

Until then, good luck!

I don't know if this leads anywhere, but here are a few thoughts on the problem.

It seems helpful to try to get away from the numbers 15 and 7, and to see the problem in a more general setting.

Conjecture. Let S be a set of integers, containing at least two elements, satisfying the following properties:

(1) S ⊆ S + S, (2) if and then |T| ≥ n.

Then .

Remarks: (a) Condition (1) just says that every element of S is the sum of two elements of S. (b) The case n=8 is equivalent to the given problem about 15 and 7.

To get a feel for the problem, I looked at the cases n=2 and n=3.

For n=2, condition (2) just says that 0∉S. In that case, it's easy to convince yourself that |S| has to be greater than 3, and that in fact |S|=4 is possible, for example if S={±1,±2}.

For n=3, condition (2) says that if x∈S then –x∉S. In this case, it takes a bit more effort to convince yourself that |S|=5 is not possible, but that |S|=6 is possible, for example if S={–6,–5,–3,1,2,4}.

That's as far as I got. When n≥4 things start to get complicated. As I said, I don't know if this gets you anywhere. But at least it gives you a framework in which to experiment, and maybe get some ideas for a more general argument.

Thank you for your reply!

I have done a fair bit of research myself as well , maybe it's wise to post it here to help people along.

First of all, if or if any s has an inverse in S, then the required subset is rather trivial, don't you agree? We can either take or . So we may rightly assume that s does not contain zero and has no inverses.

With that being said, the smallest possible set S of integers that still satisfies the second property has size 6. You already found that result. This is because S necessarily includes 3 positive and 3 negative numbers.

I suspect that the best approach to proof this is to start with a well-chosen member s and 'expand' it, if you will, as the sum of other members of s. If, at some point, you come across s again, you will know that the sum of the remaining terms will add up to zero. However, there are some issues with this approach.
- Some numbers can be written as the sum of two members of S in more than 1 way.
- There can not be doubles in the 'expansion' of s.
- Some numbers will never reoccur in an expansion.

We will have to investigate the internal structure of such an S and come up with properties to show that this is indeed possible.

For instance, it's easy to show that if you keep on expanding, you will enter a loop at some point. This is simply because the number of elements in S is finite.

Hope this helps. I have some more results.. but let's just see if this is useful.

One further thought. Here is a set S of 16 integers for which S⊆S+S but no subset of 7 or fewer elements can sum to 0:

S = {–254, –253, –251, –247, –239, –223, –191, –127, 1, 2, 4, 8, 16, 32, 64, 128}.

It's clear from that pattern that you can always find a set S of 2n integers for which S⊆S+S but no subset of fewer than n elements can sum to 0.

Very true. That was actually the b-part to that question. I used successive powers of two as well !

Keep in mind that |S| can be of the form 2n + 1 as well. I suppose in that case, the upper limit of cardinality of |T| will be Floor(|S|/2), but I haven't been able to show that. The powers of two don't work in that situation.


Now to find one more thought that can help us along. I haven't found it yet.

It seems there's not a lot of interest into the problem here.. so I figure I'll just spout some of my thoughts.

--------------

Let S be a set of integers with |S| = 15. We may assume that S contains neither zero nor an inverse of another member of s, for it would make the choice for our subset T rather trivial. Furthermore, if S contains neither, it can be shown that it must contain at least three positive and three negative numbers. The proof is rather simple, just some logic steps. So take my word for it for now.
Consider now A to be the positive members of S and B to be the negative members of S. Without loss of generality, we may assume that |A| < |B|. So 3 <= |A| <= 7. Now define a graph G on A as follows: Let x, y be members of A. There exists an edge x -> y if there exists a z in S such that x = y + z. By this definition, every member of A is adjacent to at least one other member of A, because every positive number can not be written as the sum of two negative numbers. Because A is finite, there must exist a cycle X = x1, ... xk. Let k be the smallest k with this property. Then there exist Z = z1, ... zk such that

x1 = x2 + z1 = x3 + z2 + z1 = ... = x1 + zk + ... + z1.

The the sequence z1, ..., zk will sum to zero.

The way I see it, the main problem in this proof has to do with the doubles that occur in such a sequence Z. If there are no doubles in the sequence, then we have found our T. So let's assume that there are x_i and xj with i =/= j such that xi = xi+1 + z and xj = xj+1 + z. It is easy to show that z can not be a member of X. If it were, then there would exist a smaller cycle through xi, xj and z. That is not allowed since we chose X to be the smallest cycle in A. So we are left with the case that z is not a member of X. We need to proof that either we can replace z and still get a T with |T| <= 7 or that there must exist a different cycle (possibly in B) with the required properties.

I experimented some with assuming that |X| < 7. Then it's possible for z to be positive. There are some implications there, but nothing useful. We can 'expand' z a number of times till we reach a member of X. A new cycle might be possible in that way. Remember that our upper limit on the cycle size is equal to the upper limit on the amount of positive numbers in S. The other possibility is that z is in B. Maybe it's worth looking into the smallest cycle in B then? We have no guarantee that its length will be smaller than 7, but maybe we can proof that the biggest cycle in B can be no larger than the size of A. This certainly sounds plausible.. since negative numbers are absolutely required to make a cycle in the positive part of S.

--------------

The set I've been looking into most recently is S = {-8, -4, -3, -1, 2, 5, 7, 9}. It's of size 8, naturally, but the cycle 9 -> 7 -> 5 -> 9 has a complement Z which features the number 2 twice. I'm trying to find a structural way to avoid this. My work so far:

-------------
Let X be the smallest cycle x1 -> ... -> x1 in A (the positive members of S). Then 3 <= |X| <= 7, because 3 <= |A| <= 7 and |X| = 1 -> 0 in S, |X| = 2 -> S has an inverse.

Now let xi and xj be such that xi = xi+1 + z and xj = xj+1 + z and suppose that i < j. Now there are a few cases I was thinking of addressing.

- Suppose z = xk in X. Then there exists a cycle inside of X which is smaller than X itself. This is not possible since I chose X to be the smallest cycle in A.
- Suppose |X| < 7. Then there can possibly be m = |A| - |X| members of A which are not in X. So suppose that z in A \ X. If we expand z m times, we must arrive at a member of X (since there are only m members of A left which are not in X). Then we can construct a new cycle which includes z and might possibly be larger than X but must be smaller or equal than 7.

The final case is when z is in B. I don't know how to approach that one.

Does this make sense?


Edit: I reread it and concluded, once again, that graph theory proof are totally unreadable without some drawing or example. So I'll just give you one.

Consider S = {-8, -4, -3, -1, 2, 5, 7, 9}. Then |S| = 8 and believe me that it satisfies the important property. Then A = {2, 5, 7, 9} and we found the cycle 9 -> 7 -> 5 -> 9 with complement {2, 2, -4}. In this case, xi = 9, xj = 7 and z = 2. Note that |X| = 3 < 4 = |A|, so m = 1. Here, z is in amongst the remaining members of A which are not in X, so z in X \ A. Note that if we expand z, we get z = 5 + -3. 5 is a member of X, which is to be expected after m expansions. Now we can construct the cycle z -> 5 -> 9 -> z (because 9 = xi) which satisfies our criterium.

The trick here is that the length of such a newly found cycle can not exceed |A|, which is what we wanted.

-------

There is no guarantee that this new cycle will not conflict, but I'm fairly confident we can repeat this process till we find a cycle in A which either doesn't have a conflict, or the conflicting z is not a member of A.