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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s