45th Mongolian Mathematical Olympiad

The table cells are represented by the graph's vertices. We connect adjacent cells, corresponding to edges between graph vertices.

For example, we illustrate the $3\times 4$ table in the figure.



If a square has a ball, we color it black; if a square is empty, we color it white.

Then, the sum of the numbers in all empty squares is equal to the number of edges in the table's graph that connect vertices of opposite colors (i.e., edges between black and white vertices).

So, the problem reduces to coloring the $17\times 42$ table's graph with two colors to maximize the number of edges between vertices of opposite colors.

Lemma: In a graph of squares colored with two colors, the number of edges connecting vertices of opposite colors is less than $3$ per vertex for a certain type of graph, and less than $4$ per vertex for another type. (This lemma holds for square graphs.)

Proof. By coloring all possibilities for four vertices in the graph, we can verify the lemma. For the last graph, with only one type of coloring, the number of edges connecting opposite colors is exactly $4$.

Corollary: $$\{\begin{array}{l}\square \\ \square \\ ⋮\\ \square \end{array}$$

a) For a graph with $2n$ vertices colored with two colors, the maximum number of edges connecting vertices of opposite colors is $3n-2$.

$$\{\begin{array}{l}\square \\ \square \\ ⋮\\ \square \end{array}\underset{n}{\underbrace{\square \cdots \square }}$$

b) For another type of graph, the maximum number of edges connecting vertices of opposite colors is $6n-8$.

Proof a) In the above graph, we can assume it is the union of two types of graphs: one with a single square and $n-2$ squares. By the lemma, this graph has at most $4+3(n-2)=3n-2$ edges connecting opposite colored vertices.

b) In this graph, we can assume it is the union of two types of graphs: one with a single $⊞$ graph and $n-2$ $⊞$ graphs. By the lemma, this graph has at most $4+6(n-2)=6n-8$ edges connecting opposite colored vertices.

Now, solve the problem. The $17\times 42$ table's graph is the union of $42-17=25$ graphs.



Consider the $17\times 17$ square graph. By the corollary part a), for $25$ graphs, the total number of edges connecting opposite colored vertices is less than $25\cdot (3\cdot 17-2)=1225$.

Assume that the $17\times 17$ square's graph is the union of the graphs in the figure. Then, by corollary part b), we have: $$(6\cdot 17-8)+(6\cdot 16-8)+\cdots +(6\cdot 2-8)=6\cdot 152-8\cdot 16=784.$$

Hence, the $17\times 42$ table's graph has at most $1225+784=2009$ edges connecting opposite colored vertices.

If we color the vertices in odd-numbered columns black and even-numbered columns white, then the number of edges connecting opposite colors is $2009$.