- 09 May '05 04:20 / 1 editSuppose 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). - 09 May '05 05:24

Hmm. Dunno.*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). - 09 May '05 09:59

First toggle: All bulbs are 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).

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 - 09 May '05 18:39

Keep going...only 997 more toggle operations to sift through.*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

You may want to take a different, faster approach though. - 27 May '05 11:44

None will be on as they have all blown with all the toggling!*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). - 27 May '05 20:42 / 1 edit

Bulbs with an odd number of factors will be 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 togg ...[text shortened]... nge the state of the bulb once (from ON to OFF or from OFF to 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. - 28 May '05 01:20

wrong... like i said before, it'll be only squares.*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.

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... - 06 Jun '05 11:24Saying '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