Question 84
A row of $n$ lamps is labelled from left to right with the numbers $1$ to $n$, where $n$ is an *odd* positive integer. Each lamp has a switch which, if pressed, turns it from OFF to ON or from ON to OFF; however the switches may only be pressed according to the following rules:
(a) Switch 1 may be pressed at any time;
(b) Switch $k \in \{2, \dots, n\}$ may be pressed if and only if lamp $(k-1)$ is ON and all lamps $l \lt (k-1)$ (if any) are OFF.
Initially all lamps are ON. Prove that the minimum number of times the switches must be pressed to turn all the lamps OFF is
$$
\frac{2^{n+1} - 1}{3}
$$
(a) Switch 1 may be pressed at any time;
(b) Switch $k \in \{2, \dots, n\}$ may be pressed if and only if lamp $(k-1)$ is ON and all lamps $l \lt (k-1)$ (if any) are OFF.
Initially all lamps are ON. Prove that the minimum number of times the switches must be pressed to turn all the lamps OFF is
$$
\frac{2^{n+1} - 1}{3}
$$