I heard that induction or smoothing work. But here is a short solution I found during the contest.

The perfect question for dieters.

Answer and construction. The answer is \[ \frac{n^3 - n}{3} = n \cdot (n-1) + (n-1) \cdot (n-2) + \dots + 2 \cdot 1 + 1 \cdot 0 \]which is achieved by taking a black staircase. Let's in general annotate the $i$'th cell $C_i$ on the diagonal with the ordered pair $(a_i, b_i)$; so the optimum for $n=6$ is drawn below. [asy][asy] size(6cm); for (int i=0; i<=5; ++i) { for (int j=0; i+j<5; ++j) { filldraw(shift(i,j)*unitsquare, rgb(0.8,0.8,0.8), black+1.2); } } for (int i=0; i<=6; ++i) { draw((0,i)--(6,i), black+1.2); draw((i,0)--(i,6), black+1.2); } label("$(6,5)$", (0.5,5.5), red); label("$(5,4)$", (1.5,4.5), red); label("$(4,3)$", (2.5,3.5), red); label("$(3,2)$", (3.5,2.5), red); label("$(2,1)$", (4.5,1.5), red); label("$(1,0)$", (5.5,0.5), red); [/asy][/asy] Proof of optimality. By induction on $n$. For $n=1$ there is nothing to prove. Now in general, take a board achieving the maximal value. Let's assume without loss of generality that \[ a_1 = \max(a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n). \]We now do several operations which do not decrease the sum $\sum_i a_i b_i$. Then in the top row, we can change any white cells in column $1$, other than $C_1$, from white to black. If we do this to the $i$'th cell ($i \ge 2$), then $a_i$ decreases by $1$ while $b_1$ increases by $1$, giving a net change of $a_1 - b_i \ge 0$. Thus we may as well assume we are in situation where all cells below $C_1$ are black. Thus we have $b_1 \ge n-1$. Now, in the top row, we may similarly change every black cell other than $C_1$ to white. When we change the $i$'th cell, we change the sum by $b_1 - a_i = (n-1) - a_i \ge 0$. (We have $a_i \neq n$ because all cells below $C_1$ are black.) Thus in the updated board, we have a situation where $\{a_1, b_1\} = \{n-1, n\}$; other than $C_1$, the first column is entirely black and the first row is entirely white. [asy][asy] size(6cm); for (int i=0; i<=5; ++i) { filldraw(shift(0,i)*unitsquare, rgb(0.8,0.8,0.8), black+1.2); } fill(box( (1,0), (6,5)), paleyellow); for (int i=0; i<=6; ++i) { draw((0,i)--(6,i), black+1.2); draw((i,0)--(i,6), black+1.2); } label("$C_1$", (0.5,5.5), red); [/asy][/asy] At this point we may delete the first row and column. This leaves an $(n-1) \times (n-1)$ board and it does not change any of the numbers. So induction now solves the problem. Remark: The construction we gave is by no means unique. For example, in our given construction, any of the $C_i$ could change color without changing the sum. As a stranger example, here is a different construction for $n=3$. [asy][asy] size(3cm); fill(shift(0,0)*unitsquare, rgb(0.8,0.8,0.8)); fill(shift(1,0)*unitsquare, rgb(0.8,0.8,0.8)); fill(shift(0,1)*unitsquare, rgb(0.8,0.8,0.8)); fill(shift(1,2)*unitsquare, rgb(0.8,0.8,0.8)); for (int i=0; i<=3; ++i) { draw((0,i)--(3,i), black+1.2); draw((i,0)--(i,3), black+1.2); } label("$(2,2)$", (0.5,2.5), red); label("$(2,2)$", (1.5,1.5), red); label("$(1,0)$", (2.5,0.5), red); [/asy][/asy]

If you think you can rearrange, then rearrange. In particular, WE GONNA USE THE REARRANGEMENT INEQUALITY. First, let's talk about a few terms from grid theory. Consider some grid $G$ and call the ordered list of the number of black cells in each column its column list. Similarly, call the ordered list of the number of white cells in each row is its row list. We call two graphs isomorphic if the column lists and row lists are permutations of each other. This is denoted by $\sim$, which can be checked to be an equivalence relation. Now, we also call a grid $G$ top-heavy if the row lists and column lists are nondecreasing. We have the following key proposition: Proposition. Any grid $G$ is isomorphic to a top-heavy grid $G'$. Proof. We note that switching any two columns doesn't change the order of the row list, and switching any two rows doesn't change the order of the column list. Further note that the grid formed by these is isomorphic to $G$. We proceed algorithmically, pretending the row and column are two separate aspects (as they can be treated as two separate aspects). We shall sort this by induction (prove that we can sort the first $k$ columns in at most $k$ switches): Base Case. $k=1$. This follows by switching the largest column with the first column. Induction Hypothesis. Assume it is true for some $1\leq k-1\leq n-1$. Then it is also true for $k$. Induction Step. Note that we only need to make sure that the $k$th column is the maximum of the remaining, which can be done by the algorithm in the Base Case. $\blacksquare$ By repeating this for the rows, we find the isomorphic top-heavy graph $G'$. $\square$ Now, the reason we use top-heavy graphs is the following proposition. Let $S(G)=\sum_{i=1}^na_ib_i$ as defined in the problem statement: Proposition. Suppose top-heavy grid $G~G'$ a regular grid. Then $S(G)\geq S(G')$. Proof. Note that if the column list and row lists of $G$ are $a_1\geq a_2\geq\cdots\geq a_n$ and $b_1\geq b_2\geq\cdots\geq b_n$, then the row and column lists of $G'$ are $a_{\sigma(1)},a_{\sigma(2)},\ldots,a_{\sigma(n)}$ and $a_{\tau(1)},a_{\tau(2)},\ldots,a_{\tau(n)}$. The result now follows from using the said Rearrangement Inequality. $\square$ Thus, we can finish this problem off by simply considering top-heavy grids. We shall proceed by induction on $n$ (that the answer is $2\binom{n+1}3$): Base Case. $n=1$. The only two possible grids $G$ are the black and white square, and in both cases, $S(G)=2\binom{n+1}3=0$. Induction Hypothesis. Assume that for any grid of size $n-1$, $S(G)\leq 2\binom{n}3$. We demonstrate this result for $n$. Induction Step. Suppose that the row list of $G$ was $a_1\geq a_2\geq\cdots\geq a_n$ and the column list of $G$ was $b_1\geq b_2\geq\cdots\geq b_n$. Then, we shall demonstrate that it is in our best interest to maximize $a_1$. Note that changing the first value in the $k$th column (other than the first) adds a value of $a_1-a_k$, which is increasing. We can do a similar operation on the row, getting that it is in our interest to maximize $a_1$ and $b_1$. However, these sum to $2n-1$ and each have maximum value $n$, so thus we get that $a_1=n$ and $b_1=n-1$ (or the other way around). This means that in the best case, we only add $n^2-n$. Noting that $n^2-n=2\binom n2$, we get that $S(G)\leq 2\left(\binom n2+\binom n3\right)=2\binom{n+1}3$, completing the induction.

Remark: First nice problem i've in quite some time... Rearrange the columns so that the number of black squares is each column nonincreasing from left to right. We see that this does nothing to the number of white squares in each row. Now, we rearrange the rows so that the number of white squares in each row is nonincreasing from top to bottom. This does nothing to the number of black squares in each column. So if we label the rows and columns $1 \to n$ from top to bottom and left to right, respectively, by Rearrangement Inequality, after the previously described moves, the value of $\sum a_ib_i$ is at least it's previous value. Furthermore, note that swapping a white square with a black square to the right of it will result in the desired value nondecreasing, because by assumption of ordering $b_i > b_j$ iff $i > j$. Hence, we keep performing this operation on rows until all black squares accumulate on the left of each row. We get this sort of Young's Tableaux looking thing with black squares. Now we show with induction how to maximize $\sum a_ib_i$ for the previously described reduced configurations. Notice that to maximize we must have the first row entirely white and the first column almost entirely black, with the exception of the overlap with the first row. Then, since these are already maximized, we may delete these two and reduce to a $(n-1) \times (n-1)$ grid. Then, since for each $k$ by $k$ grid, we are actually adding $k(k-1)$ to $\sum a_ib_i$ each time we reduce to a smaller grid, our final answer is\[n \cdot (n-1) + (n-1)\cdot (n-2) + \ldots + 2 \cdot 1\]which upon doubling and hockey stick yields $2\tbinom{n+1}{3}$ which is our desired answer. A valid construction would be a staircase, found in the posts of many others above. $\blacksquare$

Does someone know a solution that estimates the product white×white+black×black in the corresponding row and column using the fact that sum of white in the columns ×black in corrisponding rows is equal to the sum of white in row ×black in colums?

https://artofproblemsolving.com/community/c6h1975937p13711497 Umm are these two problems equivalent? Same optimal arrangement, same solution, also solvable via smoothing.

Call $(i,j,k) $ valid if $A_{ij}=1,A_{ki}=0.$ It is not possible that $i=j=k. $ For $(i,j,k) $ off the diagonal, at most one of the following $3$ off-diagonal and distinct point $\{(i,j,k)\,,(k,j,i)\,,(j,k,i)\}$ is valid. Hence the total number of valid points is at most $\frac {(n^3-n)}{3}. $ This can be achieved by setting $A_{ij}=1$ iff $i\ge\,j. $

Let $S=\sum a_ib_i$. Treat black cells as blocks and white cells as open space. Perform the following operations that do not decrease $S$: WLOG rearrange the columns so that $\textbf{b}$ is weakly decreasing. By Rearrangement Inequality, $S$ is maximized when $\textbf{a}$ is also weakly decreasing, so permute the rows to make nondecreasing. Example: \[ \begin{array}{c||c|c|c|c|c|} \hline 5&X&X&&X& \\ \hline 4&X&X&X&&\\ \hline 3&X&&X&&X \\ \hline 2&X&X&&& \\ \hline 1&&&X&& \\ \hline \hline &1&2&3&4&5 \end{array}\]\[ \textbf{a} = (4,3,2,2,2), \ \textbf{b}=(4,3,3,1,1). \] Push each block leftwards (toward column 1) as far as possible in each row. This does not change $\textbf{a}$, but now each 1 in $\textbf{b}$ is moved and is dot-producted with a larger number. (In the example, moving the $(5,3)$ black cell left by 1 changes \[\textbf{b} = (4,3,3,1,1) \to (4,3,3,2,0), \]which has a larger dot product with $\textbf{a}$.) Now we have reduced to the case of a Young Tableuax grid with the columns based on the top. We claim $S\le \tfrac{n^3-n}{3}$. Induct on $n$, $n=1$ trivial. Note that $a_1,b_1\le n$, but they cannot both be $n$ since the $(1,1)$ square is either white or black. Hence $\{a_1,b_1\}=\{n,n-1\}$ is optimal, and it is achievable by having the first row all white and the first column on top of the $(1,1)$ square all black. Then by induction, \[ S \le n(n-1) + \tfrac{(n-1)^3-(n-1)}{3} = \tfrac{n^3-n}{3},\]finishing the induction. Equality is achieved with a staircase: $\textbf{a}=(n,\ldots,1)$ and $\textbf{b}=(n-1,\ldots,1)$.

The answer is $\tfrac{n^3-n}{3}=n(n-1)+(n-1)(n-2)+\cdots+2(1)+1(0)$, which is achieved with the same staircase thing everyone else did. To prove that this is maximal, we use induction on $n$, with the base case of $n=1$ being trivial. For the inductive step, WLOG assume that $a_1\geq a_2,\ldots,a_n,b_1,\ldots,b_n$. Label the cells $(\text{row}, \text{column})$ and perform following "smoothing" operation: if some $(j,i)$ is black and row $j$ contains at least one white cell $(j,k)$, then flip the colors of $(j,i)$ and $(j,k)$. This increases the sum by $a_1$ and decreases the sum by $a_k$, which is a net (nonstrict) increase. Note that this operation may break the fact that $a_1 \geq b_1,\ldots,b_n$, but the fact that $a_1 \geq a_2,\ldots,a_n$ is preserved, which is all that matters. After we repeat this operation until we cannot anymore, we either end up with the entirety of column 1 being black (so $b_1=n$, which occurs if $a_1<n$, or we have $a_1=n$. These two cases are actually symmetrical, so WLOG the first one holds. In this case, since $b_1\geq a_1,\ldots,a_n,b_2,\ldots,b_n$, we can swap any black cell $(i,j)$ with $j \neq 1$ to white, which increases the sum by $b_1=n$ and decreases it by $a_j$, for a net increase. Further, since $b_1$ doesn't change, this operation preserves the inequality. Once we are done with this, we end up with row $1$ being all white and column $1$ being all black, with $(1,1)$ colored arbitrarily, so $a_1b_1=n(n-1)$. Since the white cells on row $1$ don't contribute at all to $b_i$ for $i>1$, and the symmetrical statement applies to the black cells on column $1$, it follows that by deleting row and column $1$ we can reduce to the $(n-1) \times (n-1)$ grid, so we're done. $\blacksquare$ Remark: An interesting way of getting the intuition for the answer is that rearrangement should sort of dictate that if $a_i$ is large, then so is $b_i$, leading us to believe that the staircase construction which achieves this is correct.

Cool problem The answer is $2\binom{n+1}{3}$, which can be obtained by coloring everything below the main diagonal black. Call the summation the "value" of a configuration. To prove that no greater value can be achieved, first shuffle the rows and columns so that from top to bottom, the number of white squares in each row is in decreasing order. Suppose that we have an optimal configuration Claim: There is a construction with at least equal value having the property that there is no black cell that's in the same row as a white cell, but to the right of some white cell. Proof: Suppose that row $i$ contains a white cell in column $j$ and a black cell in column $k$ with $j<k$. Swapping them changes the sum by $a_j-a_k$, which is nonnegative as the rows are sorted. Now, assume that each row only contains black cells to the left of white cells. Claim: There is no white cell below the main diagonal. Proof: Consider any bottommost white cell below the main diagonal in row $x$, column $y$. If we re-color it to black, the value is changed by at least $(n-y)+1-(n-x)$, which is positive and contradicts optimality. By a similar argument, there is no black cell above the main diagonal; then, it is obvious that $a_ib_i=(n+1-i)(n-i)=2\binom{n+1-i}{2}$, Summing this gives the desired.

Very cool local problem. The answer is $2 \tbinom{n+1}{3}$, attained by coloring the staircase underneath the diagonal black, which sets \[ (a_i, b_i)=(n+1-i, n-i). \]In order to show that this is optimal, we induct on $n$. We ``smooth" a general configuration into a Young tableau via the following process. Rearrange the rows and columns so that they are weakly decreasing, and note that the value of $\small\sum a_ib_i$ does not decrease per the rearrangement inequality. Repeatedly switch a white square and black square in a row such that the white square is on the left side of the black square, which eventually results in a Young tableau. Again note that $\small\sum a_ib_i$ does not decrease per the rearrangement inequality. We proceed by induction on $n$. The base case $n=1$ is trivially true, as we would then have $a_1b_1=0$. For the inductive step, delete the Young tableau $\{n, 1, 1, \ldots, 1\}$ with $n$ rows. Then the resulting configuration (which is the $n-1$ case) has a $\small\sum a_ib_i$ of at most $n(n-1)$ less, and we conclude by inducting down. Remark: The notion of inducting on grids by generalizing to Young tableaux is a very useful trick, and is also utilized in Shortlist 2017 C8.

The answer is $$2{n+1\choose 3}=0\cdot 1+1\cdot 2\dots+(n-1)n.$$ This is achieved by having everything on or above the main diagonal be $1$s and everything below be $0$s. Call a configuration $\emph{optimal}$ if it achieves the largest possible value. Claim: There exists an optimal configuration with a row having all $1$s or a column having all $0$s. Suppose no such configuration exists, take an optimal configuration. Next to each row, write the number of $1$s, and next to each column write the number of $0$s. Take one of the maximum labels, WLOG say it's the first row. Then, converting the entire first column other than the top left into $0$s does not decrease the value of the configuration, since $a_1$ is maximum. This is still an optimal configuration. The first column now has a value of $n-1$, which under our assumption is a maximum. Thus, repeat the same argument to convert the first row (other than the top left) to $1$s, retaining optimality. In this configuration, the top row is all $1$s except for possibly the top left, the left column is all $0$s except for possibly the top left. Thus we have shown the claim. Furthermore, the full 1 row/full 0 column is obviously a maximal one, so apply the same process again to convert the corresponding row or column to the other color as well. Thus, one row is full 1s, and one column is full 0s other than the one tile it shares. Thus, $f(n)\leq n(n-1)+f(n-1)$, and by induction we are done as the answer for $n=1$ is clearly $0$.