Question:

Light bulbs are numbered 1 to 100, and kept off initially. First person comes and toggles all the bulbs which are multiple of 1, i.e. he switches all bulbs to on. Second person toggles all multiples of 2, i.e he turns of even bulbs. Third person comes and toggles all multiples of 3. This process continues till 100 persons pass. After this, how many bulbs are ON?

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution:

We notice that for a perfect square (like 9), the number of factors is always odd, for example:

Number of factors of (16) = # [1,2,4,8,16] = 5

Note that for non-square numbers, factors are even.

As a factor toggles the state of a bulb, bulb number 9 will be toggled by 1,3 & 9. Thus bulb number 9 will switch ON, OFF, ON respectively. Note that the odd number of factors cause bulb 9 to be ON at the end.

We note that for the odd number of factors is the cause of bulb staying on at the end. Similarly, every squared digit bulb will be switched on, and rest will remain off after all factors toggle. Thus the bulbs 1,4,9….81,100 are ON, at the end. Hence 10 bulbs are on.