What Numbers Can We Make Now?

Henry, from St. Hugh's, answered our question at the end:

If the bags contained 3s, 7s, 11s and 15s, can you describe a quick way to check whether it is possible to choose 30 numbers that will add up to 412?

He said the following:

It is impossible to make 412.
The starting number is 3 and the difference between the numbers is 4.
If I choose 30 numbers and add them all up, I will get a number that is 30x3=90 more than a multiple of 4.
But, 90÷4=22 remainder 2, so I will get a number that is 2 more than a multiple of 4.
But since 412 is a multiple of 4 (not 2 more than a multiple of 4), it won't work.

Well spotted! Luke, from Cottenham Village College, said this in a more algebraic way, using a tool called 'modular arithmetic':

All of our numbers are of the form 4x-1, for x=1, 2, 3 or 4. Therefore the sum of 30 of them comes to $4(x_1+x_2+\dots +x_{30})-30$, which is 2 mod 4 (i.e. 2 more than a multiple of 4). But 412 is 0 mod 4 (i.e. 0 more than a multiple of 4), so this sum cannot be equal to 412.

If you are unfamiliar with Modular Arithmetic, you might like to take a look at this introductory article.

Luke also gave his thoughts on the interactivity:

The numbers in the bag always form part of a linear arithmetic sequence, and so the number in the x-th bag is mx+c. Consecutive numbers are always a fixed distance m apart. This means that we can read off the value of m easily, and then find the value of c. We can then conclude that, if you choose z numbers from the bags, their sum will be of the form $m(x_1+x_2+\dots +x_z) + cz$, as all the numbers are of the form mx+c, for different values of x. This is obviously cz more than a multiple of m.

To illustrate this method with an example, take the numbers in the bag to be 1, 4, 7 and 10, as in the original example, with z=4.
Their differences are all a multiple of 3, so by analysing them mod 3 (i.e. by looking at their remainders when they are divided by 3) we find that they are all of the form 3x+1.
As z=4 and c=1, they must be cz=4 more than a multiple of 3.
Since 4 is 1 mod 3 (i.e. dividing 4 by 3 gives remainder 1), 4 numbers selected from the bags must add to give 1 more than a multiple of 3.

Nice!