Here is a well-known result.

**Theorem**. Consider a list of not-necessarily distinct integers . Then there always exists a subset of these numbers with sum divisible by .

Let’s do a quick example for 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 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 be integers. We consider the partial sums of these:

and so on up to

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

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

Let’s call these and where . Then it follows that must be divisible by .

Importantly, is the difference of two partial sums, and so it has the form

This is the sum of the subset 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?

### Like this:

Like Loading...

*Related*