The Magic Café
Username:
Password:
[ Lost Password ]
  [ Forgot Username ]
The Magic Cafe Forum Index » » Puzzle me this... » » One million light bulbs! (0 Likes) Printer Friendly Version

Scott Cram
View Profile
Inner circle
2676 Posts

Profile of Scott Cram
There is a row of one million light bulbs, labeled from 1 to 1,000,000. To start with, all the bulbs are off.

What is going to be done with the light bulbs involves "flips". A "flip" is simply the change of state of the light bulb - if the light bulb is off, a flip will turn it on. If a light bulb is on, a flip will turn it off.

Starting with bulb #1, every bulb is flipped (obviously, this results in all the bulbs being on). Next, starting with bulb #2, every second bulb is flipped (resulting in only the odd numbered bulbs remaining on). This continues with bulb #3, and every third bulb being flipped, then starting at #4 and every fourth bulb being flipped, and so on, until we reach bulb #1,000,000 with "every millionth bulb" (just the one, of course) being flipped.

At the end of this exercise, which bulbs are on, and which bulbs are off?
thefifth
View Profile
Regular user
105 Posts

Profile of thefifth
All perfect squares will be on, and the rest off. I believe this puzzle relies on how many products a number has. Most numbers have an even number of products where as perfect squares have an odd number of products.
[email]info@williampenix.com[/email]
www.williampenix.com
TomasB
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
I sense that this is correct and would love to see a proof that squares have an odd number of different divisors and that all other integers have an even number of different divisors. Sounds like a nice problem indeed.

/Tomas
Scott Cram
View Profile
Inner circle
2676 Posts

Profile of Scott Cram
Tomas, thefifth was indeed correct. As for the proof, it is quite simple.

Any number will always have at least two factors, 1 and itself. Any other factors will always bring in another pair of numbers, which keeps the number of factors even. The only case where this isn't technically true is the case of a square number. In this case, you're bringing in another pair of factors, but they're both exactly the same number, so you're really only adding 1 factor. Thus, square numbers are the only case where a number would have an odd number of factors.

For example, check out the factors of the first 5 square numbers:

1=1
4=1,2,4
9=1,3,9
16=1,2,4,8,16
25=1,5,25
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
Maybe this is not rigorous enough but I will give it a go...

imagine all the integers from 1 to the number - N, on a line.
now divide this line into two segments at the square root point (this might be directly ON an integer or between two)
now, starting with "1" - any factor of N will have a "brother" factor on the other segment, if not their product will either be less than N or bigger than N (the product of any 2 numbers on the left segment is less than N since the two largest integers there can "reach" maximum to N - same argument applies for the right hand segment bur with opposite results)
therefore we can start to cross off pairs of factors - one from each segment. the only exception is when we got a perfect square, then the division point is exactly "on" a factor.

hope I could make it clear enough,

Nir
TomasB
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
Scott, "Any other factors will always bring in another pair of numbers, which keeps the number of factors even." was too compressed for me. Smile

Any chance you can rewrite it? You are using the word "factors" in an uncommon way. I assume that at at least one point here you mean "divisor", since the number itself is a factor only if the number is prime. Do you mean "divisor" when you write "number"? Let's say the number is 15, so it has 1 and 15 as divisors. What's the reasoning that the divisor 3 has to bring another divisor with it (and only one)? I know that it does, of course, but I can't quite follow the resoning.

Ah, just read Nir's take on it. Brilliant idea to look around the point sqrt(N). Forget what I asked above. Smile

/Tomas
drkptrs1975
View Profile
Elite user
North Eastern PA
452 Posts

Profile of drkptrs1975
What I do know is this, the ones that alternate an Odd number of times will be on, and the ones that alternate an even amount of times will be off.
The Magic Cafe Forum Index » » Puzzle me this... » » One million light bulbs! (0 Likes)
[ Top of Page ]
All content & postings Copyright © 2001-2019 Steve Brooks. All Rights Reserved.
This page was created in 0.16 seconds requiring 5 database queries.
The views and comments expressed on The Magic Café
are not necessarily those of The Magic Café, Steve Brooks, or Steve Brooks Magic.
> Privacy Statement <

ROTFL Billions and billions served! ROTFL