There is a strip $1 \times 99$, divided into 99 cells $1 \times 1$, which are alternately painted in black and white. It is allowed to repaint simultaneously all cells of any rectangular cell $1 \times k$. What is the minimum number of repaintings required to make the entire strip monochromatic?

#
Each repainting destroys no more than two borders between cells of different colors.

## Solution

Estimate. Let's call a bridge an segment separating two cells of different colors. Initially, we have 98 bridges. Each repainting changes the number of bridges by no more than 2. Therefore, 48 repaintings are not enough.

Algorithm. We will repaint all cells from the second to the 98th, then all cells from the third to the 97th, ..., and finally, one 50th cell. After this, the strip will become monochromatic.

## Answer

In 49 repaintings.