Let $n$ be a natural number and suppose that $ w_1, w_2, \ldots , w_n$ are $n$ weights . We call the set of $\{ w_1, w_2, \ldots , w_n\}$ to be a Perfect Set if we can achieve all of the $1,2, \ldots, W$ weights with sums of $ w_1, w_2, \ldots , w_n$, where $W=\sum_{i=1}^n w_i $. Prove that if we delete the maximum weight of a Perfect Set, the other weights make again a Perfect Set.
Problem
Source: Iran second round- 2013- P2
Tags: induction, combinatorics proposed, combinatorics
06.05.2013 14:56
Assume $w_1 \leq w_2 \leq \ldots \leq w_n$. It is easily observed that the weights $(w_j)_{j=1}^n$ satisfy : (i) $w_1=1$ (ii) $w_k \leq \sum_{j=1}^{k-1} w_j +1 \,,\, k=2,3,\ldots ,n$ Now by a straightforward induction one can prove that if $(w_j)_{j=1}^{n}$ satisfy (i) and (ii) then for $\forall j\,,\, 1\leq j\leq n $ the set $\{w_1,w_2,\ldots,w_j\}$ is a perfect set.
07.04.2016 19:46
Say that finite list $A$ generates set $B$ if $\forall b\in B$ there is a sublist of $A$ whose sum equals $b$, and say that $A$ is awesome if it generates the set $\{1,2,\dots,\max A\}$. First, note that if $A=\{a_1\le a_2\le \dots\le a_n\}$ is awesome, then so is $A_k=\{a_1,a_2,\dots,a_k\}$ for any $k\le n$. Indeed, when we write the elements of $\{1,2,\dots,a_k\}$ as the sums of members of $A$, all of the summands are $\le a_k$. Secondly, notice that if $A$ is awesome, it is also a Perfect Set. Indeed, suppose $A=\{a_1\le a_2\le \dots\le a_n\}$ generates $\{1,2,\dots,a_n\}$. Now for any $x$ with $a_n<x\le a_1+a_2+\dots+a_n$, note that there must be a $k\in\{1,2,\dots,n-1\}$ for which \[y:=a_{k+1}+\dots+a_n<x\le a_k+a_{k+1}+\dots+a_n. \]Now since $z:=x-y\le a_k$ and $\{a_1,a_2,\dots,a_k\}$ generates $\{1,2,\dots,a_k\}$, we can write $z$ as the sum of a sublist of $a_1,\dots,a_k$ and so $x=y+z$ is the sum of a sublist of $a_1,\dots,a_k,a_{k+1},\dots,a_n$. This shows that $A$ generates not only $\{1,2,\dots,a_n\}$, but the whole of $\{1,2,\dots,a_1+a_2+\dots+a_n\}$ as well, and so is a Perfect Set. Therefore, given a Perfect Set $A$, it suffices to see that $A$ is awesome to show that $A'=A\setminus\{\max A\}$ is also awesome and hence a Perfect Set.
22.02.2022 18:16
The key claim is the following characterization of all perfect sets: Claim: $S=\{w_1,\ldots,w_n\}$ with $w_1\leq \cdots \leq w_n$ is a perfect set if and only if we have $w_1=1$ and $w_k\leq 1+\sum_{i=1}^{k-1} w_i$ for all $k \geq 2$. Proof: The conditions are clearly necessary, since if we have some $k$ with $w_k>1+\sum_{i=1}^{k-1} w_i$, then any set containing $w_j$ for $j \geq k$ is at least $2+\sum_{i=1}^{k-1} w_i$, and any set not containing any such $w_j$ is at most $\sum_{i=1}^{k-1} w_i$, so there is no subset of $S$ with sum $1+\sum_{i=1}^{k-1} w_i$, hence $S$ is not perfect. To show that the conditions are sufficient, we use induction, with the base case of $n=1$ being clear. Then, if $\{w_1,\ldots,w_k\}$ is perfect, we have for all $w_{k+1} \leq 1+\sum_{i=1}^{k-1} w_i$: $$\{1,2,\ldots,w_1+\cdots+w_k\} \cup \{w_{k+1},w_{k+1}+1,\ldots,w_1+\cdots+w_{k+1}\}=\{1,\ldots,w_1+\cdots+w_{k+1}\},$$hence $\{w_1,\ldots,w_{k+1}\}$ is perfect as well. $\blacksquare$ Now the rest is easy, as by the above claim if $\{w_1,\ldots,w_n\}$ is perfect then $\{w_1,\ldots,w_{n-1}\}$ must be as well.
17.07.2023 02:12
Very silly problem. WLOG assume that $w_1 < w_2 < \dots < w_n$. Claim: $\{w_1, w_2, \dots w_k\}$ is perfect for all $k$. Proof. Take the base case of $k = 1$. Now suppose that $\{w_1, w_2, \dots w_k\}$ is perfect. If $w_{k+1} \le w_1 + w_2 + \dots + w_k + 1$, then it follows that $\{w_1, w_2, \dots w_k, w_{k+1}\}$ is a perfect set. Else, $\{w_1, w_2, \dots w_k, w_{k+1}\}$ does not contain $w_1 + w_2 + \dots + w_k + 1 < w_{k+1}$ and since $w_{k+1} < w_{k+2} < \dots$ it follows that $\{w_1, w_2, \dots w_{n-1}, w_n\}$ does not contain it, contradiction. $\blacksquare$ Taking each $k$ gives the result.
29.08.2023 02:28
Feels like a very rigid-y problem. It dies once you notice the following: Claim. The set $\{w_1, w_2, \dots, w_n\}$ is perfect if and only if $w_1 = 1$ and $w_k \leq 1 + w_1+ w_2+\cdots + w_{k-1}$ for all indices $k$. Proof. The conditions are obviously necessary; otherwise, there aren't enough subsets to cover the sums between $w_1+w_2+\cdots+w_{n-1} + 1$ and $w_1+w_2+\cdots+w_n$. To prove sufficiency, we can argue inductively, noticing that if the set $\{w_1, w_2, \dots, w_{n-1}\}$ produces $w_1+w_2+\cdots+w_{n-1}$ distinct sums, shifting those sums by $w_n$ produces $w_1+w_2+\cdots+w_{n-1}$ distinct sums in the range $[w_n+1, w_1+w_2+\cdots+w_n]$. By Pigeonhole this obviously must cover all possible sums in that range. $\blacksquare$ On the other hand, this works in the reverse direction: if $\{w_1, w_2, \dots, w_n\}$ is perfect then so is $\{w_1, w_2, \dots, w_{n-1}\}$. Thus all partial sum sets are perfect, as needed.
13.02.2024 17:58
First, we have the following claim. Claim: The set $\{w_1, \dots, w_n\}$ (with terms in increasing order) is perfect if and only if $w_1=1$ and $w_k \le w_1+\dots+w_{k-1}+1$ for each index $k$. Proof. If $w_k \ge w_1+\dots+w_{k-1}+2$ for some $k$, then the number $w_1+\dots+w_k+1$ cannot be written as the sum of elements of a subset of $\{w_1, \dots, w_n\}$, so $\{w_1, \dots, w_n\}$ is not perfect in this case. On the other hand, suppose that $w_1=1$ and $w_k \le w_1+\dots+w_{k-1}+1$ for every $k$. We claim that $\{w_1, \dots, w_n\}$ is perfect, and prove this by induction on $n$ with base case $n=1$ easy. For the inductive step, observe that subsets of $\{w_1, \dots, w_{n-1}\}$ cover sums from $1$ to $w_1+\dots+w_{n-1}$, so the sums covered by subsets of $\{w_1, \dots, w_n\}$ containing $w_n$ are those between $w_n$ and $w_1+\dots+w_n$, inclusive. Since $w_n \le w_1+\dots+w_{n-1}+1$, no integer between $1$ and $w_1+\dots+w_n$, inclusive, is missed by the sums, which completes the induction. $\square$ By the claim, it follows that $\{w_1, \dots, w_k\}$ is perfect for each $1 \le k \le n-1$, so $\{w_1, \dots, w_n\}$ has at least $n-1$ nonempty proper perfect subsets, as desired.
25.12.2024 23:26
It suffices to show that the $k$ least elements of a perfect set, for $1 \leq k \leq n-1$, also form a perfect set. This is clear for $k=1$, and if we add $w_k$ to $\{w_1, w_2, \ldots, w_{k-1}\}$, notice \[\underbrace{\{1,\ldots,w_1+\cdots+w_{k-1}\}}_{\text{Sums of } k-1 \text{ set}} \cup \underbrace{\{w_k+1,\ldots,w_1+\cdots+w_k\}}_{w_k + \text{ Sums of } k-1 \text{ set}}\] comprises all elements $\{1,\ldots,w_1+\cdots+w_k\}$; otherwise our original set $\{w_1, \ldots, w_n\}$ would not be perfect. $\blacksquare$