Track / Stage 5 / 75 of 400 #675 of 1964

Problem 675

AIME late

Number theory Difficulty 5.2 Find the answer

9. 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. Spacing and $ signs are ignored.

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 and solution reproduced as published; topic, difficulty and ordering added by this site.