There are 100 people and 100 lightbulbs. All the lightbulbs are off.
The first person flips the switch and turn all the lightbulbs on.
The 2nd person flips the switch of every 2nd lightbulb.
The 3rd person flips the switch of every 3rd lightbulb.
The 4th person flips the switch of every 4th lightbulb and so on till the 100th person.
How many lightbulbs are on after the 100th person flips the switch?
Do not use Excel to solve the question.
EDIT: Actually, please feel free to use any methods to solve the puzzle. :P Heheheh....I actually was looking to see if there's any other way apart from using Excel, which I did. :P
Sorry, it's the 4th person flips the switch of every 4th lightbulb.
I came up with an elegant way to solve this problem
This approach uses Number Theory.
Specifically something called number-theortic functions.
The function that I will use is it is the number of divisors of . For example,
because are divisors.
Now, returning back to the problem.
I will work backwards because it is easier to follow.
The number 100 is activated (either on or off) by
That means it is turned on and off times.
The number 99 is activated (either on or off) by . That means it is turned on and off times.
That means 98 is activated (either on or off) by .
And so on....
~~~~~~ Take a pause
Okay now we get to the fun part.
The numbers that are remained lit are those numbers that have an odd number of divisors. Because: on, off, on, off, on, off.... So if the number is odd then it remains lit.
What I am about to state I will not prove....
It can be shown in number theory that is odd if and only if is a square.
That means, all the square in between 1 and 100 are lit.
That means,
1,4,9,16,25,36,49,64,81,100
Which is 10.
~~~
Given lightbulbs.
The number of ones that remain lit is,
Where is the greatest integer function.
As a result I can up with my own riddle.
What is the ratio of the lightbulbs lit to lightbulbs dead, tending to?
Oops, sorry, didn't check what I typed. yup it's every 4th lightbulb.
Gee... I didn't know about number theory. Havn't taken number theory at all.
I only came up with the squares with Excel, 10 bulbs on.
Since my excel sucks, I was intending to check the answer with the old fashion way, drawing 100 lightbulbs then striking them off. Yeah...I'm that slow when it comes to using my brain for Math.
Hello, Ruichan!
This is a classic (old) problem.
There are 100 people and 100 lightbulbs. . All the lightbulbs are off.
The first person flips the switch and turn all the lightbulbs on.
The 2nd person flips the switch of every 2nd lightbulb.
The 3rd person flips the switch of every 3rd lightbulb.
The 4th person flips the switch of every 4th lightbulb and so on till the 100th person.
How many lightbulbs are on after the 100th person flips the switch?
With a little exploring you could have discovered the secret.
Consider the 12th bulb. .It will be:
. . turned on by the 1st person,
. . turned off by the 2nd person,
. . turned on by the 3rd person,
. . turned off by the 4th person,
. . ignored the 5th person,
. . turned on by the 6th person,
. . ignored by the 7th, 8th, 9th, 10th, and 11th persons,
, , turned off by the 12th person.
The state of the bulb is changed by people with numbers that divide 12.
Since 12 has six divisors: 1, 2, 3, 4, 6, 12 . . . an even number of divisors,
. . bulb #12 will be off and the end of the problem.
In general, if a bulb has a number with an even number of divisors, it will be off.
The only bulbs left on have numbers with an odd number of divisors.
Very well, which ones are they?
Most number have an even number of divisors because they "come in pairs".
For example: . (8 divisors).
We find that has five divisors: 1, 2, 4, 8, 16
. . and that has three divisors: 1, 5, 25
. . and that has seven divisors: 1, 2, 3, 4, 6, 9, 12, 18, 36
Get it? . . . Only the squares have an odd number of divisors!
The bulbs that are left on are: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.
My prof did mention that it's a classic. However, all Math puzzles to me, are new and I have to spend time looking at it if I don't know how to use Excel to solve it. Yup, I'm kind of slow at Math. I'm going to study what all of you guys wrote.
Thank you very much. At least if the prof asked how did I get the answer, I could give him an answer that make sense. Thank you very much again!
I was doing the similar Locker Problem and was directed to this thread, where Student 1 opens all lockers, 2 changes 2,3,4 etc... There are 1000 lockers and 1000 students.
How would we solve:
i) How many lockers are closed immediately after the third student has walked along the corridor? Explain your reasoning.
(ii) How many lockers are closed immediately after the fourth student has walked along the corridor? Explain your reasoning.
My answer was:
) student 3 opens all even multiples of 3, closes odd multiples. He changes 333 lockers, and 333/3 = odd, so last thing he does is close a locker, which isnt cancelled by a further opening.
so 1 more closed at the end. ==> 501 closed
ii) All multiples of 3 and 4 will be closed, and multiples of 4 not multiples of 3 opened
all numbers of the form 12a are multiples of 3 and 4
1000 div by 4 250 times, so 250 lockers changed
1000 is div by 12, 83 times, so 83 closed
250 - 83 = 167 opened
so the total is: 167 - 83 = 83 lockers opened which not cancelled by another closing
so 501 - 84 = 417 lockers closed at the end
Is this correct? Does anyone have a more elegant solution?
Thanks
Also:
(iv) After the hundredth student has walked along the corridor, what is the state of locker 1000? Explain your reasoning.
1000 is not a square number, but it is left open since it has 11 divisors from 0-100. Is there any other method to do this, without counting up its divisors in that range?