100 switches start off. Person 1 flips every switch, person 2 flips every 2nd switch, person 3 every 3rd, and so on up to person 100. How many switches are on at the end?
Right answers go through as you type.
Show the solution
Answer: 10
Flips for switches 1 to 16. Orange ones are flipped an odd number of times.
Step 1 · Switch k is flipped by each person whose number divides k
switch 12: people 1,2,3,4,6,12
Person m flips switches m,2m,3m,…, so a switch is flipped once for each of its divisors.
Step 2 · On at the end means an odd number of flips
divisors pair up:2×6,3×4…
Divisors come in pairs that multiply to k. Only a perfect square has one divisor paired with itself, so only squares have an odd count.