Puzzles
New puzzle
Edit “light switches”
Title
Problem statement
(markdown + LaTeX)
There are $n$ lights and $n$ light switches. Each light is connected to at least one light switch, and each light switch is connected to 1 or more lights. A light is on if an odd number of light switches attached to it is odd (i.e. light switches act as XOR's on whether their lights are on or not). Prove that there always exists some setup where at least half the lights are on.
Solution
(markdown + LaTeX)
Linearity of expectations on # of lights that are on
Save changes