IMO 2019 Shortlisted Problems

Claim. Suppose that you have $n$ blocks, each of weight at least $1$, and of total weight $s⩽2n$. Then for every $r$ with $-2⩽r⩽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⩾s/n$, so $s-x⩽\frac{n-1}{n}s⩽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⩽r⩽s-x$. Adding the excluded block to each of those combinations, we see that the claim also holds when $x-2⩽r⩽s$. So if $x-2⩽s-x$, then we have covered the whole interval $[-2,s]$. But each block weight is at least $1$, so we have $x-2⩽(s-(n-1))-2=s-(2n-(n-1))⩽s-(s-(n-1))⩽s-x$, as desired.

---

Alternative solution.

Let $x_1,\dots ,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,\dots ,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⩽k⩽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,\dots ,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⩽{\sum }_{j<k}{x}_j+2$. But if this were not the case, we would have $x_l>{\sum }_{j<k}{x}_j+2⩾k+1$ for all $l⩾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⩽k⩽n$, giving the desired contradiction.