Partitioning a sequence of positive integers into two subsequences with equal sums

Question

Tried searching on this forum but haven't found a similar problem.

Use the pigeonhole principle to prove that, for all positive integers $n$, any sequence of $n+1$ positive integers whose sum is $2n$ can be partitioned into two subsequences, each with sum equal to $n$.

Answer 1

I'll prove by induction.

$\textbf{Base Case:}$ $n = 1$

The only sequence of two positive integers that adds up to 2 is (1,1). Clearly there are two subsequences of (1,1) such that their sums equal 1.

$\textbf{Inductive Step:}$

Assume that it is true for $n$, we will prove for the $n+1^{\text{th}}$ case. Note that if we have a sequence of $n+2$ positive integers that add up to $2n+2$, then two of the positive integers must equal 1. I'll leave this for you to show.

Now the remaining $n$ integers must add up to $2n$, and we must also have that one of the $n$ numbers must be larger than 1. Otherwise if all of them were equal to 1, their sum would not be $2n$. (You can also see this through the pigeonhole principle by imagining we have $2n$ ones that must be distributed into $n$ spots.) Call this number $x_1$ and label the other numbers $x_2,...,x_n$.

So our sequence of $n+2$ numbers looks like $(1,1,x_1,x_2,...,x_n)$. We consider the following sequence of $n+1$ positive integers: $(1,x_1-1,x_2,...x_n)$. This is a sequence of $n+1$ positive integers whose sum is $2n$.

By our inductive hypothesis, this sequence has two subesequences whose sums are equal to $n$. Let A denote the subsequence that contains the term $x_1-1$, and let B denote the other subsequence.

How do we change A and B so that they are subsequences for our original sequence? Well we just add back $1$ to the $x_1-1$ term in A and we append our extra $1$ term to the subsequence B.

This gives us two subsequences whose sums are equal to $n+1$ in our original sequence.

Answer 2

Suppose it is not true for some $n$, and a set of numbers $x_{1}\leq...\leq x_{n+1}$ for which $\sum^{n+1}_{i=1}x_{i}=2n$.

Let $$m=\min\{|\sum_{j\in J}x_{j}-\sum_{i\not\in J}x_{i}|:J\subset\{1,...,n+1\}\}>0$$ be the smallest difference the two sets can have, note $m$ is even, and let $J_{m}$ be such that $$\sum_{j\in J}x_{j}-\sum_{i\not\in J}x_{i}=m$$ and let $k=\min J$, i.e. the index such that $x_{k}=\min_{j\in J}x_{j}$. Clearly $x_{k}\geq m\geq 2$

Claim: $x_{1}=...=x_{x_{k}}=1$, suppose not, then $$2n=\sum^{n+1}_{i=1}x_{i}=\sum_{i=1}^{x_{k}-1}x_{i}+\sum_{i\in\{x_{k},...,n+1\}\setminus\{k\}}x_{i}+x_{k}\geq \sum_{i=1}^{x_{k}-1}1+\sum_{i\in\{x_{k},...,n+1\}\setminus\{k\}}2+x_{k}$$ $$=x_{k}-1+2(n+1-x_{k})+x_{k}=2n+1,$$ which is a contradiction. Now define $J'=(J\setminus\{k\})\cup\{1,...,\frac{2x_{k}-m}{2}\}$, then $$\sum_{j\in J'}x_{j}-\sum_{i\not\in J'}x_{i}=m-2x_{k}+\frac{2x_{k}-m}{2}\cdot2=0.$$