52
$\begingroup$

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

  • 0
    Are *a* and *b* distinct from *s*? Are they distinct from each other? (Otherwise any set that contains 0 satisfies (2).)2010-08-14
  • 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…".2010-08-14
  • 1
    @SHree: Right. Edited the problem.2010-08-14
  • 0
    @rgrig: a and b need not be distinct.2010-08-14
  • 0
    @Moron: Thanks for the second clarification. However, I realized I must have been picking mushrooms when I posted that first comment after ShreevatsaR replied. :)2010-08-14
  • 7
    This question was posed in MathOverflow (without the condition that |S| = 15) in March, at http://mathoverflow.net/questions/16857/existence-of-a-zero-sum-subset . It has still not been answered.2010-09-07
  • 0
    @Tony: Thanks for the link!2010-09-07
  • 0
    @Robby: Thanks to Robby too, I see the deleted answer.2010-09-07
  • 10
    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?2010-09-08
  • 0
    @Matt: No idea!2010-09-08
  • 0
    Check out the solution I posted last week to the MO problem! I decided to work on that one because I felt like an existence proof should come before a result on the size of the zero sum set, I thought the size result seemed much more difficult actually. After I posted this, http://math.stackexchange.com/questions/4678/…, I realized that the method of constructing a path which leads to an arbitrary vertex is a very powerful tool; it actually proves the "weaker statement" about repeated elements in the zero sum set in a neat way.2010-09-21
  • 0
    @Aryabhata: This is a really nice puzzle! +1! (None of the tricks I try seem to lead anywhere)2011-06-12
  • 0
    @Eric: Yeah, this problem seems be surprisingly tough!2011-06-12
  • 5
    One source for this problem is http://www.maths.tcd.ie/pub/Maths/ProblemCorner/Problems-15.pdf . Unfortunately this is in Set 15, and solutions are posted only through Set 9.2014-07-13
  • 0
    @NoamD.Elkies: Thank you!2014-07-13

4 Answers 4