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 odd 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: Lower bound: In each column, either 3 or 6 cells are marked, so there are at least $3 \cdot 7=21$ marked cells in total.

Upper bound: Summing the number of marked cells by rows, we get that the total number of marked cells is odd, while summing by columns gives that it is divisible by 3. Since in each column no more than 6 cells out of 7 are marked, the total number of marked cells is at most 42. The largest odd multiple of 3 not exceeding 42 is 39, and there are no more than this number of marked cells in the table.

Examples implementing the two bounds 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}$ |

## Criteria:

- Lower bound and example with 21 cells - 1 point each (points are cumulative);
- Upper bound and example with 39 cells - 2 points each (points are cumulative with each other and with the previous criterion).