Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 09 May '05 04:20 / 1 edit
    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).
  2. Subscriber AThousandYoung
    It's about respect
    09 May '05 05:24
    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.
  3. 09 May '05 06:48
    Originally posted by AThousandYoung
    Hmm. Dunno.
    squares?
  4. Standard member Daemon Sin
    I'm A Mighty Pirateā„¢
    09 May '05 09:59
    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
  5. 09 May '05 18:39
    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.
  6. 09 May '05 21:18
    cubes? it's an old trick!


    ...which i forget
  7. 09 May '05 21:23
    squares... bulbs 1, 4, 9, 25, 36, 49, 64, 81, 100, 121, 144, etc.
  8. 27 May '05 11:44
    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!
  9. 27 May '05 13:14
    eleven
  10. 27 May '05 20:42 / 1 edit
    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.
  11. 28 May '05 01:20
    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...
  12. 28 May '05 03:45
    all perfect square numbers up to 1000
  13. 06 Jun '05 11:24
    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
  14. 06 Jun '05 11:27
    So, as 1000^0.5=31.6, 31 bulbs left on