Problem

Source: Stars Of Mathematics 2014, Seniors, Problem 3

Tags: algebra, combinatorics



Let positive integers $M$, $m$, $n$ be such that $1\leq m \leq n$, $1\leq M \leq \dfrac {m(m+1)} {2}$, and let $A \subseteq \{1,2,\ldots,n\}$ with $|A|=m$. Prove there exists a subset $B\subseteq A$ with $$0 \leq \sum_{b\in B} b - M \leq n-m.$$ (Dan Schwarz)