Problem: Let $m \ge 2$ be an integer,
$A$ a finite set of integers (not necessarily positive)
and $B_1$, $B_2$, \dots, $B_m$ subsets of $A$.
Suppose that, for every $k=1,2,\dots,m$,
the sum of the elements of $B_k$ is $m^k$.
Prove that $A$ contains at least $\frac{m}{2}$ elements.

\end{enumerate}

Solution: If $0 \le X < m^{m+1}$ is a multiple of $m$, then write it in base $m$ as
\[ X = \sum_{i=1}^m c_i m^i \qquad c_i \in \{0,1,2,\dots,m-1\} \]
Then swapping the summation to over $A$ through the $B_i$'s gives
\[ X = \sum_{i = 1}^n \left( \sum_{b \in B_i} b \right) c_i
  = \sum_{a \in A}  f_a(X) a
  \quad\text{where}\quad
  f_a(X) \coloneq \sum_{i : a \in B_i} c_i.
\]

Evidently, $0 \le f_a(X) \le n(m-1)$ for any $a$ and $X$.
So, setting $|A| = n$, the right-hand side of the display takes on at most
$\left( n(m-1) + 1 \right)^n$ distinct values.
This means
\[ m^m \le \left( n(m-1) \right)^n \]
which implies $n \ge m/2$.

\begin{remark*}
  [Motivation comments from USJL]
  In linear algebra terms,
  we have some $n$-dimensional 0/1 vectors $\vec{v_1}$, \dots, $\vec{v_m}$
  and an $n$-dimensional vector $\vec a$
  such that $\vec{v_i} \cdot \vec a = m^i$ for $i=1, \dots, m$.
  The intuition is that if $n$ is too small,
  then there should be lots of linear dependences between $\vec{v_i}$.

  In fact, \emph{Siegel's lemma} is a result that says,
  if there are many more vectors than the dimension of the ambient space,
  there exist linear dependences whose coefficients are not-too-big integers.
  On the other hand, any linear dependence between $m$, $m^2$, \dots, $m^m$
  is going to have coefficients that are pretty big;
  at least one of them needs to exceed $m$.

  Applying Siegel's lemma turns out to solve the problem
  (and is roughly equivalent to the solution above).
\end{remark*}

\begin{remark*}
  In \url{https://aops.com/community/p23185192},
  \texttt{dgrozev} shows the stronger bound
  $n \ge \left(\frac{2}{3}+\frac{c}{\log m} \right)m$ elements,
  for some absolute constant $c > 0$.
\end{remark*}