Which lightbulbs are on?

**Ruichan** · October 26th 2006, 12:47 PM

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.

**Quick** · October 26th 2006, 03:17 PM

Originally Posted by Ruichan

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 5th lightbulb and so on till the 100th person.
How many lightbulbs are on after the 100th person flips the switch?

I was just about to do it when I read:

Do not use Excel to solve the question.

There's always a catch

Anyway, is it every prime number? Or what...

**Ruichan** · October 26th 2006, 04:01 PM

Originally Posted by Quick

I was just about to do it when I read:

There's always a catch

Anyway, is it every prime number? Or what...

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

I need to check my answer too. My usage and knowledge of Excel is really not the best.

**Quick** · October 26th 2006, 05:36 PM

Originally Posted by Ruichan

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

I need to check my answer too. My usage and knowledge of Excel is really not the best.

There is usually a way to do things mathematically, but back to my question, you say that the 4th person turns off every 5th light bulb, did you mean to say 4th lightbulb or is it that each person turns off the next primeth light bulb?

**ThePerfectHacker** · October 26th 2006, 06:34 PM

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 $\tau (n)$ it is the number of divisors of $n\geq 1$ . For example,
$\tau (6)=4$ because $1,2,3,6$ 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 $1,2,4,5,10,20,25,50,100$
That means it is turned on and off $\tau (100)$ times.

The number 99 is activated (either on or off) by $1,3,9,11,33,99$ . That means it is turned on and off $\tau (99)$ times.

That means 98 is activated (either on or off) by $\tau (98)$ .

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 $\tau (n)$ is odd if and only if $n$ 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 $n\geq 1$ lightbulbs.
The number of ones that remain lit is,
$[\sqrt{n}]$
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?

**Ruichan** · October 26th 2006, 11:28 PM

Originally Posted by Quick

There is usually a way to do things mathematically, but back to my question, you say that the 4th person turns off every 5th light bulb, did you mean to say 4th lightbulb or is it that each person turns off the next primeth light bulb?

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.

**Soroban** · October 27th 2006, 11:19 AM

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: . $24\:=\:1 \times 24 \:=\:2 \times 12 \:=\:3 \times 8 \:=\:4 \times 6$ (8 divisors).

We find that $16$ has five divisors: 1, 2, 4, 8, 16
. . and that $25$ has three divisors: 1, 5, 25
. . and that $36$ 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.

**Ruichan** · October 27th 2006, 06:40 PM

Originally Posted by Soroban

Hello, Ruichan!

This is a classic (old) problem.

[/size]

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!

**Aquafina** · October 28th 2009, 12:52 AM

Originally Posted by Soroban

The bulbs that are left on are: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.

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

**Aquafina** · October 28th 2009, 12:58 AM

Originally Posted by Soroban

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.

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?

**Aquafina** · October 28th 2009, 01:15 AM

Originally Posted by Quick

I was just about to do it when I read:

There's always a catch

Anyway, is it every prime number? Or what...

How would you use Excel? I want to check my answers

Thread: Which lightbulbs are on?

LinkBack

Thread Tools

Display

Which lightbulbs are on?

Similar Math Help Forum Discussions

Probability 2 - Lightbulbs

Calculus - Lightbulbs

Search Tags