# Partitioning $n$ naturals summing $2N$ into two sets summing $N$

I'm trying to solve this problem:

Let $a_1, \ldots , a_n$ be natural numbers such that $a_k \le k$ for every $k = 1,\ldots,n$, and $\sum_{k=1}^{n} a_k=2N$. Show that there exists a partition of this $n$ numbers in two sets, such that for each set, the sum of its elements is $N$.

I think I found an algorithm that works, but I don't know how to formally prove that it works. It goes as follows:

We have $a_1, \ldots , a_n$. Rearrange the elements in ascending order. This preserves the property that $a_k \le k$ for every $k = 1,\ldots,n$. Then start by picking the biggest element $a_n$. Add to it $a_{n-1}$, which is $\le a_{n}$. If the sum exceeds N, go back on your steps and substract $a_{n-1}$, then try the same with $a_{n-2}$. If, on the contrary, the sum didn't exceed N, also go on to $a_{n-2}$, but this time without subtracting $a_{n-1}$. Keep doing this until you reach $a_1$, meaning that you tried to add every element to the sum, with the condition that the inclusion of that element doesn't make the sum bigger than $N$. In the end, the elements you picked sum $N$, and the ones left out also sum $N$.

Could someone help me formalize this? (or show me that it doesn't work) (or show me a nicer way to solve this)

• If believe that $(a_1,a_2,a_3)=(1,0,3)$ is a counter example. Its sum equals $4=2\cdot 2$, but I cannot even find one partition that sums up to two. – gebruiker Jun 9 '15 at 8:53
• @gebruiker: What is "natural" about $0$? – String Jun 9 '15 at 8:54
• @String Depends on your religion. (I think that this is the problem with gebruiker's example though.) – Mario Carneiro Jun 9 '15 at 8:54
• 0 is also considered "natural" by one school. – true blue anil Jun 9 '15 at 8:55
• @String Valid point – gebruiker Jun 9 '15 at 8:57

We can show by induction the even stronger statement, that given natural numbers $a_1\leq ...\leq a_n$ with $a_k\leq k$ we can find a subset summing to any number between $0$ (the empty sum) and $S_n=\sum_{k=1}^n a_k$:

First the base case, namely $n=1$, in which we only have $a_1=1$ and every number between $0$ and $\sum_{k=1}^1 a_1=1$ can be formed from summing a subset.

Then the inductive step: given $a_1\leq ...\leq a_n$, we know that $\sum_{k=1}^{n-1} a_k=S_{n-1}\geq n-1$ since each $a_k\geq 1$, and by the induction hypothesis, these $n-1$ numbers can form any number between $0$ and $S_{n-1}\geq n-1\geq a_n-1$. Thus together with $a_n$ they can form any number between $0$ and $a_n-1$, but also between $a_n+0$ and $a_n+S_{n-1}=\sum_{k=1}^n a_k$. Done.

In particular in the setup in the question, we can make subsets of the $a_k$'s sum to any given number between $0$ and $2N$. In particular $N$.

• Don't you want your claim to be that there is a subset summing to anything between $0$ and $\sum_k a_k$? – Mario Carneiro Jun 9 '15 at 9:18
• @MarioCarneiro: Oh, true. I did not consider the empty set. But it does not seem to be all that important here. – String Jun 9 '15 at 9:23
• Yeah, it just saves you a tiny bit of case analysis for the "$a_n$ (naturally)" part (and makes the proof more "natural" IMO). – Mario Carneiro Jun 9 '15 at 9:25
• @MarioCarneiro: You are right! – String Jun 9 '15 at 9:26
• @MarioCarneiro: Does it look better this way? – String Jun 9 '15 at 9:27