Maths Olympiad Prep

Track / Stage 5 / 203 of 400 #803 of 1964

Problem 803

AIME late
Number theory Difficulty 5.5 Find the answer

Joana wrote the numbers from 1 to 10000 on the blackboard and then erased all multiples of 7 and 11. What number remained in the 2008th position?

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

Official solution

Initially observe that, from 1 to 77, Joana erased 11 multiples of 7 and 7 multiples of 11. Since 77 is a multiple of 7 and 11, she erased 11+71=1711+7-1=17 numbers, leaving 7717=6077-17=60 numbers. Now, grouping the first 10000 numbers into groups of 77 consecutive numbers, this reasoning applies to each of the lines below, that is, in each line 60 numbers remained.

 1st line: 1,2,,772nd  line: 78,79,,1543rd  line: 155,158,,231 \begin{array}{ccccc} \text { 1st line: } & 1, & 2, & \ldots, & 77 \\ 2^{\text {nd }} \text { line: } & 78, & 79, & \ldots, & 154 \\ 3^{\text {rd }} \text { line: } & 155, & 158, & \ldots, & 231 \end{array}

Since 2008=33×60+282008=33 \times 60+28, we know that among the first 33×77=254133 \times 77=2541 numbers, 33×60=198033 \times 60=1980 numbers remained without being erased.

 33rd line: ,,,2541 \text { 33rd line: } \quad \ldots, \quad \ldots, \quad \ldots, \quad 2541

We still need to count 28 numbers. Let's then examine the 34th line, which starts with 2542. Since the erased numbers are in columns 7,11,14,21,22,28,33,357,11,14,21,22,28,33,35, etc., and up to the 35th 35^{\text {th }} column, eight numbers have been erased, there remain 358=2735-8=27 numbers in the 34th 34^{\text {th }} line. Therefore, after erasing the multiples of 7 and 11 in this line, the 28th number is 2577. Thus, the number in the 2008th position is 2577.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.