Weighted Blocks

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ilovemath04

70 posts

ilovemath04

#1 h Sep 22, 2020, 11:48 PM • 4 Y

Y by centslordm, varunkute, samrocksnature, aidan0626

You are given a set of $n$ blocks, each weighing at least $1$ ; their total weight is $2n$ . Prove that for every real number $r$ with $0 \leq r \leq 2n-2$ you can choose a subset of the blocks whose total weight is at least $r$ but at most $r + 2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#2 h Sep 22, 2020, 11:49 PM • 5 Y

Y by SNAilFrOlIc, centslordm, DongerLi, sabkx, bhan2025

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ainulindale

32 posts

Ainulindale

#3 h Sep 23, 2020, 12:02 AM • 5 Y

Y by SNAilFrOlIc, centslordm, yee5487, GuvercinciHoca, sabkx

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.

This post has been edited 3 times. Last edited by Ainulindale, Sep 23, 2020, 12:35 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cefer

294 posts

cefer

#4 h Sep 23, 2020, 12:58 AM • 1 Y

Y by centslordm

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MarkBcc168

1595 posts

MarkBcc168

#5 h Sep 23, 2020, 1:39 AM • 14 Y

Y by Gaussian_cyber, k12byda5h, SNAilFrOlIc, mijail, hakN, centslordm, Kobayashi, Jalil_Huseynov, Mango247, Mango247, Mango247, BorivojeGuzic123, iamnotgentle, ike.chen

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.

This post has been edited 2 times. Last edited by MarkBcc168, Sep 23, 2020, 1:40 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Eyed

1065 posts

Eyed

#6 h Sep 23, 2020, 1:39 AM • 4 Y

Y by centslordm, Mango247, Mango247, Mango247

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ACGNmath

327 posts

ACGNmath

#7 h Sep 23, 2020, 1:50 PM • 4 Y

Y by SNAilFrOlIc, centslordm, Mango247, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Anzoteh

126 posts

Anzoteh

#8 h Sep 24, 2020, 1:23 AM • 2 Y

Y by centslordm, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kvs

620 posts

kvs

#9 h Sep 24, 2020, 9:41 PM • 5 Y

Y by centslordm, XbenX, Mango247, Mango247, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mela_20-15

125 posts

mela_20-15

#10 h Sep 26, 2020, 8:57 PM • 1 Y

Y by centslordm

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)]$ .
We have that $w_n\le a +w_1+w_2+...+w_{n-1}=a+a'(n-1)$ Click to reveal hidden text
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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

fukano_2

492 posts

fukano_2

#12 h Sep 27, 2020, 1:12 PM • 1 Y

Y by centslordm

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VulcanForge

626 posts

VulcanForge

#13 h Oct 5, 2020, 2:48 AM • 2 Y

Y by centslordm, de-Kirschbaum

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Vitriol

113 posts

Vitriol

#15 h Oct 7, 2020, 1:19 AM • 2 Y

Y by centslordm, ike.chen

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jj_ca888

2726 posts

jj_ca888

#16 h Oct 15, 2020, 5:36 PM • 2 Y

Y by Vitriol, centslordm

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}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5005 posts

IAmTheHazard

#17 h Jan 1, 2021, 9:01 PM • 2 Y

Y by centslordm, sabkx

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$

This post has been edited 1 time. Last edited by IAmTheHazard, Jan 1, 2021, 9:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Leo.Euler

577 posts

Leo.Euler

#43 h Feb 6, 2024, 5:11 PM

Y by

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]$ .
:yoda:

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.)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

naonaoaz

334 posts

naonaoaz

#44 h Feb 25, 2024, 6:00 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dolphinday

1329 posts

dolphinday

#45 h Feb 26, 2024, 7:41 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alsk

28 posts

alsk

#46 h Mar 9, 2024, 9:49 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ike.chen

1162 posts

ike.chen

#47 h Mar 28, 2024, 6:11 PM

Y by

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].$

This post has been edited 10 times. Last edited by ike.chen, Mar 28, 2024, 8:19 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7585 posts

asdf334

#48 h Apr 25, 2024, 10:42 PM

Y by

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

This post has been edited 1 time. Last edited by asdf334, Apr 25, 2024, 10:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7585 posts

asdf334

#49 h Apr 27, 2024, 9:03 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ywgh1

139 posts

Ywgh1

#50 h Sep 4, 2024, 7:34 PM

Y by

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!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2534 posts

joshualiu315

#51 h Sep 30, 2024, 5:20 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

onyqz

195 posts

onyqz

#52 h Nov 2, 2024, 1:10 AM

Y by

quite tricky
solution

Note to myself for memorization

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7585 posts

asdf334

#53 h Dec 22, 2024, 8:30 PM • 1 Y

Y by OronSH

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

qwertyuiop123456789

6 posts

qwertyuiop123456789

#54 h Jan 3, 2025, 9:51 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

NTguy

23 posts

NTguy

#55 h Feb 12, 2025, 10:51 AM • 1 Y

Y by alexanderhamilton124

The statement is equivalent to showing that in any $2$ consecutive integers, we can form one of them using the given blocks. Notice that the average weight of a block is $2$ . So, if there exist any blocks with weight $k>2$ , we need to have exactly $k-2$ blocks of weight $1$ to get the average back to $2$ . Having a block of $2$ does not affect the average in any way. So, if we have $k$ blocks with weights $w_1, w_2, ..., w_k (w_i>2)$ , then we have exactly $w_1+w_2+...+w_k - 2k$ blocks of weight $1$ .
There are $2$ cases -
Case $1$ - There is no block with weight $2$ .
Now, if the blocks with weight $>2$ have weights $w_1, ..., w_k$ , then we can split them into groups such that each group has weight $2(w_i - 1)$ , by taking the block with weight $w_i$ and the corresponding $w_i - 2$ blocks of weight $1$ . Then, it is trivial to prove that in each of these groups, a subset can be chosen such that it forms all weights from $1$ to $2w_i-2$ except for $w_i-1$ . Taking sums of different groups of subsets, we can ensure that in every pair of consecutive integers, one of them can be made. In particular, we can make $2(w_1+w_2+...+w_k - k)$ .

Case $2$ - There exist $m$ blocks with weight $2$ .
Notice that by taking away these $m$ blocks, we get Case $1$ . So, we can ensure that for all $r$ such that $0 \leq r \leq 2(n-m)$ , we can get a subset of blocks with total weight in the range $[r, r+2]$ without using a single block of weight $2$ . So, we can make subsets with weight $2(n-m)$ and $2(n-m)-1$ . Now, using blocks of weight $2$ along with these subsets, we can form every integer greater than $2(n-m)$ , so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

575 posts

Maximilian113

#56 h Apr 30, 2025, 5:48 PM

Y by

We claim that the statement holds when the sum is between $2n-2, 2n.$ We proceed by induction on $n.$ The base case, $n=1,$ is trivial, so assume that the proposition holds for $n$ and everything below. For $n+1,$ if every block has weight at most $2,$ greedily adding blocks works as we never "skip" over an interval of the form $[k, k+2]$ for integers $k.$ So the proposition holds for any real $r.$

However, if there is a block $B$ with weight more than $2,$ taking away this big weight we are left with the inductive hypothesis for $\lceil n-k/2 \rceil \geq \lceil n/2-1/2 \rceil$ as $B$ s weight is at most $n+1.$ For the numbers above we can take $B$ plus the other weights and apply the inductive hypothesis. QED

This post has been edited 1 time. Last edited by Maximilian113, Apr 30, 2025, 5:49 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ND_

56 posts

ND_

#57 h May 1, 2025, 11:36 AM

Y by

We keep taking the highest weight available, if taking it does not take the weight above $r + 2$ . Let the last block taken have weight $m$ and let the number of blocks taken be $k$ , $t$ the weight needed more. Let $s$ be the number of light blocks, blocks weighing less than 2. Then,
$\frac{m \cdot k + 1 \cdot s}{k+s} \leq 2 \Rightarrow m \leq 2 + \frac{s}{k}$ .

If $k > 1$ and $s>2$ , $t \leq m \leq 2+\frac{s}{k} \leq s \leq \text{Weight of the light blocks}$
If $k=1$ , each other block weighs less than $m$ and we have at least $m-2$ light blocks, from where it is trivial.
If $s=1$ , maximum weight is less than $2+ \frac{1}{n-1}$ . $s=2$ is similar

So, we can get the remaining $t$ weight using the $s$ light blocks, through which we won't skip $[r, r+2]$ .

This post has been edited 1 time. Last edited by ND_, May 1, 2025, 1:29 PM

Z K Y