, 2019

Claim. Suppose that you have $n$ blocks, each of weight at least $1$, and of total weight $s \leqslant 2n$. Then for every $r$ with $-2 \leqslant r \leqslant s$, you can choose some of the blocks whose total weight is at least $r$ but at most $r+2$.

Proof. The base case $n=1$ is trivial. To prove the inductive step, let $x$ be the largest block weight. Clearly, $x \geqslant s/n$, so $s-x \leqslant \frac{n-1}{n} s \leqslant 2(n-1)$. Hence, if we exclude a block of weight $x$, we can apply the inductive hypothesis to show the claim holds (for this smaller set) for any $-2 \leqslant r \leqslant s-x$. Adding the excluded block to each of those combinations, we see that the claim also holds when $x-2 \leqslant r \leqslant s$. So if $x-2 \leqslant s-x$, then we have covered the whole interval $[-2, s]$. But each block weight is at least $1$, so we have $x-2 \leqslant (s-(n-1))-2 = s-(2n-(n-1)) \leqslant s-(s-(n-1)) \leqslant s-x$, as desired.

Let $x_1, \ldots, x_n$ be the weights of the blocks in weakly increasing order. Consider the set $S$ of sums of the form $\sum_{j \in J} x_j$ for a subset $J \subseteq \{1,2, \ldots, n\}$. We want to prove that the mesh of $S$—i.e., the largest distance between two adjacent elements—is at most $2$.

For $0 \leqslant k \leqslant n$, let $S_k$ denote the set of sums of the form $\sum_{i \in J} x_i$ for a subset $J \subseteq \{1,2, \ldots, k\}$. We will show by induction on $k$ that the mesh of $S_k$ is at most $2$.

The base case $k=0$ is trivial (as $S_0 = \{0\}$). For $k > 0$ we have
$$S_k = S_{k-1} \cup \left(x_k + S_{k-1}\right)$$
(where $\left(x_k + S_{k-1}\right)$ denotes $\left\{x_k + s : s \in S_{k-1}\right\}$), so it suffices to prove that $x_k \leqslant \sum_{j<k} x_j + 2$. But if this were not the case, we would have $x_l > \sum_{j<k} x_j + 2 \geqslant k+1$ for all $l \geqslant k$, and hence
$$2n = \sum_{j=1}^n x_j > (n+1-k)(k+1) + k-1$$
This rearranges to $n > k(n+1-k)$, which is false for $1 \leqslant k \leqslant n$, giving the desired contradiction.