Existence of a zero-sum subset
The answer is in the affirmative; indeed,
If $S$ is a finite non-empty subset of any abelian group such that every element of $S$ is a sum of two other (possibly, equal to each other) elements, then $S$ has a non-empty, zero-sum subset.
For a complete proof, see this recent preprint by János Nagy, Péter Pach, and myself. The proof is a little too long to be presented here but at least, to indicate the general direction, here is our main lemma.
Lemma. Suppose that $M$ is an integer square matrix of order $n$, representable as $A-I$ where $A$ has all its elements non-negative and all row sums equal to $2$, and $I$ is the identity matrix. Then there exist nonzero vectors $u,v\in\{0,1\}^n$ such that $M^Tu=v$; that is, there exists a system of rows of $M$ such that their sum is a nonzero, zero-one vector.
In fact, for our purposes it would suffice to have any nonzero vector $u$ satisfying $M^Tu\in\{0,1\}^n$; having $u$ itself to be zero-one is an extra (compare with Bill Thurston's answer above).
The proof of the main lemma is completely elementary, by induction on $n$.
Historically, the question seems to originate from a problem contributed by Dan Schwarz to the EGMO 2012 (European Girls’ Mathematical Olympiad):
Does there exist a set of integers such that every element of the set is a sum of two other elements, while the set does not contain a finite nonempty zero-sum subset?
The answer to this question is positive since the set here is allowed to be infinite.
A weaker result can be obtained if we do not require the solution set to be distinct:
Lemma. There exist $i_1, \ldots, i_m$ (not necessary distinct) so that $a_{i_1}+a_{i_2}+ \ldots +a_{i_m}=0$.
proof. Consider the sum of all the equations $a_i=b_i+c_i$ over all $a_i \in S$, where $b_i,c_i \in S$ guaranteed by the definition of $S$, we have
$\sum_i a_i = \sum_i (b_i+c_i)$.
Noticed that the multiset {$b_i,c_i$} must contain all elements in $S$, otherwise we can remove the elements in $S \setminus$ {$b_i,c_i$}, obtaining another $S^*$ which satisfies the property.
Now since $S \subseteq$ {$b_i,c_i$}, we cancel out $\sum_i a_i$ with the same numbers in {$b_i,c_i$}, which makes the equality the form $a_{i_1}+a_{i_2}+ \ldots +a_{i_m}=0$ with $a_{i_k} \in$ {$b_i,c_i$}, i.e. $a_{i_k} \in S$. Since there are totally $2|S|$ elements in multiset {$b_i,c_i$} and $0 \notin S$, we have the lemma. $\square$
-- Edited at 2010/03/07 --
This conjecture is related to a special case of the Rainbow conjecture, which is highly related to the Caccetta-Häggkvist conjecture; see a survey by Sullivan.
For a digraph $G$ and edge sets $E_1, \ldots, E_k \subseteq E(G)$, denote $G_i = (V(G), E_i)$ and we say a subgraph $H$ of $G$ is rainbow if $|E(H) \cap E_i| \leq 1$ for each $i$ and $|E(H)| \geq 1$. Let $\delta_i^+(v)$ denote the outdegree of $v$ in graph $G_i$.
The Rainbow conjecture states that,
Conjecture. For a simple digraph $G$, either
- There is a rainbow (di)cycle in $G$, or
- There exists a node $v$ s.t. |{$w|\exists \text{ rainbow path from } v \rightarrow w $}| $\geq \sum_{i=1}^k \delta^{+}_{i}(v)$.
Now by constructing a digraph $G$ with directed edge $(u,v)$ in $E_w$ if $u+w = v$,
there is a dicycle in $G$ iff there is a set $U$ s.t. $\sum_{x\in U} x = 0$, for $x \in S$.
Since the second condition of the Rainbow conjecture can not be satisfied for $k=|S|$ and $\delta_{i}^+(v) \geq 1$ for all $i$$^@$, there must be a dicycle in $G$ with distinct colors,
that is, a subset $U$ with distinct numbers.
@ The condition $\delta_{i}^+(v) \geq 1$ is wrong.
In the survey by Sullivan, the conjecture is solved for the special case that $\delta_{i}^+(v) \leq 1$ for all $v$ and all $i$, which is the case since for a given $u$ and $w$, there is at most one solution to the equation $u+v=w$, which corresponds to the directed edge $(u,v) \in E_w$.
The brilliant proof of Seva, János and Péter seems pretty short for me. Here it is.
We prove the following statement which obviously implies the claim.
Let $S$ be a non-empty finite set of variables. Assume that for each $a\in S$ we have a linear form $\ell_a:=b(a)+c(a)-a$ for certain $b(a),c(a)\in S\setminus\{a\}$ (possibly $b(a)=c(a)$). Then there exists a non-empty set $A\subset S$ such that all coefficients of the linear form $\sum_{a\in A}\ell_a$ belong to $\{0,1\}$.
By induction, we may assume that this holds for smaller values of $|S|$.
Consider the multiset $T=\{b(a),c(a):a\in S\}$. We have $|T|=2|S|$. If $T$-multiplicity of every element $x\in S$ equals 2, we have $\sum_{a\in S} \ell_a=\sum_{x\in S} x$, so we may take $A=S$. If $T$-multiplicity of some $x\in S$ equals 0, just remove $x$ from $S$ ($S$ remains non-empty) and apply induction.
It remains to consider the case when $T$-multiplicity of some $z\in S$ equals 1. Say, $z=b(x)$, $\ell_x=z+y-x$ for certain $y\notin \{x,z\}$. Denote $T=S\setminus \{x,z\}$. For $a\in T$ consider the linear form $\ell_a'$, obtained from $\ell_a$ by replacing $x$ by $y$ if necessary (note that if this happens for $\ell_y$, i.e., $\ell_y=x+t-y$, then $\ell_y+\ell_x=z+t$ and we may take $A=\{x,y\}$.) By induction, the sum of several such forms $\ell_a'$ have coefficients 0's and 1's. For the corresponding forms $\ell_a$ this means either what we need, or that the coefficient of $y$ in their sum equals -1 and the coefficient of $x$ equals 1 or 2. In the latter case add $\ell_x$ to their sum.