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 davegageHmm. Dunno.
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).
Originally posted by davegageFirst toggle: All bulbs are ON
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
Originally posted by Daemon SinKeep going...only 997 more toggle operations to sift through.
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. 😀
Originally posted by davegageNone will be on as they have all blown with all the toggling!
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).
- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by davegageBulbs with an odd number of factors will be on
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.
Originally posted by iamatigerwrong... like i said before, it'll be only squares.
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...
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