This is actually a classic problem. The key to the problem is to split $S$ into two subsets $A,B$ such that $|A| = m, |B| = n-m$ and the residues that the subset sums of $A$ contains the negative of those residues spanned by the subset sums of $B$.Then we can simply take any subset from $B$ and pair up with the appropriate subset of $A$ to get one whose sum is divisible by $m$. Since there are $2^{n-m+1}$ subsets of $B$, we are done. To show this, we will construct $A$ one element at a time. Starting from a random element, we will try to add an element one by one such that the number of residues spanned by the subsets will increase by at least one each time. If we can keep doing this step until $|A| = m$, then the residues spanned will simply be everything mod $m$ and the conclusion is trivial. So assume that it stops when $|A| < m$. Now add in random elements into $A$ until $|A| = m$ and let $S$ be the set of residues spanned at that time and let $b_1,b_2,\ldots,b_l$ the elements which are not in $A$. It is easy to see that we must have $S + kb_i \subseteq S$ for all $k$ and $i$ and hence $S + k_1b_1 + k_2b_2 + \cdots + k_lb_l \subseteq S$ for any $k_1,k_2,\ldots,k_l$. Now by the classic pigeonhole argument, we must have $0 \in S$ since $|A| = m$ and by choosing $k_i$ to be $0$ or $m-1$, the conclusion follows. Edit: There is a mistake - we actually need $|A| = m-1$ and $|B| = n-m+1$. However this is easily fixed since the zero set is counted hence we don't need $|A| = m$ to have $0 \in S$ and we just need to keep adding until it reaches $|A| = m-1$ since it starts off two residues spanned.

An essentially similar solution: for $k = 1,2,...,n$, let $A_k$ denote the subset sums of the first $k$ elements of $S$. Denote by $a_k$ the number of distinct residues $mod~m$ in $A_k$, and $b_k$ the minimum multiplicity of those residues that do appear in $A_k$. We show $b_k \geq 2^{k+1 - a_k}$, which would imply $b_n \geq 2^{n+1-m}$. The proof is by induction, the base case $k = 0$ is trivial. Suppose the claim holds for $k$. If $a_{k+1} > a_{k}$ then the induction step is easy. Otherwise $a_{k+1} = a_k$, so that the distinct residues in $A_k + s_{k+1}$ are the same as those in $A_k$. It then follows that $b_{k+1} \geq 2b_{k}$, again completing the induction.

We prove the result by strong induction on $m$, allowing $m=1$ for our base case (which is immediate). Now, suppose $m = pk$, where $p$ is prime and $k \ge 1$. We say that a \emph{quasi-blob} is a nonempty set $Q$ whose sum of elements is divisible by $k$, but not by $m$. A \emph{blob} is a quasi-blob which is minimal by inclusion. The famous pigeonhole argument now implies blobs have size $\le k$ (among any $k$ integers is a subset with sum $0 \pmod k$). Now suppose we have a disjoint union \[ S = B_1 \cup B_2 \cup \dots \cup B_r \cup T \]where the $B_i$ are blobs, and either $r = p-1$, or $r < p-1$ but is as large as possible. In either case $|T| \ge n - (p-1)k = n - m + p$, so at least $2^{|T|-p+1} \ge 2^{n-m+1}$ subsets of $T$ have sum $0 \pmod k$; call these sets good. If $r < p-1$, any good set is also $0 \pmod m$ (since $r$ was maximal). Now if $r = p-1$, then each good set can be completed by taking some of the blobs $B_1$, \dots, $B_{p-1}$ to give a set with sum divisible by $m = pk$. This is because Cauchy-Davenport theorem ensures that sums of blobs $B_i$ will cover all residues $k, 2k, \dots, pk \pmod{m}$.

v_Enhance wrote: A \emph{blob} is a quasi-blob which is minimal by inclusion. The famous pigeonhole argument now implies blobs have size $\le k$ (among any $k$ integers is a subset with sum $0 \pmod k$). But by pigeonhole we cannot guarantee the existence of a subset whose sum is divisible by $k$ and not divisible by $m$, can we?

Ah, but if $Q$ is a quasi-blob and $\varnothing \neq B \subsetneq Q$ is a sub-quasi-blob, then at least one of $B$ or $Q \setminus B$ is a quasi-blob.

I see, very nice indeed

v_Enhance wrote: Now suppose we have a disjoint union \[ S = B_1 \cup B_2 \cup \dots \cup B_r \cup T \]where the $B_i$ are blobs, and either $r = p-1$, or $r < p-1$ but is as large as possible. But when $r\ge p$ then we don't estimate the set $|T|$? Quote: If $r < p-1$, any good set is also $0 \pmod m$ (since $r$ was maximal). Can you explain explicitly why $r$ was maximal?

Given a set $X$ of integers, write $X_-$ to denote the set formed by negating all the elements of $X$. (For example, $\{ -1,2,6 \}_- = \{1,-2,-6 \}$.) Say that a subset $T$ of $S$ is sunny if the sum of the elements of $T$ is divisible by $m$. We wish to show that $S$ has at least $2^{n-m+1}$ sunny subsets. We will induct on $n$, the base case ($n=m$) being a corollary of the Pigeonhole Principle. For $n \ge m+1$, take an arbitrary non-empty sunny subset $P$ of $S$. Consider an arbitrary element $a \in P$. Let $P'$ be $P \setminus \{a\}$. We will construct two sets $S', S''$ of cardinality $n-1$: $S' = S \setminus \{ a \}$ $S'' = (S \setminus P) \cup P'_-$ By the inductive hypothesis, $S'$ and $S''$ have at least $2^{n-m}$ sunny subsets each. Note that each sunny subset of $S'$ is a sunny subset of $S$ not containing $a$. For each sunny subset $T$ of $S''$, we will transform it into a sunny subset $T'$ of $S$ (where $T'$ contains $a$) in the following manner: Say that $T = A \cup B$, where $A \subseteq (S \setminus P)$ and $B \subseteq P'_-$. Now let $T' = A \cup (P \setminus (B_-))$. Thus $S$ has at least $2^{n-m}$ sunny subsets containing $a$, and at least $2^{n-m}$ sunny subsets not containing $a$, for a total of $2^{n-m} + 2^{n-m} = 2^{n-m+1}$ sunny subsets total. $\blacksquare$

The $2^{n-m+1}$ number suggests we should find a set $A$ of size at least $n-m+1$ such that for all $U\subseteq A,$ there exists a set $g(U)$ such that $U\subseteq g(U)$, and for all elements $x\in A\backslash U, x\notin g(U)$. Proving this clearly suffices. Indeed, this turns out to be true and the crux of this solution. If we can construct a set $S$ of $m-1$ elements such that for all $x\in \mathbb{Z}_m,$ there exist a (not necessarily nonempty) subset of $S$, call $S'$ such that $\sum_{a\in S'} a=x$ in $\mathbb{Z}_m$, we'd be easily done. Now assume this isn't possible. Let $f(T)$ be the set of residues modulo $m$ that can be obtained via a subset of $T$. Initially, $f(T)=\{0\}$ If I push $x$ into the set, then if $x\in f(T), x+t\notin f(T)$ then I put $x+t$ into our set $f(T).$ If there exist $x$ that can increase $f(T),$ we use it. Since $|f(T)|$ has $m-1$ chances to be incremented, it follows that from some point, for all $x$, using $x$ doesn't increase $|f(T)|$. Then, for all $x\in S\backslash T, a\in \mathbb{Z}$, we can see that $f(T)$ actually contains all or none of the residues that are $a$ modulo $\gcd(x,m)$, since we are working in $\mathbb{Z}_m$. In other words, let $d=\gcd(m,\gcd_{x\in S\backslash T} x)$, then $f(T)$ contains all or none of the residues that are $a$ modulo $d$. Since all the elements in $S\backslash T$ are divisible by $d$, it follows that $S\backslash T=A$ works because all elements $dk(\bmod\; m)$ are in $T$, and has size at least $n-|T|\ge n-m+1$, as desired.

Solved with Justin Lee and Raymond Feng. We strong induct on \(m\) with base case \(m=1\) trivial. Assume the hypothesis for \(m\); we will prove it for \(pm\) where \(p\) is prime. Express \(S\) as the disjoint union \[S=\widetilde S\sqcup(S_1\sqcup S_2\sqcup\cdots\sqcup S_k)\]with the following properties: \(k\) is maximal, \(\widetilde S\) is maximal, and for each \(i\), the sum of the elements of \(S_i\) is a multiple of \(m\) but not \(pm\). Claim: For each \(i\), \(|S_i|\le m\). Proof. Assume not, and let \(S_i=\{a_1,a_2,\ldots,a_t\}\). If \(t>m\), at least two numbers from the list \(a_0\), \(a_0+a_1\), \(\ldots\), \(a_0+\cdots+a_t\) are equal by Pigeonhole, so \(a_{i+1}+\cdots+a_j\equiv0\pmod m\) for some \(i<j\). It follows that \(A=\{a_{i+1},\ldots,a_j\}\) and \(S_i\setminus A\) have sum of elements divisible by \(m\), and since the sum of the elements of \(S_i\) is not divisible by \(pm\), neither is the sum of the elements of either \(A\) or \(S_i\setminus A\). Thus we may replace \(S_i\) with \(A\) or \(S_i\setminus A\), contradiction. \(\blacksquare\) Now we take two cases: First case: Suppose \(k<p-1\). Then \(|\widetilde S|\ge n-km>n-(p-1)m\), so by the inductive step, there are \(2^{|\widetilde S|-m+1}\ge 2^{n-pm+1}\) subsets of \(\widetilde S\) with sum divisible by \(m\). But since \(k\) is maximal, each such subset has sum divisible by \(pm\). Second case: Suppose \(k\ge p-1\). Let \[S=\overline S\sqcup(S_1\sqcup S_2\sqcup\cdots\sqcup S_{p-1}),\]so that \(\overline S=\widetilde S\sqcup(S_p\sqcup S_{p+1}\sqcup\cdots\sqcup S_k)\) and \(|\overline S|\ge n-(p-1)m\). Claim: Each multiple of \(m\) (modulo \(pm\)) may be expressed as the sum of the elements of a subset of \(S_1\sqcup S_2\sqcup\cdots\sqcup S_{p-1}\). Proof. Let \(s_i=\frac1m\sum_{s\in S_i}s\) for each \(i\) be integers that are not multiples of \(p\). Among \(s_1\), \(\ldots\), \(s_{p-1}\), let each \(i=1,\ldots,p-1\) appear \(a_i\) times. Then the \(a_i\) instances of \(i\) may express the numbers \(A_i=\{0,i,2i,\ldots,a_ii\}\), i.e.\ \(a_i+1\) numbers. By Cauchy-Davenport, \[|A_1+A_2+\cdots+A_{p-1}|\ge\min\{p,a_1+\cdots+a_{p-1}+1\}=p,\]proving the claim. \(\blacksquare\) By the inductive step, there are \(2^{|\overline S|-m+1}\ge 2^{n-pm+1}\) subsets of \(\overline S\) with sum divisible by \(m\). For each such subset, we may add on a subset of \(S_1\sqcup S_2\sqcup\cdots\sqcup S_{p-1}\) so that the resulting sum is divisible by \(pm\).

Lemma: Let $b_1,\cdots,b_{m-1}$ be nonzero (possibly equal) elements of $\mathbb{Z}/m\mathbb{Z}$ such that for all $d\mid m$ there exists at least $d-1$ indices $j$ such that $b_j$ is not a multiple of $d$. Prove that $$\{ \sum_{j\in S} b_j \mid S\subseteq [m-1]\} = \mathbb{Z}/m\mathbb{Z}$$ Proof: We prove the strengthened statement $A(n)$: let $n\ge m-1$, and let $b_1,\cdots,b_{n}$ be nonzero elements of $\mathbb{Z}/m\mathbb{Z}$ such that for all $d\mid m$ there exists at least $d-1$ indices $j$ such that $b_j$ is not a multiple of $d$. Prove that $$\{ \sum_{j\in S} b_j \mid S\subseteq [n]\} = \mathbb{Z}/m\mathbb{Z}$$ Let $m$ be the minimal counterexample. In other words, we have $$\left| \{0,b_1\} + \cdots + \{0,b_{n}\} \right|<m$$ Let $T$ be a set that is initially the emptyset, and elements will be added to $T$. When $T=\{t_1,\cdots,t_a\}$, as long as there exists $j$ such that $j\notin T$ and $$|\{0,b_j\} + \{0,b_{t_1}\} + \cdots + \{0,b_{t_a}\}| > | \{0,b_{t_1}\} + \cdots + \{0,b_{t_a}\}|$$we add $j$ to $T$. Suppose we add the elements of $T$ as $t_1,\cdots,t_a$ IN THAT ORDER. Let $$x_j = | \{0,b_{t_1}\} + \cdots + \{0,b_{t_{j-1}}\} |$$ If $a\ge m-1$, then $x_j \ge x_{j-1}+1$ for all $j=2,3,\cdots,a$, we clearly have $x_a\ge m$, so we are done. The other case is $a<m-1$. Let $U = \{ b_q \mid q\notin T\}$, $$d=\gcd(m,\gcd_{u\in U} u), W = \{0,b_{t_1}\} + \cdots + \{0,b_{t_a}\}$$then for some subset $D\in \mathbb{Z}/d\mathbb{Z}$ Claim: There exists a subset $D\subset \{0,\cdots,d-1\}$ such that $U\in \mathbb{Z}/m\mathbb{Z}$ is EXACTLY the set of all residues in $\mathbb{Z}/m\mathbb{Z}$ that are equivalent to an element in $D$ modulo $d$. Proof: Note that $\{b\}+U = U$ imply that for all $u\in U$, $u+tb\in U$ for all integers $t$. In other words, if $\beta=\gcd(b,m)$, then $u+t\beta\in U$ for all integers $t$. By Bezout, if $U=\{u_1,\cdots,u_p\}$, then there exists integers $a_1,\cdots,a_p$ such that $\sum_{j=1}^p a_ju_j \equiv d(\bmod\; m)$. This readily implies that $u\in U \iff u+d\in U$, and therefore our claim holds. Back to the problem. Since all non-multiples of $d$ in $\{b_1,\cdots,b_{m-1}\}$ are included in $\{b_t \mid t\in T\}$, $$X=\{b_t \mid t\in T, d\nmid b_t\}=\{x_1,\cdots,x_l\}$$in $\mathbb{Z}/d\mathbb{Z}$ satisfy the statement for $d$ (namely $A(d)$). Clearly $d< m$, so by inductive hypothesis, $$\{ \sum_{j\in S} x_j \mid S\subseteq [l]\} = \mathbb{Z}/d\mathbb{Z}$$ Therefore, $D=\mathbb{Z}/d\mathbb{Z}$. We are done because "$U\subseteq \mathbb{Z}/m\mathbb{Z}$ is EXACTLY the set of all residues in $\mathbb{Z}/m\mathbb{Z}$ that are equivalent to an element in $D$ modulo $d$" With this lemma in mind, the problem is a corollary because we can use induction on $n$.

We uploaded our solution https://calimath.org/pdf/ChinaTST2016-1-6.pdf on youtube https://youtu.be/Srm9H8tXsOs.