1000 Light Bulbs

Suppose you have 1000 light bulbs which are lined up in a row, numbered from 1 to 1000. Each bulb has it's own ON/OFF toggle switch, and initially, all bulbs are in the OFF state.

Suppose you then perform the following: you first toggle all bulbs which are multiples of 1; then you toggle all bulbs that are multiples of 2; then you do the same for all bulbs that are multiples of 3; etc. You do this all the way through multiples of 1000.

Upon completion of this toggling exercise, which light bulbs are in the ON state?

EDIT: To be clear, by "toggle" I mean that you simply change the state of the bulb once (from ON to OFF or from OFF to ON).

Originally posted by davegage
Suppose you have 1000 light bulbs which are lined up in a row, numbered from 1 to 1000. Each bulb has it's own ON/OFF toggle switch, and initially, all bulbs are in the OFF state.

Suppose you then perform the following: you first toggle all bulbs which are multiples of 1; then you toggle all bulbs that are multiples of 2; then you do the same for all b ...[text shortened]... e" I mean that you simply change the state of the bulb once (from ON to OFF or from OFF to ON).

Hmm. Dunno.

Originally posted by AThousandYoung
Hmm. Dunno.

squares?

Originally posted by davegage
Suppose you have 1000 light bulbs which are lined up in a row, numbered from 1 to 1000. Each bulb has it's own ON/OFF toggle switch, and initially, all bulbs are in the OFF state.

Suppose you then perform the following: you first toggle all bulbs which are multiples of 1; then you toggle all bulbs that are multiples of 2; then you do the same for all b ...[text shortened]... e" I mean that you simply change the state of the bulb once (from ON to OFF or from OFF to ON).

First toggle: All bulbs are ON
Second toggle: All even numbered bulbs OFF, all odd bulbs ON
Third toggle: All even mutiples of 3 are ON, all other numbers are OFF

Originally posted by Daemon Sin
First toggle: All bulbs are ON
Second toggle: All even numbered bulbs OFF, all odd bulbs ON
Third toggle: All even mutiples of 3 are ON, all other numbers are OFF

Keep going...only 997 more toggle operations to sift through.

You may want to take a different, faster approach though. 😀

cubes? it's an old trick!


...which i forget

squares... bulbs 1, 4, 9, 25, 36, 49, 64, 81, 100, 121, 144, etc.

Originally posted by davegage
Suppose you have 1000 light bulbs which are lined up in a row, numbered from 1 to 1000. Each bulb has it's own ON/OFF toggle switch, and initially, all bulbs are in the OFF state.

Suppose you then perform the following: you first toggle all bulbs which are multiples of 1; then you toggle all bulbs that are multiples of 2; then you do the same for all b ...[text shortened]... e" I mean that you simply change the state of the bulb once (from ON to OFF or from OFF to ON).

None will be on as they have all blown with all the toggling!

eleven

Originally posted by davegage
Suppose you have 1000 light bulbs which are lined up in a row, numbered from 1 to 1000. Each bulb has it's own ON/OFF toggle switch, and initially, all bulbs are in the OFF state.

Suppose you then perform the following: you first togg ...[text shortened]... nge the state of the bulb once (from ON to OFF or from OFF to ON).

Bulbs with an odd number of factors will be on

Each number which is a multiple of n primes (not including 1 as a prime) has X factors, where X is the number of ways of selecting 0..n items from n (we go from 0 because 1 is a factor but is not conventionally included in the n primes). It is not too hard to show that this is the sum of the numbers in row n of pascals triangle

The sum of the numbers in any row of pascals triangle, except the first row (row 0) is an power of 2, so all numbers except 2^0=1 have an even number of factors

So only bulb 1 remains on.

Originally posted by iamatiger
Bulbs with an odd number of factors will be on

Each number which is a multiple of n primes (not including 1 as a prime) has X factors, where X is the number of ways of selecting 0..n items from n (we go from 0 because 1 is a factor but is not conventionally included in the n primes). It is not too hard to show that this is the sum of the numbers in row ...[text shortened]... r of 2, so all numbers except 2^0=1 have an even number of factors

So only bulb 1 remains on.

wrong... like i said before, it'll be only squares.

Try starting with the same thing but only ten bulbs. numbers one, nine and 4 will be on, and they're squares.

1st time: 1,2,3,4,5,6,7,8,9,10 are on, _____ is off.
2nd time: 1,3,5,7,9 are on, 2,4,6,8,10 are off.
3rd time: 1,5,6,7 are on, 2,3,4,8,9,10 are off.

Note that 2 and 3 will NEVER turn on because the numbers that toggle them (multiples of one and 2/3) have already been used.

4th time: 1,4,5,6,7,8 are on, 2,3,9,10 are off.
5th time: 1,4,6,7,8,10 are on, 2,3,5,9 are off.

Now note that the number 5 will always be off, whereas 1 and 4 will always be on because the numbers that toggle them have also already been used.

i think i spoiled it...

all perfect square numbers up to 1000

Saying 'bulbs with an odd number of factors' and 'bulbs which are square numbers' refer to the same bulbs.

This is because factors split into pairs (e.g. 1+12, 2+6, 3+4 for 12) meaning a number always has an even number of factors unless it is a square number as the 'pair' for e.g. 16, is 4+4 which is only 1 factor.

So the total number of factors which are not square roots of a number is even, if a number is a perfect square then that is one more factor making an odd number of factors and leaving the bulb switched on.

So yes perfect squares is correct

So, as 1000^0.5=31.6, 31 bulbs left on