The Magic Cafe Forum Index » » Puzzle me this... » » One million light bulbs! (0 Likes) Scott Cram Inner circle 2677 Posts  Posted: Aug 21, 2005 04:26 pm 0 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? Grey Matters:Blog|Videos|Mental Gym|Presentation|Store thefifth Regular user 105 Posts  Posted: Aug 21, 2005 04:56 pm 0 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 Inner circle Sweden 1143 Posts  Posted: Aug 22, 2005 07:06 am 0 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 Inner circle 2677 Posts  Posted: Aug 22, 2005 08:01 am 0 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 Grey Matters:Blog|Videos|Mental Gym|Presentation|Store Nir Dahan Inner circle Munich, Germany 1390 Posts  Posted: Aug 22, 2005 08:15 am 0 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 Adventures in ASIC digital design TomasB Inner circle Sweden 1143 Posts  Posted: Aug 22, 2005 10:08 am 0 Scott, "Any other factors will always bring in another pair of numbers, which keeps the number of factors even." was too compressed for me. 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. /Tomas drkptrs1975 Elite user North Eastern PA 452 Posts  Posted: Sep 1, 2005 03:02 pm 0 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)
 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 <   