CEMC Gauss (Grade 8), 2017

Solution 1

The sum of the positive integers from 1 to $n$ is given by the expression $\dfrac{n(n+1)}{2}$.

For example when $n=6$, the sum $1+2+3+4+5+6$ can be determined by adding these integers to get 21, or by using the expression $\dfrac{6(6+1)}{2}=\dfrac{42}{2}=21$.

Using this expression, the sum of the positive integers from 1 to 2017, or $1+2+3+4+\cdots+2016+2017$ is $\dfrac{2017(2018)}{2}=\dfrac{4\,070\,306}{2}=2\,035\,153$.

To determine the sum of the integers which Ashley has not underlined, we must subtract from 2 035 153 any of the 2017 integers which is a multiple of 2, or a multiple of 3, or a multiple of 5, while taking care not to subtract any number more than once.

First, we find the sum of all of the 2017 numbers which are a multiple of 2.

This sum contains 1008 integers and is equal to $2+4+6+8+\cdots+2014+2016$.

Since each number in this sum is a multiple of 2, then this sum is equal to twice the sum $1+2+3+4+\cdots+1007+1008$, since $2\times1=2$, $2\times2=4$, $2\times3=6$, and so on.

That is, $2+4+6+8+\cdots+2014+2016=2(1+2+3+4+\cdots+1007+1008)$.

Using the formula above, the sum of the first 1008 positive integers is equal to $\dfrac{1008(1009)}{2}=\dfrac{1\,017\,072}{2}=508\,536$, and so

$2+4+6+8+\cdots+2014+2016=2\times508\,536=1\,017\,072$.

We may similarly determine the sum of all of the 2017 numbers which are a multiple of 3.

This sum is equal to $3+6+9+12+\cdots+2013+2016$ and contains 672 integers (since $3\times672=2016$).

Since each of these numbers is a multiple of 3, $3+6+9+12+\cdots+2013+2016$ is equal to $3(1+2+3+4+\cdots+671+672)=3\times\dfrac{672(673)}{2}=3\times\dfrac{452\,256}{2}=3\times226\,128=678\,384$.

The sum of all of the 2017 numbers which are a multiple of 5 is equal to

$5+10+15+20+\cdots+2010+2015=5(1+2+3+4+\cdots+402+403)=5\times\dfrac{403(404)}{2}$ or $5\times81\,406$ which is equal to $407\,030$.

We summarize this work in the table below.

If we now subtract the sum of any of the 2017 integers which is a multiple of 2, or a multiple of 3, or a multiple of 5 from the sum of all 2017 integers, is the result our required sum?

The answer is no. Why?

There is overlap between the list of numbers that are a multiple of 2 and those that are a multiple of 3, and those that are a multiple of 5.

For example, any number that is a multiple of both 2 and 3 (and thus a multiple of 6) has been included in both lists and therefore has been counted twice in our work above.

We must add back into our sum those numbers that are a multiple of 6 (multiple of both 2 and 3), those that are a multiple of 10 (multiple of both 2 and 5), and those that are a multiple of 15 (multiple of both 3 and 5).

The sum of all of the 2017 numbers which are a multiple of 6 is equal to

$6+12+18+24+\cdots+2010+2016=6(1+2+3+4+\cdots+335+336)$, which is equal to $6\left(\dfrac{336(337)}{2}\right)=6\times56\,616=339\,696$.

The sum of all of the 2017 numbers which are a multiple of 10 is equal to $10+20+30+40+\cdots+2000+2010=10(1+2+3+4+\cdots+200+201)$, which is equal to $10\left(\dfrac{201(202)}{2}\right)=10\times20\,301=203\,010$.

The sum of all of the 2017 numbers which are a multiple of 15 is equal to $15+30+45+60+\cdots+1995+2010=15(1+2+3+4+\cdots+133+134)$, which is equal to $15\left(\dfrac{134(135)}{2}\right)=15\times9045=135\,675$.

We again summarize this work in the table below.

If we take the sum of all 2017 integers, subtract those that are a multiple of 2, and those that are a multiple of 3, and those that are a multiple of 5, and then add those numbers that were subtracted twice (the multiples of 6, the multiples of 10, and the multiples of 15), then we get: $$2\,035\,153-1\,017\,072-678\,384-407\,030+339\,696+203\,010+135\,675=611\,048$$ Is this the required sum?

The answer is still no, but we are close!

Consider any of the 2017 integers that is a multiple of 2, 3 and 5 (that is, a multiple of $2\times3\times5=30$).

Each number that is a multiple of 30 would have been underlined by Ashley, and therefore should not be included in our sum.

Each multiple of 30 was subtracted from the sum three times (once for each of the multiples of 2, 3 and 5), but then added back into our sum three times (once for each of the mutiples of 6, 10 and 15).

Thus, any of the 2017 integers that is a multiple of 30 must still be subtracted from 611 048 to achieve our required sum.

The sum of all of the 2017 numbers which are a multiple of 30 is equal to $30+60+90+120+\cdots+1980+2010=30(1+2+3+4+\cdots+66+67)$, which is equal to $30\left(\dfrac{67(68)}{2}\right)=30\times2278=68\,340$.

Finally, the sum of the 2017 integers which Ashley has not underlined is $611\,048-68\,340=542\,708$.

Solution 2

We begin by considering the integers from 1 to 60.

When Ashley underlines the integers divisible by 2 and by 5, this will eliminate all of the integers ending in 0, 2, 4, 5, 6, and 8.

This leaves $1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39,41,43,47,49,51,53,57,59$.

Of these, the integers $3,9,21,27,33,39,51,57$ are divisible by 3.

Therefore, of the first 60 integers, only the integers $$1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59$$ will not be underlined.

Among these 16 integers, we notice that the second set of 8 integers consists of the first 8 integers with 30 added to each.

This pattern continues, so that a corresponding set of 8 out of each block of 30 integers will not be underlined.

Noting that 2010 is the largest multiple of 30 less than 2017, this means that Ashley needs to add the integers $$\begin{array}{rrrrrrrr} 1& 7&11&13&17&19&23&29\\ 31&37&41&43&47&49&53&59\\ 61&67&71&73&77&79&83&89\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ 1981&1987&1991&1993&1997&1999&2003&2009\\ 2011&2017 \end{array}$$ Let $S$ equal the sum of these integers.

Before proceeding, we justify briefly why the pattern continues:

Every positive integer is a multiple of 30, or 1 more than a multiple of 30, or 2 more than a multiple of 30, and so on, up to 29 more than a multiple of 30. Algebraically, this is saying that every positive integer can be written in one of the forms $$30k, 30k+1, 30k+2, 30k+3, \ldots, 30k+27,30k+28,30k+29$$ depending on its remainder when divided by 30.

Every integer with an even remainder when divided by 30 is even, since 30 is also even.

Similarly, every integer with a remainder divisible by 3 or 5 when divided by 30 is divisible by 3 or 5, respectively.

This leaves us with the forms $$30k+1,30k+7,30k+11,30k+13,30k+17,30k+19,30k+23,30k+29.$$ No integer having one of these forms will be underlined, since, for example, $30k+11$ is one more than a multiple of 2 and 5 (namely, $30k+10$) and is 2 more than a multiple of 3 (namely, $30k+9$) so is not divisible by 2, 3 or 5.

The sum of the 8 integers in the first row of the table above is $120$.

Since each of the integers in the second row of the table is 30 greater than the corresponding integer in the first row, then the sum of the numbers in the second row of the table is $120+8\times30$.

Similarly, the sum of the integers in the third row is $120+8\times60$, and so on.

We note that $2010 = 67 \times 30$ and $1980 = 66 \times 30$, so there are 67 complete rows in the table.

Therefore, $$\begin{aligned} S & = 120+(120+8\times30)+(120+8\times60)+\cdots+(120+8\times1980) + (2011+2017) \\ & = 120\times 67 + 8\times(30+60+\cdots+ 1980) + 4028 \\ & = 8040 + 8\times30\times(1+2+\cdots + 65 + 66) + 4028 \\ & = 12\,068 + 240\times(33\times 67) \\ & = 12\,068 + 530\,640 \\ & = 542\,708\end{aligned}$$

Here, we have used the fact that the integers from 1 to 66 can be grouped into 33 pairs each of which adds to 67, as shown here: $$1+2+\cdots+65+66 = (1+66)+(2+65)+\cdots+ (33+34) = 67 +67 + \cdots + 67 = 33\times 67$$