[Guest]

(standard apology if repost, but I didn't find it in search)

This puzzle was featured recently on Car Talk.

You're standing at the start of a (very) long hallway with bulbs all in a row. Let's say there are 40,000 bulbs. All begin in the "off" position. Each light has its own (labeled) toggle switch (flipping it will switch the indicated bulb from on to off, or off to on).

First you toggle every switch. (This obviously turns all bulbs on, from bulb 1 to bulb 4e4).

Next you toggle every other switch (that is, beginning with bulb 2, then 4, 6,...,4e4). This produces the pattern on-off-on-off-on-...-off.

Next you toggle every third switch (bulb 3,6,9,...,39999). Then every 4th, 5th, etc. until you reach every 40,000th switch (which of course would just be toggling the last switch).

-Will bulb number 40,000 end on or off?

-What sequence is formed by the "on" bulbs? Explain your reasoning.

[bonanova]

40,000 will be off.

First toggle they are all on.

Second toggle turns the even ones - including 40,000 off.

Third toggle affects multiples of 3 - leaving 40,000 off.

The sequence will repeat with a period of 6.

The first 6 are oooooo then o-o-o- then o---oo.

After a bit, they just look like three on, then three off.

[voider]

1. 1 is on

2. primes are off as two divisors

3. squares of primes are on as three divisors

4. squares of squares of primes are on as odd divisors

5. non-square composites (the rest) are off as even divisors

6. 40000 = 200^2 so on

7. check: 40000 has 35 divisors so on

Edited November 10, 2011 by voider

[voider]

1. 1 is on

2. primes are off as two divisors

3. squares of primes are on as three divisors

4. squares of squares of primes are on as odd divisors

5. non-square composites (the rest) are off as even divisors

6. 40000 = 200^2 so on

7. check: 40000 has 35 divisors so on

Oops correction:

4. Squares of anything are on as odd divisors.

[Guest]

I see j.green is also a car talk fan!

For those interested in the source of this puzzle (and many more in archives)

http://www.cartalk.com/content/puzzler/

This was the puzzle for last week, first aired in program of first weekend in November.

[Guest]

Every square is on (1, 4, 9, 16 etc...) and everything else is off, thus 40000 is on as the square of 200.

I built a little program to prove this hypothesis, however, I still haven't proved it mathematically, yet.

Edited November 11, 2011 by iangardner777

[Guest]

Aha! I got it! And it was so simple when I finally found the reasoning that I was excited to come back.

So, every light bulb will be hit by all of it's divisors.

So, if it is prime it will be hit by 1 and then again by itself, turning itself off.

If it is a regular number for example 12, each divisor will have a second matching divisor, i.e. 1 with 12, 2 with 6, 3 with 4; thus every time it gets flipped the matching divisor will be waiting to turn it off. Another way to say this is that almost all numbers have an even number of divisors, thus that switch will be flipped an even number of times and the last flip will then always turn that switch off.

Finally, let's take a square, for example 25. Here, 1 will pair with 25, but 5 pairs with itself, so there is no second flip. Another way to say this is that only squares have an odd number of divisors and thus only squares will be left on.

Yay!

[Guest]

Basically nth light switch is toggled as many times as the number of divisors of n.

40000=2^6.5^4

=>(6+1).(4+1)=35 divisors

=>35 toggles

=>the last light bulb remans on

[Guest]

Basically nth light switch is toggled as many times as the number of divisors of n.

40000=2^6.5^4

=>(6+1).(4+1)=35 divisors

=>35 toggles

=>the last light bulb remans on

Check out this solution

Aha! I got it! And it was so simple when I finally found the reasoning that I was excited to come back.

So, every light bulb will be hit by all of it's divisors.

So, if it is prime it will be hit by 1 and then again by itself, turning itself off.

If it is a regular number for example 12, each divisor will have a second matching divisor, i.e. 1 with 12, 2 with 6, 3 with 4; thus every time it gets flipped the matching divisor will be waiting to turn it off. Another way to say this is that almost all numbers have an even number of divisors, thus that switch will be flipped an even number of times and the last flip will then always turn that switch off.

Finally, let's take a square, for example 25. Here, 1 will pair with 25, but 5 pairs with itself, so there is no second flip. Another way to say this is that only squares have an odd number of divisors and thus only squares will be left on.

Yay!

and it becomes obvious

Since the set of lights remaining on is the sequence of perfect squares and 40000 =200^2. Hence 40000 is in the set of perfect squares and will remain turned on.

[Guest]

Got shown (well, a very similar problem to) this in my maths class today.. it's great having a teacher who also loves solving problems