1,000,000 Light bulbs....

[RyanJ]

Picture this, you have an array of 1,000,000 light bulbs, numbered 1 to 1,000,000, all of which are off (and all of which work).

 

The following task involves these light bulbs and an action we'll call "flipping". Flipping simply means changing the state of a light bulb. If the bulb is off, flipping will turn it on. If the bulb is on, flipping it will turn it off.

 

Starting with all the light bulbs off, you start at bulb #1, and flip the state of every bulb. Once you've done that, you go back and start with bulb #2, flipping the state of every second bulb. Next, you go back, start with bulb #3, and flip the state of every third bulb.

 

This continues all the way up to 1,000,000, where you flip the state of every "millionth" bulb (obviously, just the one bulb).

 

Here's the question: After performing this massive task, which light bulbs will be on, and which light bulbs will be off?

 

Enjoy!

 

Ryan Jones

[drochaid]

They will all be off. After being switched on and off so much, they will almost certainly have blown.

[RyanJ]

They will all be off. After being switched on and off so much, they will almost certainly have blown.

 

 

Good answer

 

Quite correct, they all would have blown

 

Cheers,

 

Ryan Jones

[drochaid]

aww, that was meant to be a smart alec answer, not correct! :-D

[RyanJ]

aww, that was meant to be a smart alec answer, not correct! :-D

 

 

Well, it is correct.

 

If you want to give an answer where the bulbs are unbreable then that would be even better

 

Cheers,

 

Ryan Jones

[Mobius]

this is a good question and I don't like answers that state the impraticallity of the question when we should only consider the maths.

 

Light bulb number 1 is obviously on, so are all the prime numbers. Lightbulb 2 is off (as you won't be coming back to it after flipping every second bulb), 3 is on, 4 is off... therefore all the odd light bulbs will be ON and all the even bulbs will be OFF.

[RyanJ]

this is a good question and I don't like answers that state the impraticallity of the question when we should only consider the maths.

 

Light bulb number 1 is obviously on' date=' so are all the prime numbers. Lightbulb 2 is off (as you won't be coming back to it after flipping every second bulb), 3 is on, 4 is off... therefore all the odd light bulbs will be ON and all the even bulbs will be OFF.[/quote']

 

So you are saying a 50% - 50% ratio? Correct.

 

I drew the first hundred out to prove this to myself after I posted the question.

 

Is there amy mathematican way to prove this? it actually makes sence to me like that but I've never seen proof of it

 

Cheers,

 

Ryan Jones

[Mobius]

Actually my original post is incorrect. I over simplified the sum.

In the situation of 10 light bulbs only 1 and 4 are on when you are finished. I will work on this some more.

[RyanJ]

Actually my original post is incorrect. I over simplified the sum.

In the situation of 10 light bulbs only 1 and 4 are on when you are finished. I will work on this some more.

 

 

Great, can't wait to see your proof

 

Cheers,

 

Ryan Jones

[Mobius]

Okay, I wrote a program to map out the results (well the first 100 anyway).

 

It seems that the only bulbs left on are the square numbers... So light bulb 1, 4, 9, 16, 25.... are on while the rest are off.

 

As yet I have no proof...

[Mobius]

Okay from a logical point of view.

 

All bulbs are turned on. then every second 1 is switched off. All multiples of 2 are switched off, this means that 2 squared i.e. is off. Now it will be turned on when we come to every 4th bulb. After this these earlier numbers are left alone. now look at the 3rd bulb, this will turn every 3rd bulb off which includes 9. This one will be turned back on when we get to switch every 9th light bulb.

 

All the numbers have a corresponding square number which will be off until it is turned on when it is time to switch that number. All the other bulbs will end up being switched off.

 

This is not so much a mathematical proof but a logical one....

[The Thing]

This is a pattern problem, and the only way I see it being done is figuring out the pattern. Do a smaller sample of the light bulbs first, say the first 100.

Draw a chart to map out all the remaining bulbs.

We find out that the lights that are left on are all perfect squares, so we can safely deduct (hopefully) that perfect squares will be the only light bulbs that are on. The biggest perfect square in 1 mil is 1,000,000.

[math]

\sqrt{1000000}=1000

[/math],

thus 1000 lights are on, namely the 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144 etc lights.

[shmoe]

At the nth step, the mth bulb is flipped if and only if n divides m, so you want to determine which m's have an odd number of divisors. Consider the prime factorization of m etc..

[cosine]

This is a pattern problem' date=' and the only way I see it being done is figuring out the pattern. Do a smaller sample of the light bulbs first, say the first 100.

Draw a chart to map out all the remaining bulbs.

We find out that the lights that are left on are all perfect squares, so we can safely deduct (hopefully) that perfect squares will be the only light bulbs that are on. The biggest perfect square in 1 mil is 1,000,000.

[math']

\sqrt{1000000}=1000

[/math],

thus 1000 lights are on, namely the 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144 etc lights.

 

Yes, it is correct that only perfect squares will be on. The reasoning follows this way.

 

We can agree that if a bulb has been flipped an even number of times, it will be off.

 

And If a bulb has been flipped an odd number of times, it will be on.

 

Now whenever starting from a bulb that is a Factor of the Nth bulb, the Nth bulb will be flipped that turn.

 

So the problem is equivalent to finding what numbers have an even number of factors, and which have an odd number of factors.

 

Consider a number N, if a is a factor of N, then there exists a number b such that ab = N, by definition of a factor. So that means that for every factor, there exists another factor in the set of factors of N.

 

Consider N such that that for all a that are factors of N, the b for which ab = N is not a. Thus for every factor a, there is another factor. Thus, there is an even number of factors.

 

Consider N such that there exists an a in the set of of factors of N, such that ab = N where b is a, or in other words that a^2 = N. For now, assume that there is only one such a (to be proven later). Now if you remember from the previous case, the number of all factors of N besides a is even. Thus including a would lead to an odd number of factors. Now, if our assumption is true, then we have proved what we wanted to.

 

To proove there is at most one a such that a*a = N, assume the opposite. That is, assume there is distinct A and B such that there squares are equal to N, with A being the greater. Let B be represented by A - C.

Then A*A = (A - C)(A - C). Take the square root of both sides, A = A - C. But this is true only if C = 0. But then B = A, contradictory to hypothesis. Thus there is no more than 1 a such that a*a = N.

 

So all of this demonstrates mathematically why only the square numbers are on.