9.1 In a $7 \times 7$ grid, several cells were marked, with at least one cell marked in each row and each column. It turned out that in any row of the grid, an even number of cells were marked, and in any column, the number of marked cells is divisible by 3. What is the smallest and largest number of cells in the grid that could have been marked?
Solution: Let's start with a lower bound estimate. By summing the number of cells in each row, we get that the total number of cells in the table is even. Summing by columns, we also get that the total number of cells is divisible by 3. Therefore, it is divisible by 6. Since the sum by columns is at least \(3 \cdot 7 = 21\) and is divisible by 6, it is at least 24.

Upper bound estimate: Notice that in each row, no more than 6 cells are marked. Therefore, the total number of marked cells is no more than 42.

Examples that achieve the two estimates are provided below.

| $\mathrm{X}$ | $\mathrm{X}$ |  |  |  | $\mathrm{X}$ | $\mathrm{X}$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $\mathrm{X}$ | $\mathrm{X}$ |  |  |  | $\mathrm{X}$ | $\mathrm{X}$ |
| $\mathrm{X}$ | $\mathrm{X}$ |  |  |  | $\mathrm{X}$ | $\mathrm{X}$ |
|  |  | $\mathrm{X}$ | $\mathrm{X}$ |  |  |  |
|  |  | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ |  |
|  |  | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ |  |
|  |  |  |  | $\mathrm{X}$ | $\mathrm{X}$ |  |


|  | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $\mathrm{X}$ |  | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ |
| $\mathrm{X}$ | $\mathrm{X}$ |  | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ |
| $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ |  | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ |
| $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ |  | $\mathrm{X}$ | $\mathrm{X}$ |
| $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ |  | $\mathrm{X}$ |
| $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ | $\mathrm{X}$ |  |

## Criteria:

- Lower bound estimate and example with 24 cells - 2 and 3 points respectively (points are cumulative);
- Upper bound estimate and example with 42 cells - 1 and 1 points respectively (points are cumulative with each other and with the previous criterion).