Petya colored one cell of the rectangle. Sasha can color other cells of this rectangle according to the following rule: any cell can be colored if it has an odd number of colored neighbors (by side). Will Sasha be able to color all the cells of the rectangle (regardless of which cell Petya chose), if the size of the rectangle is a) $8 \times 9$ cells? b) $8 \times 10$ cells?
a) First, we will color a row of 9 cells, containing the initially colored cell (see the first figure). Then we will paint every other column, starting the coloring from the painted row (see the second figure). After this, coloring the remaining cells of the board is quite simple.
![](https://cdn.mathpix.com/cropped/2024_05_06_49e49f22191b45b40a57g-32.jpg?height=434&width=1008&top_left_y=1092&top_left_x=526)

Comment. This method of coloring generalizes to the case where at least one of the sides of the rectangle has an odd length. We rotate the rectangle so that its width is odd, and then repeat the procedure just described: paint a row of odd length, and so on.

b) First method. Let's look at the semi-perimeter of the figure consisting of the colored cells. Initially, when one cell is colored, the semi-perimeter is 2. On each step, the semi-perimeter either increases by 1 (if the cell had only one adjacent colored cell) or decreases by 1 (if there were 3 such neighbors), meaning the semi-perimeter increases or decreases by 1. Therefore, when an even number of cells are colored, the semi-perimeter of the colored figure is odd. Note that the semi-perimeter of the entire $8 \times 10$ rectangle is 18, which is even, so the entire rectangle cannot be colored.

Second method. We will prove that for even $\mathrm{m}$ and $\mathrm{n}$, the $\mathrm{m} \times \mathrm{n}$ rectangle cannot be colored regardless of the initial colored cell. Let's count the total number of sides of the cells (including external sides). The number of sides of the cells is $\mathrm{m}(\mathrm{n}+1)+\mathrm{n}(\mathrm{m}+1)=2 \mathrm{mn}+\mathrm{m}+\mathrm{n}$, which is an even number. Suppose we managed to color the entire rectangle. We will call a side colored if at least one of the adjacent cells is colored. Initially, 4 sides are colored. On each step, 1 or 3 sides are colored. In total, we need to make $\mathrm{nm}-1$ such steps. Since $\mathrm{m}$ and $\mathrm{n}$ are even, the number $\mathrm{nm}-1$ is odd. Therefore, if we managed to color the entire rectangle, there would be 4 + (an odd number of times an odd number) sides colored, which is an odd number, but as we have already calculated, there are an even number of such sides, so the entire rectangle cannot be colored.

## Answer

a) Yes; b) No.