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).

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).