Find the number of Lights.

Number Theory Level 3

The students of a Technical Institute went to the house of bulb collector Prof Sharma. He gave them a task- Each of them had to go and switch on bulbs that were switched off and switch off the on ones. At the start, all lights were switched off. They had to proceed in the following manner-
1. The first student switched on all lights.
2. The second one switches off all switches that are multiples of two.
3. The third one switched off all on lights and switched on the off lights that were multiples of 3.This continued for 4, 5, 6 and so on.

If the professor had 1000 bulbs and each of the 1000 students did as told, find the number of bulbs that remained on after the exercise.

The answer is 31.

2 solutions

Eddie The Head
Apr 7, 2014

Clearly the bulbs which will remain switched on will be theones which have been altered an odd number of times and the number of times each bulb is altered is equal to it's total number of factors.....we know that only perfect square numbers have an odd number od factors and hence the number of bulbs switched on will be the numbers having squares less than 1000 ie 31..

Nice problem :)

So, in general, if there are $n$ light bulbs (all turned off at the beginning) and $n$ students (obviously $n\in\Bbb{Z^+}$ ), then we have,

$\textrm{\# of light bulbs that are on after the exercise}=\left\lfloor\sqrt{n}\right\rfloor$

Prasun Biswas - 5 years, 9 months ago

Ameya Salankar
Apr 6, 2014

First of all, let me tell you that this is a brilliant problem!

Let each bulb be numbered $1, 2 , 3, \dots$ . We reason out as follows:

Observe that the actions performed on trip # $d$ affect only the light bulbs numbered $d, 2d, 3d, 4d, \dots$ or in other words, multiples of $d$ . Now here comes the reasoning part -

At the start, each bulb is switched on , so for a bulb to be ultimately left on, it's switch should be pressed odd number of times. In other words, the light bulb's number should have odd number of divisors .

Having found this, I found that the only numbers with odd divisors are the perfect squares . There are exactly $31$ perfect squares under $1000$ .

$\Rightarrow$ The bulbs which remained switched on were $\boxed{31}$ .

Find the number of Lights.

The answer is 31.

2 solutions

0 pending reports