3. There are $2 n-1$ bulbs in a line. Initially, the central ( $n$-th) bulb is on, whereas all others are off. A step consists of choosing a string of at least three (consecutive) bulbs, the leftmost and rightmost ones being off and all between them being on, and changing the states of all bulbs in the string (for instance, the configuration $\bullet \circ \circ \circ \bullet$ will turn into $\circ \bullet \bullet \bullet \circ)$. At most how many steps can be performed?

(Dušan Djukić)

Time allowed: 270 minutes. Each problem is worth 7 points.

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

Assign to the $i$-th bulb the number $2^{|i-n|}$ and define the value of a configuration as the sum of numbers assigned to the bulbs that are on. The initial configuration has value 1. With each step, the value increases by a multiple of 3 . If a step switches the $n$-th bulb, the value increases by exactly 3 ; we call such steps good.

Since the value cannot exceed $2^{n+1}-4$ (for not all bulbs can be on), one cannot make more than $\left[\frac{2^{n+1}-5}{3}\right]$ steps. In order to show that this number can be attained, it suffices to show that at least $\frac{2^{n+1}-7}{3}$ good steps can be made.

We prove by induction on $n$ that, starting with a configuration of value at most 3 , we can reach a configuration of value at least $2^{n+1}-6$ by a sequence of good steps. For $n \leqslant 2$ this is directly verified. Let $n \geqslant 3$. By the inductive hypothesis for $n-1$, it is possible to reach a configuration with the first and last bulb off, and value at least $2^{n}-6$. In such a configuration, other than the outer two, the bulbs that are off can be $\left(1^{\circ}\right)$ only the $n$-th, $\left(2^{\circ}\right)$ only the $n$-th and an adjacent one, or $\left(3^{\circ}\right)$ only one bulb adjacent to the $n$-th. In each of these three cases, in at most three good steps we reach a configuration in which the two outer bulbs are on and the value of the rest of the configuration (not counting these two) is at most 3 .

![](https://cdn.mathpix.com/cropped/2024_06_04_31a83bcaa45a5783e6aeg-08.jpg?height=358&width=1437&top_left_y=1881&top_left_x=173)

Now we can apply the inductive hypothesis for $n-1$ again, finishing the induction.