3. There are $2 n-1$ light bulbs in a row. Initially, the middle ($n$-th) one is on, and all the others are off. In one step, it is allowed to choose two non-adjacent off bulbs between which all bulbs are on, and change the state of those two bulbs, as well as all the bulbs between them (for example, from the configuration $\cdot$ооо $\cdot$ we get о $\cdot$ $\cdot$). What is the maximum number of steps that can be performed?

(Dushan Dukic)

## Ministry of Education, Science and Technological Development Mathematical Society of Serbia  11th SERBIAN MATHEMATICAL OLYMPIAD FOR HIGH SCHOOL STUDENTS
3. The answer is $\left[\frac{2^{n+1}-5}{3}\right]$.

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

Since the value cannot exceed $2^{n+1}-4$ (since all lights cannot be lit), it is not possible to perform more than $\left[\frac{2^{n+1}-5}{3}\right]$ steps. This number can be achieved: it is sufficient 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 obtain a configuration of value at least $2^{n+1}-6$ by a sequence of good steps. This can be directly verified for $n \leqslant 2$. Let $n \geqslant 3$. By the inductive hypothesis for $n-1$, it is possible to reach a configuration of value at least $2^{n}-6$ with the first and last light off. In such a configuration, apart from the first and last light, the following can be off: (1) only the $n$-th, (2) only the $n$-th and one of its neighbors, or (3) only one of the two neighbors. In each of these three cases, in at most three good steps, we can achieve that the first and last lights are on and that the value of the rest of the configuration (excluding these two lights) is at most 3.

![](https://cdn.mathpix.com/cropped/2024_06_04_5a6e83cb5d39ea537491g-4.jpg?height=223&width=348&top_left_y=1559&top_left_x=360)

$\left(1^{\circ}\right)$

![](https://cdn.mathpix.com/cropped/2024_06_04_5a6e83cb5d39ea537491g-4.jpg?height=291&width=357&top_left_y=1556&top_left_x=864)

$\left(2^{\circ}\right)$

![](https://cdn.mathpix.com/cropped/2024_06_04_5a6e83cb5d39ea537491g-4.jpg?height=229&width=369&top_left_y=1556&top_left_x=1369)

$\left(3^{\circ}\right)$

Reapplying the inductive hypothesis for $n-1$ completes the induction.