A Divisible Subset Sum

Here is a well-known result.

Theorem. Consider a list of $n$ not-necessarily distinct integers $a_1, a_2, \ldots, a_n$ . Then there always exists a subset of these numbers with sum divisible by $n$ .

Let’s do a quick example for $n = 4$ of what this result means. First, choose any four integers you like. I’m going to go with:

1, 2, 7 and 17.

Then, it follows that there must be a subset of these integers with sum divisible by 4.

Indeed, the subset $\{7, 17\}$ has a sum of 24 which is divisible by 4.

But how would we prove this result? Actually, better question: how would you prove this result? Have a go of this first before reading through the textbook proof below.

Proof. Let $a_1, a_2, \ldots a_n$ be integers. We consider the partial sums of these:

$s_1 = a_1$

$s_2 = a_1 + a_2$

$s_3 = a_1 + a_2 + a_3$

and so on up to

$s_n = a_1 +a_2 + a_3 + \cdots + a_n.$

Now, if any of the partial sums $s_i$ are divisible by $n$ then we are done. If none of them are, then consider the remainders $s_i \mod n$ .

As we have discounted zero from being a remainder, it follows that there are only $n-1$ possibilities for these $n$ remainders. By the pigeonhole principle, there must be two partial sums that are equal $\mod n$ .

Let’s call these $s_i$ and $s_j$ where $i < j$ . Then it follows that $s_j - s_i$ must be divisible by $n$ .

Importantly, $s_j - s_i$ is the difference of two partial sums, and so it has the form

$s_j - s_i = a_{i+1} + a_{i+2} + \cdots + a_{j-1} + a_j.$

This is the sum of the subset $\{a_{i+1}, a_{i+2}, \ldots, a_{j-1}, a_j\}$ and so the proof is complete.

We actually proved something slightly stronger than the theorem in the above proof. Can you work out what it is?

Here’s another thought on the proof. There is some standard mathematical backwardsness delivered with a “just trust me” smokiness when the idea of partial sums is conjured up. This does not feel natural until later in the proof when we realise why it was set up that way. Can you come up with a proof that feels more natural and proceeds more linearly?