
3. Paul is filling the cells of a rectangular table alternately with crosses and circles (he starts with a cross). When the table is filled in completely, he determines his score as $X+O$ where $X$ is the number of rows containing more crosses than than circles and $O$ is the number of columns containing more circles than crosses. In terms of $n$, what is the largest possible score Paul can achieve for a $(2 n+1) \times(2 n+1)$ table?

(Josef Tkadlec)


Solution. In total there are $2 n(n+1)+1<(2 n+1)(n+1)$ crosses and $2 n(n+1)$ circles. Hence the crosses can dominate in at most $2 n$ rows and, similarly, circles can dominate in at most $2 n$ columns for the total score $2 n+2 n=4 n$.

Such a score can be achieved if, for example, Paul draws crosses in the left $n+1$ columns of the first $n$ rows, the right $n+1$ columns of the last $n$ rows and the middle cell of the middle row. That is precisely $2 n(n+1)+1$ crosses and we easily check that crosses dominate in all rows except for the middle one while circles dominate in all columns except for the middle one.

![](https://cdn.mathpix.com/cropped/2024_04_17_c0cc9d17594ecfc50dfag-09.jpg?height=480&width=485&top_left_y=1485&top_left_x=754)

Fig. 3

## Second Round of the 67th Czech and Slovak Mathematical Olympiad (January 16th, 2018)

$\mathbb{N} / /(2)$
