Posers and Puzzles

Posers and Puzzles

  1. Joined
    04 Aug '01
    Moves
    2408
    09 May '05 04:201 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. SubscriberAThousandYoung
    iViva la Hispanidad!
    tinyurl.com/y2c6j2t3
    Joined
    23 Aug '04
    Moves
    24791
    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. Non-Sub Recs: 0
    Joined
    08 Apr '05
    Moves
    455
    09 May '05 06:48
    Originally posted by AThousandYoung
    Hmm. Dunno.
    squares?
  4. Standard memberDaemon Sin
    I'm A Mighty Pirate™
    PaTROLLING the forum
    Joined
    01 Dec '04
    Moves
    36332
    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. Joined
    04 Aug '01
    Moves
    2408
    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. Joined
    06 Apr '05
    Moves
    1133
    09 May '05 21:18
    cubes? it's an old trick!


    ...which i forget
  7. Joined
    06 Apr '05
    Moves
    1133
    09 May '05 21:23
    squares... bulbs 1, 4, 9, 25, 36, 49, 64, 81, 100, 121, 144, etc.
  8. THORNINYOURSIDE
    Joined
    04 Sep '04
    Moves
    245624
    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. Joined
    09 Feb '05
    Moves
    6175
    27 May '05 13:14
    eleven
  10. Joined
    26 Apr '03
    Moves
    26510
    27 May '05 20:421 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. Joined
    06 Apr '05
    Moves
    1133
    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. Joined
    29 Jan '05
    Moves
    3164
    28 May '05 03:45
    all perfect square numbers up to 1000
  13. Joined
    06 May '05
    Moves
    7898
    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. Joined
    06 May '05
    Moves
    7898
    06 Jun '05 11:27
    So, as 1000^0.5=31.6, 31 bulbs left on
Back to Top