Monday, 13 August 2012

Bulbs & Switches

Suppose you have 'n' lightbulbs and 'n' switches that correspond to each of the lightbulbs. Initially, all the lightbulbs are turned off. After you flip a switch, the corresponding lightbulb turns on. If you flip the same switch again, the lightbulb turns off. Each switch corresponds to only 1 lightbulb and vice versa. After 'k' random switches are flipped, what is the expected number of lightbulbs turned on?