Maths on Steroids: Tute 4

I didn't think that I was going to write up this post. But there's something compelling about the following question from the yellow Accelerated Mathematics exercise (*) book. It is, after all, one of my favourite questions from the book (as in, it was around when I did one of the old incarnations of this subject).

To be honest, I never managed to solve it. I thought about it for a day or two but just couldn't really make any headway. And I'm not sure who eventually showed me how to do it - probably Nick Sheridan or Zhihong Chen, or both. But here it is, in all its unadulterated vexatiousness:

Problem sheet 3, question 19 (official rating: Very hard easy):

Prove that, for any 1993 integers, there is a subset whose sum is divisible by 1993.

Okay, well, you can see that this version of the question is a bit outdated. Like, twenty years outdated. So let's solve it, but with 1993 changed to 2013. =P

Now, you might think this changing of numbers is just some general frivolousness on my part, but there's something to it: I've just hinted that this property isn't specific to the number 1993 - which is prime, but also applies to 2013 - which certainly isn't. So, whatever strategy that we try had better not need prime-factor-based arguments (**).

Now, let's call these integers $a_1, a_2, a_3,\ldots, a_{2013}$ and consider the following related integers: $$\begin{align}b_1&=a_1,\\ b_2&=a_1+a_2,\\b_3&=a_1+a_2+a_3,\\&\vdots\\b_{2013}&=a_1+a_2+a_3+\ldots+a_{2013}.\end{align}$$

Now, if any of these $b_i$s is a multiple of $2013$, then we're done - because each $b_i$ is the sum of some subset of the $a_j$s.

On the other hand, if none of the $b_i$s are a multiple of $2013$, then their remainders when divided by $2013$ are going to be integers between $1$ and $2012$. So, we've got 2013 $b_i$s, and their remainders could be one of 2012 different numbers; by the pigeonhole principle (try squeezing 2013 pigeons into 2012 holes), two of these numbers $b_n$ and $b_{n+m}$ must have the same remainder. But this means that $$\begin{align}b_{n+m}-b_n=a_{n+1}+a_{n+2}+\ldots+a_{n+m}\end{align}$$ is a multiple of $2013$. And we're done!

Okay, I admit that looked pretty easy, and in some sense...it was pretty easy. But to someone who hasn't done very much recreational or puzzly maths (or just maths), there's a stunning idea there - that in reorganising things you can sometimes observe the patterns more easily. Orrite orrite, it sounds even more trivial and trite and obvious when I put it like that, but I think that you get the point. So much of mathematics is based on organising things neatly. E.G.: matrices arise from wanting to organise linear equations neatly, and anyone who's done and understood a course in linear algebra can tell you how amazing matrices are.

So ugh...yea...totes do the "Very hard" questions in the exercise book guys...guuuuuys? =P

*: I don't know why, but it'd taken me years to learn how to spell "exercise". I guess I always used to chuck an extra "c" after the "x". Shrug

**: If you think about it, it's kinda weird that the difficulty of the question is somehow hugely affected by what number you give. And that in this case, giving a "nicer" number - a prime, actually makes the problem way harder. Just coz you get distracted by it.