| easy | general |
Light bulbs are numbered 1 to 100, and kept off initially. The first person comes and toggles all the bulbs which are multiple of 1, i.e. they switch all bulbs to 'ON'. The second person toggles all multiples of 2, i.e. they turn the even bulbs 'OFF'. The third person comes and toggles all multiples of 3. This process continues till the person do their part. After this, how many bulbs are 'ON'?
Consider bulb number 9.
10 bulbs
We notice that for a perfect square (like 9), the number of factors is always odd, for example The number of factors of (16) = # [1,2,4,8,16] = 5 Note that for non-square numbers, factors are always even.
A bulb is toggled between ON / OFF states only by the person with a factor of . Bulb number 9 will be toggled by 1,3 & 9. Thus bulb number 9 will be 'ON', 'OFF' and 'ON' respectively. Because of odd factors, the bulb stays 'ON' at the end.
All the perfect-square numbered bulbs (odd factors) will stay 'ON', and the rest bulbs will turn OFF at the end. Thus bulbs 1,4,9....81,100 are ON, at the end.
Hence 10 bulbs are on.