We assign to every element $i$ from $N=\{1,2,…,n\}$ a positive integer $a_i$. Suppose $$a_1+a_2+…+a_n = 2n-2$$ then prove that map $T: \mathcal{P}(N) \to \{1,2,…,2n-2\}$ defined with $$T(X) = \sum _{i\in X}a_i$$ is surjective.
We can assume that $a_1\leq a_2\leq …\leq a_n$.
Clearly, $a_1 = a_2 = 1$ and thus $1,2,2n-3,2n-4$ are in a range.
Also, if $a_i=2$ for some $i$ then we could easily apply induction.
Say $b_1< b_2<…<b_k$ are all different values that appear among $a_i$.
Then we have $n _1\cdot b_1+n_2\cdot b_2+…+n_k \cdot b_k = 2n-2$ and $n_1+n_2+..+n_k = n$. We have to prove that for each $l\leq 2n-2$ we have $$n' _1\cdot b_1+n'_2\cdot b_2+…+n'_k \cdot b_k = l$$
for some $n'_i\leq n_i$. And here it stops. I have no idea how to find all those $n_i'$. Any ideas?
Best Answer
All the answers are basically saying the same thing, so I will simply try to say it in the most "graph-theoretic" way. :)
Construct an $n$-node tree $G$ with the node degrees being $a_1, a_2, ..., a_n$. [This can be done, e.g. by starting with the highest numbers and keep combining them.] Initially every node is colored black.
We will be coloring some nodes red, and the red nodes will represent $X \in \mathcal{P}(N)$. Thus $T(X) = $ sum of node degrees of the red nodes.
Initially, every node is black, i.e. $X = \emptyset, T(X) = 0$. We now increment $T(X)$ one by one.
If some leaf is black, color it red. This increments $T(X)$ by $1$.
If all leaves are red, pick any black internal node $v \in G$. Suppose its degree is $a > 1$. Since $G$ is a tree, $G - \{v\}$ is a new graph which is a collection of $a$ separate trees (including possibly singleton nodes). Each of these $a$ smaller trees has at least one leaf belonging to the original $G$. Thus the original $G$ has at least $a$ leaves (which are, by assumption, all red). Now, change $v$ from black to red, and change any $a-1$ leaves from red back to black. This increments $T(X)$ by $1$.
We can keep doing this until all nodes are red, at which point $T(X) = 2n-2$. Thus $T()$ goes through $\{0, 1, 2, ..., 2n-2\}$, proving it is surjective.