20
$\begingroup$

We assign 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?

$\endgroup$
  • $\begingroup$ I am just curious. Is this problem is somehow related to Graph theory? $\endgroup$ – Sujit Bhattacharyya Apr 8 at 9:32
  • 1
    $\begingroup$ Yes, this can be understood as a graph with $n$ vertices and the degrees $a_1,a_2,...,a_n$. So this graph has $n-1$ edges which means it is a tree. It is also well know that tree has at least 2 vertices of the degree 1.@SujitBhattacharyya $\endgroup$ – Aqua Apr 8 at 16:04
5
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's a very nice write up the graph-theoretic approach! Do you see a nice way to extend it to a sum of $2n-1$? $\endgroup$ – Calvin Lin Apr 12 at 15:40
  • 1
    $\begingroup$ @CalvinLin - sure. Just add one more $1$, i.e. an extra leaf, call it $L$, and make sure it never turns red. So Case 1 reads "if some non-$L$ leaf is black..." and, in Case 2, when you turn $v$ red, one of the subtrees must contain $L$, and the other $a-1$ subtrees provide the $a-1$ leaves you need to turn black, without having to touch $L$. So using only non-$L$ nodes (i.e. the original nodes) you can traverse $0, 1, ... 2n-1$. $\endgroup$ – antkam Apr 12 at 17:14
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is a cleaner version of my strategy. Very nice! $\endgroup$ – String Apr 12 at 9:20
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why $a \leq n-1$ ? $\endgroup$ – darij grinberg Apr 8 at 12:14
  • $\begingroup$ @darijgrinberg: Assume for contradiction that we have some $a_i\geq n$. Then the other $n-1$ terms must sum to at most $n-2$ which is impossible since they are at least $1$. $\endgroup$ – String Apr 8 at 12:15
  • $\begingroup$ Ah, thanks. How do you use induction at the end of the proof? $\endgroup$ – darij grinberg Apr 8 at 12:20
  • $\begingroup$ @darijgrinberg: I have added details regarding that. It seems a bit messy so any simplifications are welcome. I hope this helps! $\endgroup$ – String Apr 8 at 13:06
  • 1
    $\begingroup$ Aaah! Now I understand it! I wasn't aware that your arguments for lower and higher numbers are separate (I thought you were building "base" and "socle" at the same time, because that's what I had tried to do myself). Your proof looks nice and correct now. $\endgroup$ – darij grinberg Apr 8 at 21:24
1
$\begingroup$

Here's a solution based on graph theory. The idea is to remove a "leaf" from the tree and proceed by induction.

Assuming $A_n = \{a_1, \dots, a_n\}$, $a_1 = 1$ and $a_2 > 1$, consider the set $A_{n-1} = \{a_2-1, a_3, \dots a_n\}$ which has $n-1$ elements whose sum is $2n-4$ (i.e. remove a leaf). From the induction hypothesis the map $T^{(n-1)}$ covers $\{1, \dots, 2n-4\}$. Now for $i \in \{1, \dots , 2n-4\}$, there is some $X \subset A_{n-1}$ such that $T^{(n-1)}(X) = i$.

  • If $a_2-1 \in X$ , define $Y :=(X - \{a_2-1\}) \cup \{a_2\}\subset A_n$ so that $T^{(n)}(Y) = i+1$.
  • If $a_2-1 \notin X$, define $Y :=X \cup \{a_1\} \subset A_n$ so that $T^{(n)}(Y) = i+1$.

So $T^{(n)}$ covers $2, \dots, 2n-3$. But clearly it also covers $1 (=a_1)$ and $2n-2 (=\sum_{a\in A_n} a)$, so we're done.

$\endgroup$
1
$\begingroup$

The motivation for this work was thinking about Calvin Lin's bonus problems.


Proposition 1: Let $(a_i)_{1\le i\le n}$ be a family of positive integers such that

$$\tag 1 \sum_{i=1}^n a_i = 2n - k \; \text{ with } \,1 \le k \lt n$$

Then at least one term of the family is equal to one.
Proof
The proof is extremely easy and is left as an exercise. $\quad \blacksquare$

We call a family $(a_i)_{1\le i\le n}$ satisfying $\text{(1)}$ a $2n -k$ system.

Proposition 2: For any $2n -k$ system $(a_i)_{1\le i\le n}$ suppose $a_\iota \ge 2$ for some term. Then there are at least $a_\iota - 1$ terms that are equal to $1$.
Proof
We can always decrement a term greater than one and increment another term and still have a $2n -k$ system. If $a_\iota$ was two greater than the number of units we could construct a system with no units, contradicting proposition 1. $\quad \blacksquare$

We can now prove the main result.

Proposition 3: Let $(a_i)_{1\le i\le n}$ be a $2n -k$ system.
Then for any positive integer $m$ such that $1 \le m \le 2n -k$, there exist a subset of $K$ of $\{1, \dots, n\}$ such that

$$\tag 2 \sum _{k \in K}a_k = m$$ Proof
We begin with a 'ledger' with all of our 'chips' on the right side. Now start by moving the units, one by one, over to left side while 'shouting out' the left side total. If we run out of units and anything remains on the right side, take any 'chip' and move it over to the left side while 'giving unit change' of $1$ less back over to the right (see proposition 2); then call out the new total, an increment by $1$ over the prior summation. This is what our algorithm does, and it can resume by moving the (transferred) unit chips back over to the left side. Now just keep repeating these rules.

When this process is complete (nothing remains on the right side of the ledger), all the numbers in $1 \le m \le 2n -k$ have been 'called out' by continually bumping up the left side of the ledger. $\quad \blacksquare$

Here is an alternate set theoretic proof of the result.

Proposition 4: Let $(a_s)_{s \in S}$ be a $2n -k$ system, where $|S| = n$.
Then for any positive integer $m$ such that $1 \le m \le 2n -k$, there exist a subset of $K$ of $S$ such that

$$\tag 3 \sum _{k \in K}a_k = m$$ Proof
We can partition $S$ into two sets $U$ and $V$ so that $a_u = 1$ for $u \in U$ and $a_v \gt 1$ for $v \in V$.

If $U$ has $\alpha$ elements construct subsets $U_i$ of $U$ for $1 \le i \le \alpha$ satisfying

$\quad |U_i| = i$
$\quad U_i \subset U_{i+1}$

If $V$ has $\beta$ elements construct subsets $V_i$ of $V$ for $1 \le i \le \beta$ satisfying

$\quad |V_i| = i$
$\quad V_i \subset V_{i+1}$

Consider the integers between $\sum _{k \in V_i}a_k$ and $\sum _{k \in V_{i+1}}a_k$. Let $v_{i+1}$ be the integer in $V_{i+1}$ that is not in $V_{i}$. Then the sums of the form

$$\quad \sum _{k \in V_i}a_k + \sum _{k \in U_j}a_k \text{ with } |U_j| \lt v_{i+1}$$

completely cover these integers (see proposition 2).

It is easy to explain why the sums

$$\quad \sum _{k \in V_\beta}a_k + \sum _{k \in U_j}a_k \text{ with } 1 \le j \le \alpha$$

take out all integers between $\sum _{k \in V_\beta}a_k$ and $2n -k$ and also must take out $2n -k$ itself.

Finally, it is a 'mop up' job to show that the sums

$$\quad \sum _{k \in U_j}a_k \text{ with } |U_j| \lt V_{1}$$

cover everything remaining in the interval $[1, v_1-1]$. $\quad \blacksquare$

$\endgroup$
0
$\begingroup$

How about using an induction on $n$?

From the assumption, $a_1\leq a_2\leq \cdots \leq a_n$, we derive some facts: (you mentioned)

  • $a_1=a_2 = 1$

  • $a_3 = 1$ or $2$ if $n\geq3$

The second fact makes us possible to use an induction!

The initial case, $n=2$, is trivial. Now, assume $n\geq 3$.

Let define a new sequence $\{a_i'\}_{i=1}^{n-1}$ such that

  • $a_1'=a_2' = 1$
  • Case 1. $a_3=2$. For $i\geq 3$, $a_i' = a_{i+1}$
  • Case 2. $a_3=1$. $a_3' = a_4 -1$ and $a_i'=a_{i+1}$ for $i\geq4$.

Then, $a_1'+\cdots+a_{n-1}'=2n-4$. By the induction hypothesis, there is a surjection $T_{n-1}:\mathcal{P}([n-1])\rightarrow [2n-4]$. (here, $[n]=\{1,2,\cdots,n\}$)

For the Case 1, we can extend $T_{n-1}$ to $T_n$.

However, an extension of $T_{n-1}$ is not easy for the Case 2. (I have no idea for the exentsion for this case, unfortunately.)

$\endgroup$
  • $\begingroup$ I see, possibly, a_4=1. In this case, find smallest k such that a_{k+1}>1. And using it to make an induction. $\endgroup$ – Dong-gyu Kim Apr 8 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.