We claim that the answer is $(n-1)(3n-2) = 3n^2 - 5n + 2.$ This can be achieved as follows. Label the rows $1, 2, \cdots, n$ from top to bottom. Let all squares in even-numbered rows be black and all odd-numbered rows be white. This is easily checked to attain the desired bound of $3n^2 - 5n + 2.$ Let's now show that this is optimal. Observe that the sum of all of the numbers in question is simply the number of pairs of white and black squares of the $n \times n$ which share a vertex. For a vertex of one of the squares of the $n \times n$ which isn't on the table's perimeter, define the pocket of that vertex as follows. It is the set of the unordered pairs of distinct unit squares which contain that vertex. In particular, each pocket has cardinality six and contains at least two unordered pairs of similarly-colored unit squares. Let's label the $n^2$ squares of the $n \times n$ with the elements of $[n]^2$ in the obvious manner, with the lower-left unit square being labelled with $(1, 1).$ Consider some positive integer $2 \le i < 2n,$ and let $S_i$ denote the set of unit squares $(x, y)$ so that $x+y \in \{i, i+1\}.$ We will define the $i-$slash to be the set of unordered pairs of diagonally adjacent elements of $S_i$ in addition to $((1, i-1), (1, i))$ and $((i-1, 1), (i, 1))$ if $i \le n$ and $((n, i-n), (n, i+1-n))$ and $((i-n, n), (i+1-n, n))$ if $i > n$. Define the $i-$gash to be the set of unordered pairs of unit squares of $n \times n$ which correspond to reflections of those in the $i-$slash across a vertical axis of symmetry of the $n \times n$ square. Observe that every $i-$slash contains an odd number of unordered pairs of elements of $S_i$ which correspond to an "odd cycle," which means that at least one pair of squares in the $i-$slash is comprised of two similarly-colored squares. An analogous observation holds for $i-$gashes. Now, consider the multiset which consists of the union of two copies of all pockets of all vertices (so $2(n-1)^2$ pockets in total), all $i-$gashes for $2 \le i < 2n$, and all $i-$slashes for $2 \le i < 2n.$ By our previous progress, it must contain at least $2(n-1)^2 \cdot 2 + 2(2n-2)$ unordered pairs of similarly-colored squares. However, observe that this multiset in fact simply consists of four copies of all unordered pairs of unit squares sharing a vertex, of which there are $(n-1)(4n-2)$ in total. Hence, at least $\frac14 \cdot (2(n-1)^2 \cdot 2 + 2(2n-2)) = n(n-1)$ unordered pairs of similarly-colored squares exist among these $(n-1)(4n-2)$ pairs. Therefore, there exist at most $(n-1)(4n-2) - n(n-1) = (n-1)(3n-2)$ unordered pairs of differently-colored squares in total, which proves optimality. $\square$

We’ll prove that there are at least $n(n-1)$ pairs of monochromatic adjacent (=having common point) squares, with equality if rows are colored alternatively, which will suffice. Call a pair of squares with a common side a domino, and call a domino boundary if it both of its squares are on the boundary. Call a pair of squares with a common vertex but not side a diagonal. We see that every $2\times2$ square has at least two monochromatic pairs, and summing for every $2\times2$ square we get $$\#(\text{boundary monochromatic dominoes})+\#(\text{monochromatic diagonals})+2\#(\text{non-boundary monochromatic dominoes})\geq2(n-1)^2$$So it suffices to prove that $$\#(\text{boundary monochromatic dominoes})+\#(\text{monochromatic diagonals})\geq2(n-1)$$Call the sets of squares $(x,y)$ of the kind $x+y=a$ or $x-y=a$ great diagonal. Consider any two adjacent great diagonals (two diagonals $x+y=a$ and $x+y=a+1$ or $x-y=a$ and $x-y=a+1$). These two great diagonals contain two boundary dominoes; since numbers of squares in these diagonals have different parities, either one of these dominoes is monochromatic, or one of great diagonals has a monochromatic diagonal. Summing this for all $4(n-1)$ pairs of adjacent diagonals, we see that every boundary domino is counted twice, and every diagonal is counted at most twice, so we're done.

Here is a shockingly simple solution communicated to me by Mark Khasin (apparently it was found by one of contestants during the test). Note that each blue triangle contains at least one monochromatic pair, and each yellow square contains at least two monochromatic pairs, so there are at least $n(n-1)$ of them, as desired. [asy][asy] size(10cm); for(int x=0; x<8; ++x){ draw((-0.5,x-0.5)--(6.5,x-0.5)); draw((x-0.5,-0.5)--(x-0.5,6.5)); } for(int x=0; x<6; ++x){ fill((x,x)--(x,x+1)--(x+1,x+1)--(x+1,x)--cycle, yellow); for(int y=x+1; y<6; ++y){ fill((x,y)--(x,y+1)--(x+1,y+1)--cycle, royalblue); fill((y,x)--(y+1,x)--(y+1,x+1)--cycle, royalblue); } } [/asy][/asy]

Nice solution. One of the Kazakhstan's gold medalist solved this problem by the similar idea

Another Solution: First, we define two simple graphs $G$ and $H$. Definition of graph $G$: $G$ has $n^2$ vertices, and every vertex of $G$ corresponds to the center of one of the $n^2$ squares available in our $n*n$ square. ( This is why $G$ has $n^2$ vertices. ) Now, two vertices of $G$ are adjacent if the two squares to which they correspond, have a common vertex with each other and that they have different colors. ( One of them is white and the other black. ) Definition of graph $H$: $H$ has $(n-1)^2$ vertices. In our $n*n$ square, we can find $(n-1)^2$ $2*2$ subsquares. Each vertex of $H$ corresponds to the center of one these $(n-1)^2$ subsquares. Now, two vertices $X,Y$ of $H$ are adjacent if : 1) among those four squares to which each of $X,Y$ correspond, two of them are equal. (In other words, if we assume that the length of the sides of each of our $n^2$ squares is $1$, then the distance of $X,Y$ should be $2$.) 2) The centers of each of the two squares to which both of $X,Y$ correspond, are adjacent to each other in graph $G$. What happens to the problem: In fact, we want to find the maximum number of edges in graph $G$. Before we move forward, we define \(a_i,b_i\) for \(1\leq i\leq (n-1)^2\). \(a_i\) means the number of edges in the induced subgraph of four vertices $A,B,C,D$ of $G$, the four of which are contained in one of the $(n-1)^2$ possible $2*2$ subsquares. Then, in that same $2*2$ subsquare, we must have a vertex $E$ in graph $H$. (due to the definition of $H$.) \(b_i\) means the number of edges adjacent to vertex $E$ which do not go outside of our $n*n$ square. (Particularly, this is no different from the degree of $E$. ). Claim1: The number of edges of $G$ equals $\sum_{i=1}^{(n-1)^2} a_i-\frac{b_i}{2}$. Proof: This is easy, as those edges that are counted twice in $\sum_{i=1}^{(n-1)^2} a_i$ are counted once as an edge in graph $H$ and this is equal to $\sum_{i=1}^{(n-1)^2} \frac{b_i}{2}$. (In fact, one can easily see that there is a one-on-one correspondence between edges in $G$ that are counted twice in $\sum_{i=1}^{(n-1)^2} a_i$ and the edges of $H$.) Claim2: For each $i$, $a_i-\frac{b_i}{2}$ attains its maximum when among those four squares, two squares next to each other are black and the other two white. (Exclude the case where there are two diametrically opposite black (respectively, white) squares.) Additionally, this value is either $\frac{7}{2}$ or $3$. Proof: Casework. (21 cases...) ( In fact, they generally give either $\frac{7}{2}$ or $3$ or $\frac{5}{2}$ or $2$ or $\frac{3}{2}$ as far as I can remember. ) From these two claims, we understand that the edges of $G$ increase if we try to constantly use those types of $2*2$ subsquares which have two black squares next to each other and two white squares next to each other. If we color all rows ( or columns ) in black,white,black.... or white,black,white,... order, we see that we are constantly using those good types of $2*2$ subsquares and an easy induction gives us a total of $3n^2-5n+2$ edges. We can see that in this case, $2n-4$ squares do not achieve their maximum ( they contribute $3$ to our sum instead of $\frac{7}{2}$ ) so in order to finish the proof, we will prove that any kind of white/black coloring of our $n^2$ cells give us a reduction of at least $n-2=\frac{2n-4}{2}$ from the highest possible sum. We will prove this in the next paragraph. A strip means some $1*1$ squares so that every two consecutive squares have a side of a square in common. Define $2n-4$ strips of $1*1$ squares where the two ends of these strips are either: 1) The $j-th$ square on the top side of our $n*n$ square and the $j-th$ square on the left side of our $n*n$ square. 2) The $j-th$ square on the right side of our initial square and the $j-th$ square on the bottom side of our square. ($2\leq j \leq n-1$ in both cases.) Here, we have constructed our strips in a way that we first constantly move to the left and then, upwards in case 1) or move constantly upwards and then rightwards in case 2) in order to connect the two ends of our strips. One can easily check that not all of the $1*1$ squares in a strip can contribute their highest value to our sum. Each of these strips either reduces at least $\frac{1}{2}$ from the highest sum they can give. ( And this happens only when one of the two END squares in our strip cannot produce the highest sum.) or reduces at least $1$ from its highest sum ( And this happens when the two end squares produce the highest sum but one square in the MIDDLE of the way doesn't give the highest value; and this reduces at least $1$ if one carefully looks at those $21$ cases.) What might happen is that two of our strips have a common $1*1$ square in the middle of their way and we might have counted a $1$ reduction twice, but this isn't a problem, since if the square at the intersection reduces at least $1$ from our sum, we can break this into two $\frac{1}{2}$ reductions and give one $\frac{1}{2}$ reduction to each of our strips. Therefore, on average, each strip reduces a $\frac{1}{2}$ from our sum and we are done.

Is this problem not the same as counting maximum of sum of number in minesweeper field? Such problem was in Belarusian Math Olympias some years ago

The answer is $(n-1)(3n-2)$, with equality achieved when the all square in a row are the same color, and the rows are alternating black and white. It suffices now to show that the sum is at most $(n-1)(3n-2)$. Clearly, the sum of all the numbers is the number of pairs of adjacent squares that are opposite colors (here adjacent squares means they share a common vertex). Call a pair of adjacent squares a link, and call a link good if it has opposite colors. Call a link straight if it connects two squares that are either horizontally or vertically adjacent, and call a link diagonal if it connects squares that share only one vertex. Label the grid squares $(i,j)$ where $i$ and $j$ range through $\{1,2,\ldots,n\}$. The key idea is to cover the grid with pieces in the following way: $n-1$ $2\times 2$ squares with corners at $(a,a)$ and $(a+1,a+1)$. For each $(i,j)$ with $i<j$, the $L$-shaped piece consisting of $(i,j)$, $(i,j-1)$, and $(i+1,j)$. For each $(i,j)$ with $i>j$, the $L$-shaped piece consisting of $(i,j)$, $(i,j+1)$, and $(i-1,j)$. It is easy to see that all links are in exactly one piece, except $(n-1)(n-2)$ NE links that are in no pieces. We see that a square can have at most $4$ good links, and each $L$-piece can have at most $2$ good links, so the total number of good links is at most \[4(n-1)+2(n-1)(n-2)+(n-1)(n-2) = (n-1)(2n-3),\]as desired. Remark: For reference, I originally tried to solve the problem with the pieces as overlapping $2\times 2$ blocks. This approach almost works, but the edges of the grid completely ruin it and make it very difficult to complete. The failed solution is below in hide tags just so that I don't feel like I wasted the couple hours I spent trying that approach

The answer is $(n-1)(3n-2)$, achieved by letting even numbered rows colored black and odd numbered rows colored white. To prove the bound, note that it suffices to show that there are $n(n-1)$ pairs of cells of the same color sharing at least one common vertex. Define an edge as a line connecting any two cells sharing at least one common vertex. An edge is called special if both endpoints have the same color. Moreover, the edges are classified to two types: type A if it connects either two diagonally adjacent cells, or it connects two cells on the border of the grid; and type B otherwise. Claim. At least $2(n-1)$ edges of type A are special. Proof. There are $4(n-1)$ odd cycles containing only type A edges. As shown below are the example for $n=6$. [asy][asy] size(9cm); defaultpen(fontsize(10pt)); filldraw((-6,6)--(-6,5)--(-5,6)--cycle,green); filldraw((-6,4)--(-6,3)--(-3,6)--(-4,6)--cycle,green); filldraw((-6,2)--(-6,1)--(-1,6)--(-2,6)--cycle,green); filldraw((-5,1)--(-4,1)--(-1,4)--(-1,5)--cycle,green); filldraw((-3,1)--(-2,1)--(-1,2)--(-1,3)--cycle,green); filldraw((-6,5)--(-6,4)--(-4,6)--(-5,6)--cycle,yellow); filldraw((-6,3)--(-6,2)--(-2,6)--(-3,6)--cycle,yellow); filldraw((-6,1)--(-5,1)--(-1,5)--(-1,6)--cycle,yellow); filldraw((-4,1)--(-3,1)--(-1,3)--(-1,4)--cycle,yellow); filldraw((-2,1)--(-1,1)--(-1,2)--cycle,yellow); for(int i=1; i<=7; i+=1){ draw((-i+0.5,0.5)--(-i+0.5,6.5),gray); draw((-0.5,i-0.5)--(-6.5,i-0.5),gray); } for(int i=1; i<=6; i+=1){ for(int j=1; j<=6; j+=1){ dot((-i,j)); } } filldraw((6,6)--(6,5)--(5,6)--cycle,green); filldraw((6,4)--(6,3)--(3,6)--(4,6)--cycle,green); filldraw((6,2)--(6,1)--(1,6)--(2,6)--cycle,green); filldraw((5,1)--(4,1)--(1,4)--(1,5)--cycle,green); filldraw((3,1)--(2,1)--(1,2)--(1,3)--cycle,green); filldraw((6,5)--(6,4)--(4,6)--(5,6)--cycle,yellow); filldraw((6,3)--(6,2)--(2,6)--(3,6)--cycle,yellow); filldraw((6,1)--(5,1)--(1,5)--(1,6)--cycle,yellow); filldraw((4,1)--(3,1)--(1,3)--(1,4)--cycle,yellow); filldraw((2,1)--(1,1)--(1,2)--cycle,yellow); for(int i=0; i<=6; i+=1){ draw((i+0.5,0.5)--(i+0.5,6.5),gray); draw((0.5,i+0.5)--(6.5,i+0.5),gray); } for(int i=1; i<=6; i+=1){ for(int j=1; j<=6; j+=1){ dot((i,j)); } } [/asy][/asy] Observe that each cycle has at least one special edge, while each edge is a part of exactly $2$ cycles. Hence the number of special edges of type A is at least $\tfrac{4(n-1)}{2}=2(n-1)$. $\blacksquare$ Now, we will finish by double counting. Let $a,b$ denote the number of special edges of type A and B. (Thus $a\geq 2(n-1)$.) The key idea is to count triangles, define as a cycle in form $(i,j)\to (i,j\pm 1)\to (i\pm 1, j)$ (considering all four sign choices). We count the number $N$ of pairs $(e,t)$–where $e$ is a special edge, $t$ is a triangle, and $e$ is a side of $t$–in two ways. Each triangle has at least one special edge. Since there are $4(n-1)^2$ triangles, we get $N\geq 4(n-1)^2$. However, each edge of type A is a part of two triangles, while each edge of type B is a part of four triagles. Hence $N=2a+4b$. Thus, $$2a+4b\geq 4(n-1)^2 \implies a+b \geq \frac{4(n-1)^2 + 4(n-1)}{4} = n(n-1)$$

Ouch. I claim that our answer is $(n-1)(3n-2)$, which can be obtained by allowing every even numbered row to be colored black. Check that when $n = 2m$ is even, we get a total sum of\[(3n - 2) + (m-1)(6n - 4) = (2m-1)(3n-2) = (n-1)(3n-2)\]and when $n = 2m+1$ is odd, we get a total sum of\[2(3n-2) + (m-1)(6n-4) = 2m(3n-2) = n-1(3n-2)\]as well, so this construction unconditionally works. As for the bound, we consider the $(n+1)^2$ grid intersection points. If two opposite colored squares touch at a single vertex, then we add a weight of $1$ to that vertex. If two opposite colored squares touch at a side, then we add a weight of $\tfrac12$ to each of the two vertices in the adjacent side. It is easy to see that the sum of all the $(n+1)^2$ weights is the sum of the numbers in all the white squares. Note that the four corner points must have weight $0$, and the $4(n-1)$ side points must each have weight at most $\tfrac12$. For each of the $(n-1)^2$ central points, we consider the following cases: [asy][asy] for (int i =0; i <= 1; i += 1) for (int j = 0; j <= 1; j += 1) { filldraw((i-0.5,j-0.5)--(i-0.5,j+0.5)--(i+0.5,j+0.5)--(i+0.5,j-0.5)--cycle, white); } [/asy][/asy] [asy][asy] for (int i =0; i <= 1; i += 1) for (int j = 0; j <= 1; j += 1) { filldraw((i-0.5,j-0.5)--(i-0.5,j+0.5)--(i+0.5,j+0.5)--(i+0.5,j-0.5)--cycle, white); } filldraw((0-0.5,0-0.5)--(0-0.5,0+0.5)--(0+0.5,0+0.5)--(0+0.5,0-0.5)--cycle, black); [/asy][/asy] [asy][asy] for (int i =0; i <= 1; i += 1) for (int j = 0; j <= 1; j += 1) { filldraw((i-0.5,j-0.5)--(i-0.5,j+0.5)--(i+0.5,j+0.5)--(i+0.5,j-0.5)--cycle, white); } filldraw((0-0.5,0-0.5)--(0-0.5,0+0.5)--(0+0.5,0+0.5)--(0+0.5,0-0.5)--cycle, black); filldraw((0-0.5,1-0.5)--(0-0.5,1+0.5)--(0+0.5,1+0.5)--(0+0.5,1-0.5)--cycle, black); [/asy][/asy] [asy][asy] for (int i =0; i <= 1; i += 1) for (int j = 0; j <= 1; j += 1) { filldraw((i-0.5,j-0.5)--(i-0.5,j+0.5)--(i+0.5,j+0.5)--(i+0.5,j-0.5)--cycle, white); } filldraw((1-0.5,0-0.5)--(1-0.5,0+0.5)--(1+0.5,0+0.5)--(1+0.5,0-0.5)--cycle, black); filldraw((0-0.5,1-0.5)--(0-0.5,1+0.5)--(0+0.5,1+0.5)--(0+0.5,1-0.5)--cycle, black); [/asy][/asy] [asy][asy] for (int i =0; i <= 1; i += 1) for (int j = 0; j <= 1; j += 1) { filldraw((i-0.5,j-0.5)--(i-0.5,j+0.5)--(i+0.5,j+0.5)--(i+0.5,j-0.5)--cycle, black); } filldraw((0-0.5,0-0.5)--(0-0.5,0+0.5)--(0+0.5,0+0.5)--(0+0.5,0-0.5)--cycle, white); [/asy][/asy] [asy][asy] for (int i =0; i <= 1; i += 1) for (int j = 0; j <= 1; j += 1) { filldraw((i-0.5,j-0.5)--(i-0.5,j+0.5)--(i+0.5,j+0.5)--(i+0.5,j-0.5)--cycle, black); } [/asy][/asy] and we see that the maximum possible weight of the centerpoint is $3$. Hence, a pretty loose upper bound of the final sum would be\[4 \cdot 0 + 4(n-1) \cdot \frac12 + 3 \cdot (n-1)^2 = (3n-1)(n-1).\]However, note that if point $(0, i)$ has nonzero weight, then point $(i, 0)$ cannot have nonzero weight so in fact at most half of the $4(n-1)$ border but non-corner points can have nonzero weight so we subtract $2(n-1)\tfrac12$ hence indeed, we have achieved our desired bound of $(3n-2)(n-1)$. $\blacksquare$

jj_ca888 wrote: However, note that if point $(0, i)$ has nonzero weight, then point $(i, 0)$ cannot have nonzero weight so in fact at most half of the $4(n-1)$ Why? You can choose the squares on the boundary intercally and you will get that all points on the boundary have weight 1/2 (of course it doesn't get the maximum number)

yayups wrote: The answer is $(n-1)(3n-2)$, with equality achieved when the all square in a row are the same color, and the rows are alternating black and white. It suffices now to show that the sum is at most $(n-1)(3n-2)$. Clearly, the sum of all the numbers is the number of pairs of adjacent squares that are opposite colors (here adjacent squares means they share a common vertex). Call a pair of adjacent squares a link, and call a link good if it has opposite colors. Call a link straight if it connects two squares that are either horizontally or vertically adjacent, and call a link diagonal if it connects squares that share only one vertex. Label the grid squares $(i,j)$ where $i$ and $j$ range through $\{1,2,\ldots,n\}$. The key idea is to cover the grid with pieces in the following way: $n-1$ $2\times 2$ squares with corners at $(a,a)$ and $(a+1,a+1)$. For each $(i,j)$ with $i<j$, the $L$-shaped piece consisting of $(i,j)$, $(i,j-1)$, and $(i+1,j)$. For each $(i,j)$ with $i>j$, the $L$-shaped piece consisting of $(i,j)$, $(i,j+1)$, and $(i-1,j)$. It is easy to see that all links are in exactly one piece, except $(n-1)(n-2)$ NE links that are in no pieces. We see that a square can have at most $4$ good links, and each $L$-piece can have at most $2$ good links, so the total number of good links is at most \[4(n-1)+2(n-1)(n-2)+(n-1)(n-2) = (n-1)(2n-3),\]as desired. Remark: For reference, I originally tried to solve the problem with the pieces as overlapping $2\times 2$ blocks. This approach almost works, but the edges of the grid completely ruin it and make it very difficult to complete. The failed solution is below in hide tags just so that I don't feel like I wasted the couple hours I spent trying that approach

Wow!Such a nice solution! How do you get the source of the idea?