Suppose block $i$ has weight $a_i$, and the total weight be $S=a_1+\cdots+a_n$. We prove a more general claim, which implies the problem. Claim: If $S\le 2n$, then we can get a subset of the blocks summing to a number in each range $[r,r+2]$, for all $r\in [0,S-2]$. Proof: We induct on $n$. For $n=1$, we only need to consider the case $S=2$, which is obvious. Now, assume that for any $b_1+\cdots+b_{n-1}=S'$, with $S'\le 2n-2$, we can get a subset of the $b_i$'s summing inside each of the ranges $[0,2] \to [S'-2,S']$. We are given some $r$, and we want a subset of the $a_i$'s summing to a number in $[r,r+2]$. WLOG let $a_n$ be the largest $a_i$. If $a_n < 2$, then get the subsets by just adding each $a_i$ to the set; since each $a_i<2$, we won't miss any intervals. Henceforth assume $a_n\ge 2$. Case 1: $a_n\le r$. Include $a_n$ in the subset. Then, we need a subset of $a_1,\ldots,a_{n-1}$ summing to a number in $[r-a_n, r+2-a_n]$. In order to utilize the inductive hypothesis to finish this, we need to check (1) $S-a_n \le 2n-2$; this is true since $S-a_n\le 2n-a_n \le 2n-2$, and (2) $r-a_n\le S-a_n-2$, so that the new interval is contained in the inductive bound; this is true since $r\le S-2$. Case 2: $r<a_n \le r+2$. Have the subset be just $a_n$. Case 3: $a_n >r+2$. Don't include $a_n$ in the subset. Then, we need a subset of $a_1,\ldots,a_{n-1}$ summing to a number in $[r,r+2]$. By the same logic as in Case 1, we know $S-a_n \le 2n-2$, so we can finish by induction if $r\le S-a_n$. (This bound would imply that $[r,r+2]$ and some interval in $[0,2]\to [S-a_n-2,S-a_n]$ intersect.) We have \[ a_n=S-(a_1+\cdots+a_{n-1}) \le S-(n-1) \le \tfrac{S}{2}+1, \]since $S\le 2n$. So $2a_n \le S+2$, i.e. $a_n \le S+2-a_n$. Now, $r+2 < a_n \le S+2-a_n$, so $r<S-a_n$, as desired.

Pretty terrible writeup, but I liked the problem. Let $S=\{a_1,\dots, a_n\}$ be the set of weights, where $1\leq a_1\leq a_2\leq \cdots \leq a_n$. We call a real $r\in [0,2n]$ good if there exists a subset $T$ of $S$ such that $\sum_{a_i\in T}a_i \in [r,r+2]$. Our goal is to show all $r$ are good. The main idea is that if $r$ is good for all $0\leq r\leq A$ and $B\leq r\leq C$, then $r$ is good for all $0\leq r\leq C$ if $B\leq A$. We show that we can successively `extend' this inequality to cover the entire interval. Claim: If $a_1+a_2+\cdots + a_k=K$, then $a_{k+1}\leq K+2$. Proof: Suppose $a_{k+1}>a_1+\cdots + a_k+2$. Then \begin{align*} 2n &= a_1+\cdots + a_k + a_{k+1} + \cdots + a_n \\ &>K + (n-k)(K+2) \\ \implies \frac{2k}{K}&>n-k+1\end{align*}which is easily seen to be a contradiction since $K\geq k$. $\blacksquare$ Now we prove that for all $n$, all $r$ in the interval $[0,a_1+\cdots + a_n]$ are good. Notice that if $0\leq r\leq \sum_{a_i \in A} a_i$ is good where $a_1\notin A$, then we can compute that all $r\in [0, a_1+\sum_{a_i \in A} a_i]$ are good using the fact that $a_1\leq 2$. Also, if all $r$ with $0\leq r\leq a_1+a_2+\cdots + a_m+\sum_{a_i \in B} a_i$ are good for some $m$ and some (possibly empty) set $B$, we can compute that all $0\leq r\leq a_{m+1}+\sum_{a_i\in B} a_i$ are good. So using the `covering inequality' idea, we can interpret this as a game on a blackboard where one may: i) Write $1$ on the board if it isn't there, ii) Replace $1,2,\cdots, m$ with the number $m+1$. so that at any point in time if the numbers on the board are $b_1,\cdots, b_k$, then $r$ is good for all $0\leq r\leq a_{b_1} + \dots + a_{b_k}$. It's easy to induct to show that we can eventually have all the numbers $\{1,2,\cdots, n\}$ on the board. This means that all $r\in [0,2n]$ are good so we're done.

Suppose the blocks have weights $1 \leq w_1 \leq w_2 \leq \dots \leq w_n$. We will use induction on $\lfloor r \rfloor$. If $\lfloor r \rfloor$ = 0, then $0 \leq r < 1$. Since $$nw_1 \leq w_1 + w_2 + \cdots + w_n = 2n \Longrightarrow w_1 \leq 2$$which gives us $$r < 1 \leq w_1 \leq 2 \leq 2 + r$$Suppose the claim holds for all $r$ with $\lfloor r \rfloor < k$ for some $k\geq 1$. Take any $r$ such that $\lfloor r \rfloor = k$. If $r \leq w_1$, then $r \leq w_1 \leq 2 \leq r + 2$ and we are done. If $w_{\ell} \in [r, r+2]$, then we can just take $w_{\ell}$. Otherwise, let $1\leq i \leq n$ be such that $$1 \leq w_1 \leq w_2 \leq \dots \leq w_i < r < r + 2 \leq w_{i+1} \leq \cdots \leq w_n$$Case 1: If $r = w_1 + w_2 + \cdots + w_i$ , then we are done. Case 2: If $r < w_1 + w_2 + \cdots + w_i$, then let $j$ be the minimum number $\leq i$ such that $$w_j + w_{j+1} + \cdots + w_i \leq r$$Note that this $j$ exists because $w_i<r< w_1 + w_2 + \cdots + w_i$, and we have $j \geq 2$. Now, consider $$r' = r - (w_j + w_{j+1} + \cdots + w_i)$$Since $$0 \leq \lfloor r' \rfloor \leq \lfloor r - w_i \rfloor \leq \lfloor r \rfloor - 1 \leq k-1$$by induction hypothesis $$r' = w_{s_1} + w_{s_2} + \cdots + w_{s_t}$$for some $s_1 < s_2 < \dots < s_{t}$. Then $$r = w_{s_1} + w_{s_2} + \cdots + w_{s_t} + w_j + w_{j+1} + \cdots + w_i$$So if $s_t < j$, then we are done. Otherwise, $$r \geq w_j + w_j + w_{j+1} + \cdots + w_i \geq w_{j-1} + w_j + w_{j+1} + \cdots + w_i > r$$which is a contradiction. Case 3: Suppose $$w_1 + w_2 + \cdots + w_i < r < r+2 < w_{i+1} \leq \cdots \leq w_n.$$Since $\lfloor r-1 \rfloor = k-1$ $$r - 1 = w_{s_1} + w_{s_2} + \cdots + w_{s_t}$$for some $s_1 < s_2 < \dots < s_{t}$. If $s_t \geq i+1$, then we would have $$r - 1 \geq w_{i+1} > r+2$$which is a contradiction. If $s_t \leq i$, then $$w_1 + w_2 + \cdots + w_i \geq w_{s_1} + w_{s_2} + \cdots + w_{s_t} = r - 1$$Moreover, $$r > w_1 + w_2 + \cdots + w_{i} \geq \underbrace{1 + 1 + \cdots + 1}_{i} = i$$Then \begin{align*} 2n = (w_1 + w_2 + \cdots + w_i) + (w_{i+1} + \cdots + w_{n}) \geq r - 1 + (r+2)(n-i) > (i-1) + (i+2)(n-i) \end{align*}which gives us $$2n \geq i + (i+2)(n-i) \Longrightarrow i \geq n-1$$Note that if $i=n$, then $$2n = w_1 + w_2 + \cdots + w_n < r < 2n-2$$which is a contradiction. On the other hand, if $i = n-1$, then $$n-1 \leq w_1 + w_2 + \cdots + w_{n-1} < r < r+2 < w_n = 2n-(w_1 + w_2 + \cdots + w_{n-1}) \leq 2n -(n-1) = n+1$$But this is also impossible because both $r$ and $r+2$ lie in $(n-1, n+1)$ which has length $2$.

Comment: A lot of Thailand TST takers found this a bit tricky (say for IMO 1/4), but in my opinion this is not very hard, especially if you have seen problems with similar flavor like ISL 2013 C1, USA TSTST 2019 P4, etc. We slightly modify the problem and induct the following claim on $n$. Claim: [Generalization] A set of $n$ blocks, each has weight at least one; and the total weight is $s\leq 2n$ is given. Prove that for any real number $0\leq r\leq s$, we can pick a subset of those blocks which the sum of weights is at least $r$ but at most $r+2$. The base case $n=1$ is trivial so let us focus on the inductive step. Let the weights be $x_1\leq x_2\leq\hdots\leq x_n$. We split into two cases. Case 1. $x_n\leq 2$ Consider sequence $$0, x_1, x_1+x_2, x_1+x_2+x_3,\hdots, x_1+x_2+\hdots+x_n.$$The increment of this sequence is at most $2$. Therefore at least one term works, done. Case 2. $x_n\geq 2$. Notice that $x_1+x_2+\hdots+x_{n-1}\leq 2n-2$. We first prove the following bound to restrict the growth of $x_n$. Claim: We have $x_n\leq x_1+x_2+\hdots +x_{n-1}+2$ Proof: Straightforward. We have $$x_n \leq 2n-(x_1+x_2+\hdots+x_{n-1})\leq n+1\leq x_1+x_2+\hdots+x_{n-1}+2.$$So we are done. This is the only place where we used the hypothesis $x_1\geq 1$. $\blacksquare$ Now we consider three subcases. If $r\leq x_1+x_2+\hdots+x_{n-1}$, then use the induction hypothesis to pick a subset of $\{x_1,x_2,\hdots,x_{n-1}\}$ which the sum is in $[r,r+2]$. If $x_1+x_2+\hdots+x_{n-1}\leq r\leq x_n$, then $\{x_n\}$ works. If $r\geq x_n$, then use the induction hypothesis to pick a subset of $\{x_1,x_2,\hdots,x_{n-1}\}$ which the sum is in $[r-x_n, r-x_n+2]$. Adding $x_n$ to this subset gives the conclusion. Having exhausted three cases, we are done.

We will prove the result using induction on $n$. Our base case of $n = 1$ is true ($1$ block of weight $2$, and $0\leq r \leq 0$, so $r = 0$, and we take no blocks). Assume $n$ is true, we will prove that is also works for $n+1$. Assume there existed a block with weight $2$. Then, we can ignore this block, so we have $n$ blocks with weight $2n$. For all $0\leq r\leq 2n-2$, we can find subsets of blocks due to our inductive hypothesis. Then, for $r = 2n-1, 2n$, just take every block except for the block with weight $2$. Thus, we assume no block has weight $2$. Let there be $a$ amount of $1$s. Then, there are $n-a$ blocks with weight greater or equal to $3$; we have the total sum is \[2n \geq a + 3(n-a) = 3n-2a\Rightarrow a\geq \frac{n}{2}\]Then, I claim there exists a block with weight greater than $1$ but less than or equal to $\frac{n}{2}$. This is because, excluding the blocks with weight $1$, the average weight of the blocks is $\frac{2n-a}{n-a}$. I claim this is less than or equal to $\frac{n}{2}$, which would prove that there existed such a block (or else that average would be unobtainable). We have: \[\frac{2n-a}{n-a}\leq \frac{n}{2} \Rightarrow n^{2} - na \geq 4n-2a \Rightarrow n^{2} - n(a+4) + 2a\geq 0\]Now, we have to prove the determinant is greater or equal to $0$. We have the determinant is: \[a^{2} + 8a + 16 -8n\]We can use the fact that $a\geq \frac{n}{2}$ to get: \[a^{2} + 8a + 16 - 8n \geq \frac{n^{2}}{4} + 4n-8n + 16 = \frac{1}{4}(n^{2} - 16n + 64) = \frac{1}{4}(n-8)^{2}\geq 0\]Thus the discriminant is non-negative, so there must be a block with weight less than or equal to $\frac{n}{2}$. Let this block have weight $b$. Then, consider removing the block with weight $b$ and $b-2$ of the blocks with weight $1$ (this is possible since $b\leq\frac{n}{2}\leq a$). We will have $n-b+2$ blocks with $2n+4-2b$ total weight, so by our inductive hypothesis, we can satisfy the condition for all $0\leq r\leq 2n-2b+2$. Finally, observe that for each group, we can either add: $1, 2, \ldots b-2, b, b+1, \ldots 2b-2$ more weight (from the blocks we removed). Then, take the subset with weight between $2n-2b+2, 2n-2b+4$. We can then add $1, 2, \ldots b-2, b, b+1, \ldots 2b-2$ to this subset, which will satisfy all $r$. (even though we can not add $b$ to this subset, it will still be satisfied by adding either $b-2$ or $b$). Our inductive step is complete, so we conclude that this is true for all $n$.

Let $1\leq a_1\leq a_2\leq \dots \leq a_n$ be the weights of the blocks. For each $S\subset\{1,2,\cdots,n\}:=[n]$, let $\omega(S)=\sum_{s\in S} a_s$ be the sum of weights of blocks with indices in $S$. We are to show that for all $S\subset[n]$, there exists another $S_1\subset[n]$ such that $0<\omega(S_1)-\omega(S) \leq 2$. Let $S_k=\{\omega(S)|S\subset[k]\}$ be the set of sums of weights of subsets of blocks chosen from $\{1,2,\cdots,k\}$. Note that $S_k=S_{k-1}\cup (a_k+S_{k-1})$. We induct on $k$ to show the desired result. The base case ($k=0$) is trivial. For $k>0$, it suffices to show that $a_k\leq \sum_{j<k} a_j+2$. Suppose otherwise, then $$a_n\geq a_{n-1}\geq\cdots\geq a_k>\sum_{j<k} a_j+2\geq k-1+2=k-1.$$This means that $$2n=a_1+a_2+\cdots+a_n > k-1+(n+1-k)(k+1)$$After expansion, $$n>k(n+1-k)$$This presents a contradiction.

As above we show that the claim is true for any $n$ blocks with a total mass of $\le 2n$, and induct on $n$: Base case $n=1$ is clear. Inductive step: Suppose we have $n+1$ blocks $a_1\le \cdots a_{n+1}$, our conclusion holds for $a_1, \cdots , a_n$ and if $S=a_1+\cdots a_n$ then by induction hypothesis the claim would hold for $0\le r\le S-2$ (where we can even extend it to $0\le r\le S$ as we can simply take $\{a_1, \cdots, a_n\}$ for a total weight of $S$. Therefore all It remains it to show the same for $S+1\le r\le S+a_{n+1}-2$. To determine if it's possible to choose a subset of blocks with total weight in $[r, r+2]$ where $r>S$, by choosing the element $a_{n+1}$, we're left with choosing a subset from $\{a_1, \cdots , a_n\}$ with sum in $[r-a_{n+1}, r-a_{n+1}+2]$. Considering the empty set (weight sum 0), and by hypothesis, it then suffices to show that $r-a_{n+1}+2\ge 0$, and that $r-a_{n+1}\le S$. Thus $a_{n+1}\le n+2$. The fact that $r-a_{n+1}\le S$ follows from $r\le S+a_{n+1}$. In addition, given that $S\ge n$ and $S+a_{n+1}\le 2(n+1)$, we have $r-a_{n+1}+2\ge S+1-a_{n+1}+2\ge n+3-(n+2)=1$, as desired.

Not sure if this works since I haven't seen this solution above: Let the blocks have weights $a_1,a_2,\ldots,a_n$. Consider all sums of the form $\sum_{i \in X} a_i$, where $X$ is a $j$-element subset of $\{1,2,\ldots,n\}$. Say that all such sums are less than or equal to $r$ for some $r \in [0,2n-2]$. Then, summing yields ${n-1 \choose j-1}(2n) \leq {n \choose j}r$, or $r \geq 2j$. Similarly, if all such sums are greater than or equal to $r+2$, then summing yields ${n-1 \choose j-1}(2n) \geq {n \choose j}(r+2)$, or $r+2 \leq 2j$. This means that if $2j-2 \leq r \leq 2j$, there exists some $j$-element subset $X$ of $\{1,2,\ldots,n\}$ with sum in $[r,r+2]$. (Equality must be achieved at all subsets for $r=2j-2$ or $r=2j$ to be true). Ranging $j$ from $1$ to $n-1$ yields the desired claim.

We are going to prove that if $w_1+w_2+...+w_n=an$ for $a\in [1,2]$ $(w_i\ge 1) $ then the set of all possible values of sums of subsets $S$ doesn't have gaps $>a$ in $[0,an]$. (note that it contains $0,an$) We induct on $n$ suppose it is $w_1\le ...\le w_{n-1} \le w_n$ Then $w_1+w_2+...+w_{n-1}=a'(n-1)$ with $a'\le a$ for these $w_1,...,w_{n-1}$ let the set of sums be $S'$ and the hypothesis gives it doesn't contain $a'-$gaps in $[0,a'(n-1)]$.

The above show that $S=S'\cup (S'+w_n)$ doesn't contain $a-$gaps ( $S'+w_n$ has $w_n$ as the first element and is less than the last element of $S'$ plus $a$ , $w_n\le a'(n-1)+a$, and both $S'$ and $S'+w_n$ do not contain $a'\le a-$ gaps.) We also have this for $n=1$ so we are done.

Here is a very clean solution via induction. It is easy to see that n = 2, n = 3 works. We now claim that if $n$ and $n+1$ work, then $n+2$ also works. WLOG $a_1 \le a_2 \le \dots \le a_n$ and let $a_1+ \cdots+ a_n = 2n, b_1+b_2+\cdots+b_{n+1} = 2n+2, c_1+c_2+\cdots+c_{n+2} = 2n+4.$ Let all of the possible combinations of the a's, the b's, the c's be denoted as $A, B, C$ respectively. Claim for every combination in C, there exists a combination in A Proof. We can split into the following cases: Case 1: $2 \notin \{c_1, \dots, c_n\}$ Since $2n+4-2n = 4,$ we must have $\{c_1, \dots, c_n\} = \{a_1, \dots, a_n\} \cup \{1,3\}$ with $2 \notin\{a_1, \dots, a_n\}.$ which indeed satisfies the conditions of any combination in $C.$ Case 2: $\{\underbrace{2, \dots, 2}_{k}\} \in \{c_1, \dots, c_n\}$ Similair to the previous case, we need $\{c_1, \dots, c_n\} = \{b_1, \dots, b_n\} \cup \{2\}$ with (# of times 2 is in {b_1, \dots, b_n} )+(1) = k The claim shows that all a,b satisfying the problem statement implies c satisfying the problem statement, which completes the induction, so we are done.

We show the following generalization: Claim: If we have $n$ blocks summing to $S \leq 2n$, then for any $-2 \leq r \leq S$ we can pick some subset with sum in the range $[r,r+2]$. Proof: Induct on $n$; base case $n=1$ is obvious. For the inductive step let the weights be $a_1 \leq a_2 \leq \cdots \leq a_{k+1}$ with sum $S \leq 2k+2$. The induction hypothesis tells us that the $k$ lightest rocks take care of $-2 \leq r \leq S-a_{k+1}$. Adding the heaviest rock to these sets also takes care of $a_{k+1}-2 \leq r \leq S$. Thus it clearly suffices to show that $a_{k+1}-2 \leq S-a_{k+1}$, which is true because $$2a_{k+1} \leq 2 ( S- ( \underbrace{1+1+ \cdots +1}_{k} ) ) = 2S-2k \leq S+2$$

combo list more like induction list :angery: We claim that the following generalization is true: Claim: If the blocks have total weight $S \le 2n$, then for each real number $r$ with $-2 \le r \le S$, we can choose a subset of the blocks with total weight in $[r, r+2]$ (including the empty set with weight $0$). Proof: Proceed with induction on $n$. The base case $n=1$ is easy; there is $1$ block with weight at most $2$, so all intervals contain $0$. Now assume the claim for $n$; we will prove it for $n+1$. Consider a set of $n+1$ blocks with total weight $S \le 2n+2$. Say the largest block has weight $w$. Then $w$ is at least $\frac1{n+1} S$, so the total weight $S-w$ of the rest is at most \[ S - \frac1{n+1} S = \frac{n}{n+1} S \le 2n,\]hence we may apply the inductive hypothesis. It follows that We can cover the intervals $[r, r+2]$ for $-2 \le r \le S - w$ Furthermore, we can just add $w$ to everything to obtain the intervals where $w - 2 \le r \le S$. If $S - w \ge w - 2$, then we cover everything. If not, \[ 2S - 2w < S - 2 \le 2n,\]so $S - w < n$. But there are $n$ blocks other than the one with weight $w$, each with weight at most $1$, contradiction. $\blacksquare$

This problem sucks. $[-2, S]$ sucks. Suppose that the sum of $n$ blocks with weights $a_1, \ldots , a_n$ is $S \leq 2n$. I claim that we can always find a subset of blocks summing to weight $\in [r, r+2]$ for all $r \in [-2, S]$. We will show this with induction on $n$. The base case of $n = 1$ is obvious. Next, suppose the result is true for any $k$ blocks with sum $\leq 2k$. Consider blocks with weights $a_1 \leq \ldots \leq a_k$ that sum to $\leq 2k + 2$. Clearly $a_k \geq 2$ by pigeonhole so we can achieve all intervals with $r \in [-2, S - a_{k+1}]$ and adding $a_k$ to each of these combinations can cover all intervals with $r \in [a_{k+1} - 2, S]$. We are done because it is easy to check that\[a_{k+1} \leq S - k \leq \frac{S + 2}{2}\]hence clearly $a_{k+1} - 2 \leq S - a_{k+1}$.

A unique solution: Let the weight of the blocks be $a_1 \leq a_2 \leq \cdots \leq a_n$. Note that $a_i \leq 2$ and $a_n \geq 2$. Further, let $S=\{a_1,a_2,\ldots,a_n\}$ denote the set of blocks, and for a subset $A$ of $S$ denote $W(A)$ as the weight of the blocks in $A$. We prove the following lemma first: Lemma: There does not exist a positive integer $1 \leq i \leq n$ such that $a_i > 2+\sum_{k=1}^{i-1} a_k$. Proof: Noting that for all $k$, $a_k \geq 1$, we see that it suffices to show that there does not exist $i$ such that $a_i > 2+(i-1) \implies a_i > i+1$. If such an $i$ exists, then the sum of all the weights is strictly greater than $(i-1)\cdot1+(n+1-i)\cdot(i+1)=n(i+1)+3i-i^2$. We can see that this is at least $2n$, since $n$ is a positive integer and $1 \leq i \leq n$ (the inequality reduces to $n(i-1)\geq i(i-3)$ after some straightforward computation, which holds if $i,n$ satisfy the given constraints). Therefore, if such an $i$ exists, then the sum of all of the weights must be strictly greater than $2n$, which is a contradiction. Therefore such an $i$ does not exist, as desired. $\blacksquare$ Call an interval empty if there does not exist a subset of the blocks whose total weight lies in the interval. Suppose for the sake of contradiction that an interval $[r,r+2]$ with $0 \leq r \leq 2n-2$ is empty. We claim this supposition implies that, for all $1 \leq k \leq n$, there are no subsets of $S \setminus \{a_1,a_2,\ldots,a_k\}$ which have a total weight in $[r-s(k),r+2]$ where $s(k)$ is defined as $\sum_{i=1}^k a_k$. We will prove this by induction on $k$. Our base case is $k=1$. We know that $[r,r+2]$ must be empty. Now consider any subset $A$ of $S \setminus \{a_1\}$. If $W(A) \in [r,r+2]$, then it follows that $[r,r+2]$ is not empty, so this cannot happen. Further, if $W(A) \in [r-a_1,r]$, then we have $W(A \cup a_1) \in [r,r+a_1]$. Since $a_1 \leq 2$, it follows that $[r,r+a_1] \subseteq [r,r+2]$, which would imply that $[r,r+2]$ is not empty, so this cannot happen either. Therefore any subset of $S \setminus \{a_1\}$ cannot fall in the interval $[r-a_1,r+2]$, which proves the base case. Now for the inductive step. Suppose there are no subsets of $S \setminus \{a_1,a_2,\ldots,a_{k-1}\}$ which have a total weight in $[r-s(k-1),r+2]$. Now consider any subset $A$ of $S \setminus \{a_1,a_2,\ldots,a_k\}$. If $W(A) \in [r-s(k-1),r+2]$, then we reach a contradiction, since $A$ is also a subset of $S \setminus \{a_1,a_2,\ldots,a_{k-1}\}$, yet has a total weight in $[r-s(k-1),r+2]$. If $W(A) \in [r-s(k-1)-a_k,r-s(k-1)]$, then we have $W(A \cup a_k) \in [r-s(k-1),r-s(k-1)+a_k]$. From our lemma, we know that $a_k-s(k-1) \leq 2$, so $[r-s(k-1),r-s(k-1)+a_k] \subseteq [r-s(k-1),r+2]$. But since $A \cup a_k$ is a subset of $S \setminus \{a_1,a_2,\ldots,a_{k-1}\}$, this is a contradiction as well. Therefore, there are no subsets of $S \setminus \{a_1,a_2,\ldots,a_k\}$ which have a total weight in $[r-s(k),r+2]$. This completes the inductive step, proving the claim. Using this claim, we see that taking $k=n$ shows that there are no subsets of $S \setminus \{a_1,a_2,\ldots,a_n\}=\emptyset$ which have a total weight in $[r-s(n),r+2]=[r-2n,r+2]$. But since $r \geq 0$ and $r \leq 2n$, $[r-2n,r+2]$ contains $0$. Therefore, the claim implies that $W(\emptyset)$ cannot be equal to $0$, which is absurd. Thus, our original supposition that an empty interval $[r,r+2]$ exists cannot be true. This implies the desired result. $\blacksquare$

Nice winduct exercise. We induct on $n$. The base case, $n=1$, is trivial. For the inductive hypothesis, assume that the statement is true for $n$ blocks. We will also prove it to hold for $n+1$ blocks. Let the weight of the largest block be $x$. It's easy to see from the problem statement that $2\le x\le n+1$, and hence the remaining set of $n$ blocks have sum $n+1\le S\le 2n$. We can scale these blocks up so that they sum to $2n$; the inductive hypothesis then tells us that these blocks can sum to $\left[r,r+\frac{S}{n}\right]$ for all $0\le r\le\frac{(n-1)S}{n}$, which is stronger than what we desire to prove. It remains to prove the hypothesis for all $r>S$ (for $\frac{(n-1)S}{n}\le r\le S$, just select all $n$ non-largest blocks). In this case, just include the largest block; since $r-x<S$, we can select the appropriate subset of other blocks.

FTSOC assume such an $r$ exists. Arrange the weights of the blocks (say $a_i$s)in ascending order (assume $a_i<a_{i+1}$). Say $S_k = a_1+ \cdots + a_k$. So FTSOC assume $S_k <r, S_{k+1} >r+2$ for some real $r$. Next consider $S_{k+1}-a_1$. If it is less than r we get $a_1>2$ and if it is more than r+2 we get $a_{k+1} > 3$. Continuing in a similar fashion we get that for the smallest $l$(If it exists) such that $S_{k+1}-S_{l-1} < r$ we have $a_{l-1}>2$ and $a_{k+1} > l$(Because of minimality of l). So the sum of all the blocks $2n> (l-2)+2(k-l+2)+l(n-k)$. Simplify to get $k+1>n$ which is ofc not possible. Now the second case is when such an l does not exist, that is $a_{k+1} > r+2$. We get $a_{k+1}>k+2$ in such a case. So we have the sum of the weights of all the blocks $=2n >(k+2)(n-k)+k$. Simplify to get $k>n-1$ which is absurd.

Not sure what I was on when writing up my previous solution. Anyway...

cmsgr8er wrote: Call the lightest block anorexic and the heaviest block american. what

We show that repeatedly placing the heaviest block that does not make the weight exceed $r+2$ will eventually work. Suppose otherwise. Thus, this operation must stop at a point when the blocks have total weight $<r$ but no blocks can be placed. First, notice that all blocks with weight $\le 2$ must have been placed, as otherwise for each of them we could place them and still fit (rearranging if necessary). Next, consider an unplaced block, which clearly must exist. It must have weight greater than $2$ plus the sum of the weights of blocks with weight $\le 2,$ as otherwise we could replace all blocks with weight $\le 2$ with the unplaced block (rearranging if necessary), since this block has weight $>2.$ Now suppose there are $k$ blocks with weight $\le 2.$ These $k$ have total weight $\ge k.$ Then there are $n-k$ blocks with weight $>2$ and total weight $\le 2n-k,$ so the maximal weight of a block is $<2n-k-2(n-k-1)=k+2,$ contradiction.

We consider any real number $r$ in the range $[0,2n-2]$. Now, we follow the following greedy algorithm. Algorithm : We look at the unpicked blocks and choose the block with maximum weight which has not yet been picked which does not make the sum of picked blocks exceed $r+2$. Proof : Now, for the sake of contradiction, we assume that this algorithm does not achieve the desired goal. Thus, if we picked blocks with weight $w_1,w_2,\dots, w_i$ then, \[w_1+w_2+\dots + w_i < r\]Note that then, all blocks of weight at most 2 must have been picked or else we can pick that block as well and not exceed $r+2$ which is a contradiction. We now look at the placed blocks of weight at most 2. Say we have $k$ of them with weights $v_1\leq v_2 \leq \dots \leq v_k \leq 2$. Then, the weight of the largest unpicked block $w \geq 2 \geq v_k$. If $w\leq v_k +2$ then, we can pick $w$ instead of $v_k$ and acheive a better bound, contradicting the greedy algorithm. Thus, $w> v_k +2 \geq v_k + v_{k-1}$. We continue likewise until we reach $w>v_1+\dots + v_k$. If $w \leq v_1+\dots + v_k+2$ we again contradict our greedy algorithm and thus, $w > v_1+\dots + v_k +2 \geq k+2$. Further, $w_1>w>k+2$ by the nature of our greedy algorithm. But then we notice that the sum of the blocks besides those with weight at most 2 is less than $n-k$ since every block has a weight of atleast 1. Thus, the weight of the largest block $B$ (among all picked and unpicked blocks) is, \[B < (n-k) - 2(n-k-1) = k+2\]since the blocks have weight atleast 2. Thus, the weight of the largest block $B<k+2$ which clearly contradicts the fact that $w,w_1>k+2$ which are respectively the largest picked and unpicked block. Thus, our greedy algorithm always works and there exists such a subset of blocks for every real number in the range $[0,2n-2]$.

Consider the process in which the empty set is considered, and in each step, the heaviest block that does not allow the sum of the weights of the block in the set exceed $r+2$ is appended to the set, until this step cannot be done. Assume for contradiction that the problem does not hold. Then the process terminates with the total weight of the set being less than $r$. Let the weights of the blocks that have been used in the process be $w_1, \dots, w_k$. The key claim is the following. Claim: All blocks that have not been used have weight greater than $r+2 > w_1+\dots+w_k+2$. Proof. Otherwise, such a block would have been used in the first step and the process would successfully terminate, with the total weight of the set in $[r, r+2]$. Since there are $n-k$ blocks that are unused, the total weight of all blocks is greater than \[ (w_1+\dots+w_k) + (n-k)(w_1+\dots+w_k+2) = (n-k+1)(w_1+\dots+w_k)+2(n-k). \]Thus \[ w_1+\dots+w_k < \frac{2k}{n-k+1} \le \frac{2k}{2} = k, \]a contradiction since all blocks have weight at least $1$. Remark: [motivation] The process defined is motivated by the local idea of Repeating Until Stuck (RUST). The main nontrivial step used is the key claim; when using RUST, it is important to understand when an element of the universal set is a candidate for the constructed set, and moreover what happens after a candidate is accepted and another candidate is rejected. This is often useful in local problems. (The main claim in 2023 AIME I #14 is a good example of this.)

Label the weights $w_1$ to $w_n$ in increasing order. Take any real $r \in [0, 2n-2]$. Now we construct a set $S$ such that $W(S) \in [r,r+2]$ (where $W(S)$ is the weight of set $S$). We start by repeatedly taking the largest weight $w$ such that $W(S)+w \le r+2$. Once we get stuck, there are two possibilities. Case 1: We have that $r \le W(S)$. In this case, we are clearly done as the set $S$ works. Case 2: We have that $r>W(S)$. Take the minimal $w_{\ell}$ that isn't in $S$. Since we are taking the maximal $w$ each step, we must have \[\sum_{w \in S,\text{ }w>w_{\ell}} w+w_{\ell} > r+2\]If it was less than or equal to, then we would've chosen $w_{\ell}$ contradicting the definition of $w_{\ell}$. Furthermore, since $w_{\ell}$ is minimal, we have \[\sum_{w \in S,\text{ }w>w_{\ell}} w+\sum_{i = 1}^{\ell-1} w_i < r\]These two imply that \[w_{\ell} > \sum_{i = 1}^{\ell-1}w_i+2 \implies w_{\ell} > \ell+1\]as $w \ge 1$ for all weights. Now using the fact that the max weight is $2n$, we have \[2n \ge \ell-1+w_{\ell} \cdot (n-\ell+1) > \ell-1+(\ell+1)\cdot (n-\ell+1)\]For $n > 1$, this implies that $\ell > n$, a clear contradiction since we only have $n$ blocks, and the $n = 1$ case is trivial. Therefore, the only Case that can exist is Case 1, implying this construction works.

Let the sum of the blocks be $S$ and solve generally for $S \leq 2n$. Let our blocks be $b_1 \leq b_2 \leq \dots \leq b_n$. If all $b_i$ are equal then the claim is obviously true, so we WLOG assume that not all $b_i$ are equal. We can do induction by removing the largest element of $b_i$ to show that all possible values of $r$ work. Our base case of $n = 1$ is obviously true. Then removing the largest element $b_n$ gives us that there is a sequence $g_i$ satisfying $r \in [0, S - b_n - 2]$ by induction. Adding in $b_n$ gives us that $r \in [b_n, S - 2]$ works. All we need to show that is $2n - b_n - 2 \geq S - b_n - 2 \geq b_n \implies n - 1 \geq b_n$ which would imply that $r \in [0, S]$ works. Notice that all $b_i \geq 1$ so then $b_n \leq S - n + 1 \leq n + 1$ which is true, so we are done.

We can induct. Say we have $n$ blocks, total weight $A \leq 2n$. We would like to show that for any $r$ in $[0, A-2]$, the problem statement holds. If $n=1$, then this is trivial. Then, consider the inductive step. Consider the biggest block, and say it has weight $k > 2$ (if $k=2$, then greedy works). Then, if $k$ is in $[r, r+2]$, then we are done. If $k < r+2$, then the problem is reduced to $n-1$ blocks, total weight $A-k$, and ``target'' range $[r-k, r-k+2]$, which is done by the inductive hypothesis. If $k > r+2$, then we reduce the problem to having $n-1$ blocks, total weight $A-k$, and our ``target'' range is still $[r, r+2]$. If $r \leq A-k-2$ then we are again done by the inductive hypothesis. Then, assume that $r > A-k-2$. In that case, this implies that $k > \frac{A}{2}$, which then implies that the rest of the blocks must have weights in $[1, 2]$. Then greedy algorithm finishes.

We will prove a stronger result, namely that if we have $n$ blocks each weighing at least $1$ and with a total weight of $S \le 2n$, then for all $r \in [0, S]$ it is possible to choose a subset of blocks whose total weight lies in the interval $[r, r+2]$. We proceed with induction on $n$, with the base case of $n = 1$ being trivial. Assuming the claim is true for $n$, we will show that it also holds for $n+1$. Let $A = \{b_1, b_2, \ldots, b_k\}$ denote the set of blocks with weight at most $2$ and let $w_i$ denote the weight of $b_i$ for $1 \le i \le k$. In addition, define $S_i = \sum_{t = 1}^{i} w_t$ for $1 \le i \le k$ and let $b_{n+1}$ denote the heaviest block with weight $w_{n+1}$. Notice that $$S - w_{n+1} \le S - \frac{S}{n+1} = S \cdot \frac{n}{n+1} \le (2n+2) \cdot \frac{n}{n+1} = 2n$$so the claim holds for the $n$ blocks other than $b_{n+1}$, meaning the desired condition is achievable for all $r \in [0, S - w_{n+1}]$. Now, consider the subsets of blocks with total weights $$S, S - S_1, S - S_2, \ldots, S - S_k.$$Because $$(S - S_i) - (S - S_{i+1}) = w_{i+1} \le 2$$for $1 \le i \le k-1$, we know all $r \in [S - S_{i+1}, S - S_i]$ can be achieved via the subset with total weight $S - S_i$ for $i \in [1, k-1].$ Using identical reasoning, it also follows that all $r \in [S - S_1, S]$ can be achieved using the subset of all $n+1$ blocks and all $r \in [S - S_k - 2, S - S_k]$ can be achieved via the subset with total weight $S - S_k$. Thus, we have shown all $$r \in [0, S - w_{n+1}] \cup [S - S_k - 2, S]$$can be achieved. FTSOC, suppose $S - w_{n+1} < S - S_k - 2$ or equivalently $w_{n+1} > S_k + 2$. Then, $$2n+2 \ge S \ge S_k + w_{n+1} + 2((n+1) - (k+1))$$$$> 2S_k + 2 + 2(n-k) \ge 2k + 2(n - k + 1) \ge 2n+2$$which is absurd. Thus, $S - w_{n+1} \ge S - S_k - 2$ must hold, implying $[0, S - w_{n+1}] \cup [S - S_k - 2, S]$ fully contains $[0, S]$. $\blacksquare$ Remarks: The inequality $S \ge S_k + w_{n+1} + 2((n+1) - (k+1))$ is not strict because $n = k$ is possible. Although this ends up being useless, the claim can be extended to $r \in [-2, S].$

Sort blocks in sizes $a_1\ge \dots\ge a_n$. If the condition fails, then there exists an index $i$ where \[s=a_1+\dots+a_i<r\]\[s+a_j=a_1+\dots+a_i+a_j>r+2\]for any $j>i$. As a result $s+a_n>r+2>s+2\implies a_n>2$ which is a contradiction. $\blacksquare$ wait this is wrong

aha Let the weights be $1\le a_1\le \dots\le a_n$. Add in weights one by one in increasing order; we prove that the following holds. Claim: Given weights $a_1,\dots,a_i$ with $S=a_1+\dots+a_i\ge i$, we can choose a subset of blocks with weight in $[r,r+2]$ for any $0\le r\le S-2$. Proof: Use induction; with $i=1$ we are done. Otherwise we can only fail if $a_{i+1}>S+2$ which would imply \[a_1+\dots+a_i+a_{i+1}>2S+2\ge 2i+2\]which implies the average of these weights is more than $2$, a contradiction (since the average of the first $i$ weights is nondecreasing). $\blacksquare$

Let $b_1,b_2, \dots b_n$ denote the weights and assume WLOG that $b_1 \leq b_2 \leq \dots \leq b_n$. Now construct the following greedy algorithm: Add the minimum term to our previous sum, do that until the first time the sum $b_1+b_2+\dots +b_k > r$. If the sum $b_1+b_2+\dots +b_k$ is more than $r+2$, then look at $b_k$, if $b_k \leq r+2$, then just take $b_k$. If $b_k > r+2$, then we have that. $$b_k>r+2>b_1+b_2+ \dots +b_{k-1}+2 \geq (k-1)+2=k+1$$. Now looking at the sum of all elements to get a contradiction. \begin{align*} 2n & = b_1+b_2+ \dots +b_n\\ & = (b_1+b_2+ \dots+b_{k-1})+(b_k+b_{k+1}+\dots +b_m) \\ & \geq (k-1)+(n-k+1)b_k\\ & > (k-1)+(n-k+1)(k+1) \\ & = kn-k^2+2k\\ \end{align*} The maximum $kn-k^2+2k$ gets is when $n=k$, hence equal to $2n$. which is a contradiction, hence we are done!

Let the blocks be $a_1 \le a_2 \le \dots \le a_n$. We will prove the following holds, which will solve the problem: Given $a_1, a_2, \dots, a_i$ such that $S = a_1+a_2+\dots + a_i$, we can choose a subset of the blocks whose total weight is between $r$ and $r+2$, inclusive, for $0 \le r \le S-2$. We proceed by induction; the base case $i=1$ obviously works. Now, suppose that the inductive hypothesis holds for $i$ blocks. Since we currently cover $[0,S]$, adding $a_{i+1}$ would allow us to cover $[a_{i+1},S+a_{i+1}]$. Thus, the only way for adding a block to be invalid is if $a_{i+1}>S+2$. However \[a_1+a_2+\dots+a_{i+1} > S + (S+2) = 2S+2 > 2i+2,\] which implies the average of the blocks is greater than $2$, a contradiction. Hence, the induction is complete. $\blacksquare$

quite tricky

it sort of came out of first splitting $s$ and $\ell$ by whether they were less or greater than $2$ (hence small and large) then i realized that splitting by which side of $2$ the numbers were on was actually sort of arbitrary so then stuff worked. Assume (for contradiction, as if this condition is false we will prove the problem is solved) the numbers are $s_1\le \dots\le s_x\le \ell_1\le \dots\le \ell_y$, where the following property holds: $\ell_1>S+2$, where $S:=s_1+\dots+s_x$. Here $x,y\le 1$. Then we obtain \[2n>(S+2)y+S\implies 2n-2y>S(y+1)\implies 2x>S(y+1)\ge x(y+1)\implies 1>y,\]a contradiction. Here we have used $S\ge x$, as $s_1,\dots,s_x\ge 1$. Hence the following algorithm is guaranteed to run to completion: Order numbers $a_1\le \dots\le a_n$, and begin with the guaranteed-good (referring to real numbers $r$ in the question statement) interval $[0,a_1]$. Additionally write $S_1:=a_1$. At any moment with good interval $[0,S_i]$, we can "merge" this interval with the next interval $[a_{i+1},S_i+a_{i+1}]$, which is guaranteed to work as $a_{i+1}>S_i+2$ never holds. This yields the new interval $[0,S_{i+1}]$, so we have essentially "inducted upwards." Hence eventually the good interval reaches $[0,S_n]$ or simply $[0,2n]$, and we are done. $\blacksquare$

asdf334 wrote: aha Let the weights be $1\le a_1\le \dots\le a_n$. Add in weights one by one in increasing order; we prove that the following holds. Claim: Given weights $a_1,\dots,a_i$ with $S=a_1+\dots+a_i\ge i$, we can choose a subset of blocks with weight in $[r,r+2]$ for any $0\le r\le S-2$. Proof: Use induction; with $i=1$ we are done. Otherwise we can only fail if $a_{i+1}>S+2$ which would imply \[a_1+\dots+a_i+a_{i+1}>2S+2\ge 2i+2\]which implies the average of these weights is more than $2$, a contradiction (since the average of the first $i$ weights is nondecreasing). $\blacksquare$ You mean $a_{i+1}>S-2$