Proving surjectivity of some map from a power set to a subset of integers.

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?

Solution 1:

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.

Solution 2:

Here's a direct solution (which I believe gets to the heart of the problem). (Sorry, I just noticed that OP requested a solution based on graph theory in the bounty. I ignored that.)

In $ \{ a_i \}$, let there be $k$ 1's, and let $a_n$ be the largest value.

Claim 1: $k \geq a_n$.

If $ k = n-1$, then $a_n = (2n-2) - (n-1) = n-1$ so $k \geq a_n$ as desired.
If $ k < n-1$, then $ 2n-2 = \sum a_i \geq k + 2 (n-k-1) + a_n \Rightarrow k \geq a_n$ as desired.

Claim 2: For any $ 1 \leq i \leq 2n-1 $, we can find a subset of $\{a_i\}$ that sums to these values.

If $ i \leq 2n-2 - k $, then ignore the $k$ values of 1 for now. Take the largest possible subset that gives a sum $ \leq i $. Note that the difference between $i$ and this sum is strictly less than any non-1 element, hence strictly less than $k$ from claim 1. As such, we can use additional 1's to get the sum to $i$.
If $i > 2n-2 - k$, then take all the non-1 values, and enough 1 values.

Bonus: Prove that the statement still holds true if $\sum a_i = 2n-1$. Use the same argument (modifying the first claim to $ k \geq a_n - 1$. The second claim is fine as is).

Bonus: Prove that the statement still holds true if $\sum a_i \in [n+1, 2n-1]$ using a similar argument.

Solution 3:

Assume that $\{a_i\}$ contains $k$ copies of $1$. Assume in addition to this that $a$ is the second lowest number occurring somewhere in the sequence. Then we have: $$ k+a(n-k)\leq a_1+...+a_n=2n-2 $$ which can be rearranged to see that: $$ k\geq\frac{(a-2)n+2}{a-1}> a-2 $$ The last inequality stems from the fact that $a\leq n-1$. Hence the sequence contains at least $a-1$ copies of $1$.

Finally, note that if we remove $a$ and $a-2$ copies of $1$ from the sequence we have removed $a-1$ terms and reduced the sum by $2(a-1)$: $$ a+(a-2)\cdot 1=2(a-1) $$ Hence we can use induction and we are done.

Regarding the induction

We have the base case $n=2,a_1=a_2=1$ which is easily checked. Note that $n=1$ is impossible.

Now assume we have shown all cases $n<m$. Consider $n=m$.

To construct the higher numbers, simply consider the total of $2m-2$ and subtract subset sums: $$ 0,1,...,2a-1 $$ by removing subsets of $a$ and the $a-1$ copies of $1$. This gets us as far down as: $$ 2m-2-(2a-1)=2(m-a)-1 $$

To account for the lower numbers, remove $a-1$ terms that sum to $2(a-1)$ by using the arguments above. Note that for $m>2$ we have $a\geq 2$. Then we are left with $m-(a-1)$ terms that satisfy: $$ \begin{align} \sum a_i &=2m-2-2(a-1)\\ &=2\left\{m-(a-1)\right\}-2 \end{align} $$ which is one of the cases covered by the induction hypothesis. Note that $2\leq m-(a-1)<m$ because $2\leq a\leq m-1$ so induction holds. Thus we have also covered the sums from $1$ up to: $$ 2\left\{m-(a-1)\right\}-2=2(m-a) $$ and so all sums from $1$ through $2m-2$ have been accounted for.