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)

  • $\begingroup$ 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. $\endgroup$ – gebruiker Jun 9 '15 at 8:53
  • $\begingroup$ @gebruiker: What is "natural" about $0$? $\endgroup$ – String Jun 9 '15 at 8:54
  • $\begingroup$ @String Depends on your religion. (I think that this is the problem with gebruiker's example though.) $\endgroup$ – Mario Carneiro Jun 9 '15 at 8:54
  • $\begingroup$ 0 is also considered "natural" by one school. $\endgroup$ – true blue anil Jun 9 '15 at 8:55
  • $\begingroup$ @String Valid point $\endgroup$ – 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$.

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

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.