A problem with the bulbs

[agnibho]

1. The problem statement, all variables and given/known data
There're 60 bulbs in a classroom with 60 students. Initially all of them were switched off.Now gradually the students enter roll number wise and toggle the switches that are multiples of each of their roll numbers. For example, when roll no. 1 enters, he switches on all the bulbs(as they were all switched off initially), and when roll2 enters the room, he toggles the switches that are the multiple of 2 i.e. 2,4,6,8,10....so on.At last when the teacher entered the class how many bulbs did she find switched on??

2. The attempt at a solution
I took the roll no. of the students as i. Then he toggles the switches of the multiple of i.
I couldn't find a way to solve this equation. Can anyone help me??

[HallsofIvy]

Initally, all bulbs are on. After the first student, all are off. After the second student, all the even numbered bulbs are on, odd off. After the third student, All bulbs that are multiples of 3, but NOT 2 (i.e. not multiples of 6) are on, all multiples of 6 are off, even numbers that are not multiples of 3 (even but not multiples of 6)are on, all others, odd but not multiples of 3, are off. Note which bulbs are off: all bulbs that are multiples of both 2 and 3 or are multiples of neither. Can you see (work through the possible on and off switches carefully) that after the fourth student, the bulbs that are multiples of 12 (multiples of 2 and 3 and 4) and bulbs that are multiples of none of 2, 3, and 4 are off?

[ehild]

See how many student toggles a certain lamp. If odd number of students, it is on. If even number, it is off. Find the numbers from 1 to 60 which have odd number of divisors. For example, 4 can be divided by 1,2 and 4. Students 1,2, and 4 will toggle it, so it will be on at the end. This is "brute force" but not that terrible.

ehild

[OmCheeto]

What a delightful homework problem. It reminds me of my OCD mathematical youth, my later forages into SciAm's mathematical recreations, and a certain problem in my first year computer science class.

I know the answer, but I cannot tell you how or why, as the logic behind the square of the number increase solution eludes me.

http://home.europa.com/~garry/pf_2011_09_24_mathematical_recreation.jpg
-1 = off, 1 = on

Good luck!

ps. Is the answer in the back of the book?

pps. I will not be offended if this post is deleted, as I've implied the answer without solving the problem. :redface:

[ehild]

The divisors of the number of a bulb N are in pairs: if a divides it, so does N/a. There are odd number of divisors if N/a=a, that is N is a square number.

Initially, all bulbs are off. See bulb 9 for example. The first student switches it on. The second one does not toggle it, but the third student switches off. Then nothing happens till the ninth student arrives, who switches on. Find all square numbers less than 60...

ehild