Problem 1410

The answer is $\left[\frac{2^{n+1}-5}{3}\right]$.

Let us assign to the $i$-th light bulb the number $2^{|i-n|}$ and define the value of a configuration as the sum of the numbers on the lit bulbs. The value of the initial configuration is $1$, and with each step it increases by a natural multiple of the number $3$. A step increases the value by exactly $3$ if the $n$-th bulb changes state; we call such a step good.

Since the value cannot exceed $2^{n+1}-4$ (because it is not possible for all the bulbs to be lit), it is not possible to perform more than $\left[\frac{2^{n+1}-5}{3}\right]$ steps. This number can be attained: it suffices to show that it is possible to perform at least $\frac{2^{n+1}-7}{3}$ steps.

We will prove by induction on $n$ that, starting from a configuration of value at most $3$, we can, by a sequence of good steps, obtain a configuration of value at least $2^{n+1}-6$. This is directly checked for $n \leqslant 2$. Let $n \geqslant 3$. By the induction hypothesis for $n-1$, it is possible to reach a configuration of value at least $2^{n}-6$ with the first and last bulb off. In such a configuration, besides the first and last bulb, the bulbs that may be off are

$(1^{\circ})$ only the $n$-th,

$(2^{\circ})$ only the $n$-th and one of its neighbors, or

$(3)$ only one of two neighboring ones.

In each of these three cases, in at most three good steps we achieve that the first and last bulb become lit and that the value of the remainder of the configuration (without these two bulbs) is at most $3$.

$(1^{\circ})$

$(2^{\circ})$

$(3^{\circ})$

Applying the induction hypothesis for $n-1$ once more completes the induction.