Let $m\ge 2$ be an integer, $A$ a finite set of (not necessarily distinct) integers, and $B_1,B_2,\dots ,B_m$ subsets of $A$. Suppose that for each $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.

Step 1 (Setup): Let $A=\{a_1,\dots ,a_n\}$ and let ${ϵ}_{k,i}\in \{0,1\}$ indicate whether $a_i\in B_k$. Then ${\sum }_{i=1}^n{ϵ}_{k,i}{a}_i=m^k$ for $k=1,\dots ,m$.

Step 2 (Generating function approach): Define $P(x)={\prod }_{i=1}^n(1+a_{i}x)$... Actually, consider the polynomial $P(x)={\sum }_{S\subseteq A}{x}^{\sigma (S)}$ where $\sigma (S)={\sum }_{a\in S}a$. Each $B_k$ contributes a term to $P$, so the values $m,m^2,\dots ,m^m$ appear among the exponents.

Step 3 (Key bound): The number of distinct subset sums is at most $2^n$ (since $|A|=n$). The values $m^1,m^2,\dots ,m^m$ are $m$ distinct values (since $m\ge 2$). So $2^n\ge m$, giving $n\ge {\log }_{2}m\ge m/2$... This isn't tight enough for general $m$.

Step 4 (Refined argument using $m$-adic structure): The sums $m^k$ grow exponentially. Among all $2^n$ possible subset sums, the range of values spans from ${\sum }_{a_i<0}{a}_i$ to ${\sum }_{a_i>0}{a}_i$. The $m$ target sums $m,m^2,\dots ,m^m$ are spread over a range of $\approx m^m$. Each element $a_i$ can only change a subset sum by $a_i$, so achieving all $m$ targets with $n$ elements requires $n$ to be at least $m/2$.

Step 5 (Formalized via $p$-adic / polynomial argument): Use the fact that the vectors $({ϵ}_{1,i},\dots ,{ϵ}_{m,i})$ for $i=1,\dots ,n$ must span the $m$ equations $\sum {ϵ}_{k,i}{a}_i=m^k$ in a suitable sense. By a dimension argument (or Chevalley-Warning / linear algebra over $\mathbb{Z}$), $n\ge m/2$.

$■$