Count bulbs in ON state

Question

A room has N (1 to N inclusive) bulbs and N switches. N people go in one by one. 1st person goes in and toggles none of the switches. 2nd person goes in and toggles all switches other than the multiples of 2(2, 4, 6...). 3rd person goes in and toggles all switches other than multiples of 3(3, 6, 9...), and so on (Till Nth person toggles all the switches except Nth switch). Once the process is finished, how many bulbs are in 'on' state. (Assume that all bulbs to be in 'off' state initially).

Example : If N=3 then answer is 2 and when N=7 then answer is 5.

How to find it for given N ?

@HenningMakholm What a descriptive title there. – Mar 16 '15 at 00:25 — , Mar 16 '15 at 00:25

score 2 · Answer 1 · answered Mar 15 '15 at 16:31

Notice that for the switches to be in ON state, they would have to be "touched" an odd number of times. Consider the $k$th switch. It is touched by all except persons whose serial number is a divisor of $k$. Since the number of divisors of $k$ is odd iff the number is a perfect square, we should have all switches ON except switches whose serial number is a perfect square.

score 0 · Answer 2 · answered Mar 15 '15 at 15:43

0

The solution lies in the square numbers.

You can prove it with the divisors of a number. A square number has odd number of divisors, because, let's say N^2 is a square number, than N has the "pair" N when you write down the divisors.

This attitude is only true for square numbers, so the solutions must be the square numbers between 1 and N: 1,4,...

First person toggles all the bubbles, this means that the numbers, which are divisible with 1, are now the solutions.

Second person toggles every second one, this means that the numbers, which are divisible with 2, are now not toggled on.

This goes on until we are finished, and you can see, that if a number has odd number of divisors, it stays toggled on.

Edit: I see, that your task is kind-of upside down of what I thought, in your task, the square numbers remain turned down. This task is also known as the 100 doors problem: http://www.techinterview.org/post/526370758/100-doors-in-a-row/

answered Mar 15 '15 at 15:43

Atvin

3,392

Answer is N-(Number of perfect squares less than N ) ? – doremoon Mar 15 '15 at 15:54
Yeah, in this task, this is the correct answer, but watch out, if N is a perfect square, then you have to count it down too. :) – Atvin Mar 15 '15 at 15:56
But for 6 answer is 2 – doremoon Mar 15 '15 at 15:58
Then the task is wrong, because if for N=6, you get 2, you can't get 5 for N=7. For N=6, the number 2 is the number of perfect squares less then 6, which is obviously 1, and 4. – Atvin Mar 15 '15 at 16:00
In this particular task, the solution is N-(Number of perfect squares less than N), for N=6, you get 6-(1,4)=6-2=4. – Atvin Mar 15 '15 at 16:01
No see it once. I think you missed something – doremoon Mar 15 '15 at 16:10

Count bulbs in ON state

2 Answers2