67th Czech and Slovak Mathematical Olympiad

Question

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 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)

Accepted Answer

In total there are 2n(n+1)+1 < (2n+1)(n+1) crosses and 2n(n+1) circles. Hence the crosses can dominate in at most 2n rows and, similarly, circles can dominate in at most 2n columns for the total score 2n+2n=4n. 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 2n(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. FIGURE_0 Fig. 3