There are 1000 light bulbs and 1000 tutors. All light bulbs are off. Tutor 1 goes flipping light bulb 1,2,3,4… tutor 2 then flips 2,4,6,8… tutor 3 then 3,6,9…etc until all 1000 tutors have done this. What is the status of light bulb 25? 93? 576? Is there a general solution to find out the status of any light bulb? How many light bulbs are on after all 1000 tutors have gone by?
Not homework but a UK university interview question. Please help.
Best Answer
Hint: Bulb number $N$ will be flipped by all tutors with number $m$ such that $m$ divides $N$ and no others.
For e.g. light bulb number $36$ will be flipped by tutors numbered $1,2,3,4,6,9,12,18,36$, so $9$ times. Since every bulb was initially off, an odd number of switches will turn it on, which is what will happen with number $36$.