3. Pavel alternately writes crosses and circles into the cells of a table (starting with a cross). When the table is completely filled, the final score is calculated as the sum $X+O$, where $X$ is the number of rows containing more crosses than circles and $O$ is the number of columns containing more circles than crosses. Determine the highest possible score achievable for a table of size $(2 n+1) \times (2 n+1)$ depending on the natural number $n$.

The written part of the school round in category A takes place

## on Tuesday, December 12, 2017

so that it starts in the morning and the participants have 4 hours of pure time to solve the problems. For each problem, a participant can earn 6 points, and a successful solver is a student who scores 10 points or more. Allowed aids are writing and drawing tools and school MF tables. Calculators, laptops, and any other electronic aids are not allowed. These details will be communicated to the students before the start of the competition.
3. We want crosses to prevail in as many rows as possible and circles in as many columns as possible.

There are an odd number of cells in the table, $(2 n+1)^{2}=4 n^{2}+4 n+1$. The number of crosses in the filled table is one more than the number of circles, so there are $2 n^{2}+2 n+1$ crosses, while there are only $2 n^{2}+2 n$ circles. It is also clear that any table filled with the given numbers of crosses and circles is a result that Pavel can achieve with his method.

First, we prove that crosses cannot prevail in all rows. If crosses prevailed in every row, there would have to be at least $(2 n+1)(n+1)=2 n^{2}+3 n+1$ crosses. However, there are only $2 n^{2}+2 n+1=2 n(2 n+1)+1$ crosses in the table, so they can prevail in at most $2 n$ rows.

By the same argument, we can prove that circles can prevail in at most $2 n$ columns. The highest achievable score is therefore $2 n+2 n=4 n$.

In the second part of the solution, we prove that the score $4 n$ can be achieved for any natural number $n$. It is sufficient to place crosses in the left $n+1$ columns of the first $n$ rows, the right $n+1$ columns of the next $n$ rows, and the middle cell of the bottom row (circles will then be placed in all other cells). The situation for $n=3$ is illustrated in Fig. 3. We can easily verify that the total number of crosses is $(n+1) n+(n+1) n+1=2 n^{2}+2 n+1$, which is the correct number (so the correct number of cells is also left for circles), and that crosses prevail in all rows except the last one, while circles prevail in all columns except the middle one.

| $\times$ | $\times$ | $\times$ | $\times$ | 0 | 0 | 0 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $\times$ | $\times$ | $\times$ | $\times$ | 0 | 0 | 0 |
| $\times$ | $\times$ | $\times$ | $\times$ | 0 | 0 | 0 |
| 0 | 0 | 0 | $\times$ | $\times$ | $\times$ | $\times$ |
| 0 | 0 | 0 | $\times$ | $\times$ | $\times$ | $\times$ |
| 0 | 0 | 0 | $\times$ | $\times$ | $\times$ | $\times$ |
| 0 | 0 | 0 | $\times$ | 0 | 0 | 0 |

Fig. 3

For a complete solution, award 6 points, of which 3 points for proving that the score cannot be higher than $4 n$; 2 points for describing the filling that leads to a score of $4 n$ for any (general) $n$; 1 point for stating that the described filling contains the correct total number of crosses and circles. For an incomplete solution: 1 point for the correct answer (without justification).