Back to Archive
#58discrete
medium

Light Bulbs in circle

Source: P. Winkler

In a circle are light bulbs numbered 1 through n, all initially on. At time t, you examine bulb number t, and if it’s on, you change the state of bulb t + 1 (modulo n); i.e., you turn it off if it’s on, and on if it’s off. If bulb t is off, you do nothing. Prove that if you continue around and around the ring in this manner, eventually all the bulbs will again be on.

Discussion

0

You must be logged in to participate in the discussion.

No comments yet. Be the first to start the conversation!