Track / Stage 5 / 115 of 400 #715 of 1964

Problem 715

AIME late

Number theory Difficulty 5.2 Find the answer

There are 1000 lamps and 1000 switches, each switch controls all lamps whose numbers are multiples of its own, initially all lamps are on. Now pull the $2, 3, 5$ switches, then the number of lamps that are still on is $\qquad$ .

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solutions — 2

Solution 1

9. 499 Only the numbers that are not divisible by any of $2,3,5$ , or are divisible by exactly two of them, have their lights on.

In the range from 1 to 1000, there are 500 numbers divisible by 2, 333 numbers divisible by 3, 200 numbers divisible by 5, 166 numbers divisible by $2 \times 3$ , 100 numbers divisible by $2 \times 5$ , 66 numbers divisible by $3 \times 5$ , and 33 numbers divisible by $2 \times 3 \times 5$ .

Therefore, the numbers divisible by 2 and 3 but not by 5 are $166-33=133$ ; the numbers divisible by 2 and 5 but not by 3 are $100-33=67$ ; the numbers divisible by 3 and 5 but not by 2 are $66-33=33$ . The numbers not divisible by any of $2,3,5$ are $1000-(500+333+200-166-100-66+33)=266$ .
Thus, there are a total of $133+67+33+266=499$ lights that are on.

Solution 2

9. 499 Only the numbers that are not divisible by any of $2,3,5$ , or are exactly divisible by two of them, have their lights on.

In 1 to 1000, there are 500 numbers divisible by 2, 333 numbers divisible by 3, 200 numbers divisible by 5, 166 numbers divisible by $2 \times 3$ , 100 numbers divisible by $2 \times 5$ , 66 numbers divisible by $3 \times 5$ , and 33 numbers divisible by $2 \times 3 \times 5$ .

Therefore, the numbers divisible by 2 and 3 but not by 5 are $166-33=133$ ; the numbers divisible by 2 and 5 but not by 3 are $100-33=67$ ; the numbers divisible by 3 and 5 but not by 2 are $66-33=33$ . The numbers not divisible by any of $2,3,5$ are $1000-(500+$ $333+200-166-100-66+33)=266$ .
Thus, there are a total of $133+67+33+266=499$ lights that are on.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.