lyukhson wrote: In a $999 \times 999$ square table some cells are white and the remaining ones are red. Let $T$ be the number of triples $(C_1,C_2,C_3)$ of cells, the first two in the same row and the last two in the same column, with $C_1,C_3$ white and $C_2$ red. Find the maximum value $T$ can attain. I can give a hand-waving argument that I believe will produce the correct answer--but I haven't been able to make it fully rigorous yet. If we pick $C_1$ and $C_3$ at random, this can be done in $999^4$ ways. The cell $C_2$ is then uniquely determined as the cell at the intersection of $C_1$'s row and $C_3$'s column. Let $p$ be the probability that any given cell is red. So the probability that $C_2$ is red is $p$. Where some hand-waving comes in is that it seems fairly obvious that, given $C_2$, the probability of $C_1$ being white cannot be higher than $(1-p)$--that is the probability of a cell being white in the same row (or column) as a randomly selected red cell cannot be higher than the overall probability of a cell being white. Also the probability of $C_1$ being white is not correlated to the probability to the probability of $C_3$ being white. These statements seem fairly obvious but I haven't been able to prove them yet. Assuming these statements, the overall probability of $(C_1,C_2,C_3)$ being colored white, red, white is less than or equal to $p(1-p)^2$--establishing $T\le p(1-p)^{2}999^4$. $p(1-p)^2$ is maximized when $(1-p)^{2}-2p(1-p)=0$ or $p=\frac{1}{3}$, so $T\le \frac{4}{27}*999^4$. And the maximum will be attained if we repeat the following pattern $333\times 333$ times to cover the entire $999\times 999$ grid: RWW WRW WWR So the maximum possible value of $T$ is $T=\frac{4}{27}*999^4=147,556,443,852$.

12(333)^4 configuration is easy. just 3 333x333 red squares, the rest white. to prove it is the maximum, take all the red squares, say there are X. We say that column i has $c_i$ white squares, row i has $r_i$. it is easy to see $T=\sum_{red} f_ir_i$ We can do Cauchy Schwarz and prove that $x^2(999-x)$ attains its maximum at $x=666$ to prove the maximum is 12(333)^4. don't have time to write out full proof, this is a sketch.

theflowerking wrote: 12(333)^4 configuration is easy. just 3 333x333 red squares, the rest white. to prove it is the maximum, take all the red squares, say there are X. We say that column i has $c_i$ white squares, row i has $r_i$. it is easy to see $T=\sum_{red} f_ir_i$ We can do Cauchy Schwarz and prove that $x^2(999-x)$ attains its maximum at $x=666$ to prove the maximum is 12(333)^4. don't have time to write out full proof, this is a sketch. Yes I think this allows one to complete the full proof. I presume you mean: $T=\sum_{red} c_ir_i$. Then by Cauchy Schwarz $T^2=(\sum_{red} c_ir_i)^2\le (\sum_{red} c_i^2)(\sum_{red} r_i^2)$. Then $\sum_{red} c_i^2=\sum_{i=1}^{999} (999-c_i)c_i^2$. The term $(999-c_i)c_i^2$ will be maximized when $c_i=\frac{2}{3}*999$ implying $\sum_{red} c_i^2\le \sum_{i=1}^{999} \frac{4}{27}*999^3=\frac{4}{27}*999^4$. It is similarly shown that $\sum_{red} r_i^2\le \frac{4}{27}*999^4$ and hence $T\le \frac{4}{27}*999^4=12*333^4$.

If you select $C_1,C_3$ at $999^4$ ways, it means you can select the same row or column or place , so $C_2$ isn't determined exactly of is exactly the same place. Also the probabilty being $C_3$ is red doesn't change if you take it totally arbitrary. If you assume they have to be different there is a small difference. ( take a $2*2$bord with only one white, if $C_1$ is white, there is a probability of $100$ % $C_3$ is red ) Hence the solution with probalistic ideas isn't correct.

SCP wrote: If you select $C_1,C_3$ at $999^4$ ways, it means you can select the same row or column or place , so $C_2$ isn't determined exactly of is exactly the same place. In the probabilistic argument, I'm not making any effort to explicitly require that $C_1,C_2,C_3$ all be distinct cells. Rather, I'm relying on the fact that if we select $C_1$ and $C_3$ in such a way that $C_1,C_2,C_3$ do not all end up being distinct, then the problem conditions won't be met anyways--so we don't really need to deal with this as a separate case. For example, if we select $C_1$ and $C_3$ such that they are in the same row, then $C_2$ and $C_3$ will end up being the same cell. But we don't need to rule that case out explicitly because in that case it would be impossible for $C_2$ to be red and $C_3$ to be white--since they are the same cell. SCP wrote: ( take a $2*2$bord with only one white, if $C_1$ is white, there is a probability of $100$ % $C_3$ is red ) Hence the solution with probalistic ideas isn't correct. I'm not sure if you've understood my attempted argument--which I admit isn't rigorous. This example definitely doesn't disprove my argument. I'm considering two probabilities: $p_1$ which is the a priori probability of $C_1$ being white. In your example $p_1=\frac{1}{4}$. $p_2$ which is the probability of $C_1$ being white given the knowledge that $C_2$ is red. In your example, for $C_1$ to be white given that $C_2$ is red, we would first require that $C_2$ be the one of the $3$ red cells in the same row as the white (probability $\frac{1}{3}$). And then $C_1$ would need to be the one white cell of the $2$ cells in that row (probability $\frac{1}{2}$--remembering, again, that we aren't doing anything to explicitly require that $C_1$ and $C_2$ be distinct). Overall probability: $p_2=\frac{1}{3}*\frac{1}{2}=\frac{1}{6}$. Note that in your example, it turns out that $p_2<p_1$. What I'm claiming for my argument is that it will always be the case that $p_2\le p_1$. I do not claim to have proven rigorously that $p_2\le p_1$. But I do claim that your example is not a counterexample to my claim. I still suspect a full proof based on these probabilistic arguments would be possible. But it would likely be a longer, more involved proof than the argument that theflowerking sketched and I filled in the details on. Therefore I'm not feeling that motivated now to try to fill in the details on my probabilistic argument.

In general, we will prove that $\frac{4}{27} n^4$ is an upper bound for all $n \times n$ grids. We'll double count over red cells. Let $a_i$ and $b_i$ denote the number of white cells in the $i$th row and $j$th column, and let $S = \{ (i,j) \text{ red} \}$. Then \begin{align*} T &= \sum_{(i,j) \in S} a_i b_j \\ &\le \frac{1}{2} \sum_{(i,j) \in S} (a_i^2 + b_j^2) & \text{ by AM-GM} \\ &= \frac{1}{2} \sum_{i} (n-a_i)a_i^2 + \frac{1}{2} \sum_j (n-b_j) b_j^2 \\ &= \frac14 \sum_{i} (2n-2a_i) \cdot a_i \cdot a_i + \frac14 \sum_{j} (2n-2b_i) \cdot b_j \cdot b_j \\ &\le \frac14 \left( \frac{2n}{3} \right)^3 + \frac14 \left( \frac{2n}{3} \right)^3 = \frac{4}{27} n^4 & \text{ by AM-GM}. \end{align*}When $3 \mid n$, equality occurs in several situations, including the following natural ones: Three red regions of size $n/3 \times n/3$. Ryan Kim points out that $x+y \equiv 0 \pmod 3$ (so ``checkerboard coloring modulo $3$'') works well. Vincent Bian reminds me this is equivalent to the previous one under permutation of rows and columns. An important sub-problem is to look at constructions where $1/3$ is replaced by the constant $c$; this gives the answer $c = 1/3$. That means an AM-GM type inequality near the end is inevitable. The earlier AM-GM is the critical estimate that lets us split $a_i b_j$ and take the global sum. Remark: [Brandon Chen] The probabilistic method also can give some motivation in the following way. Suppose we randomly color the board red/white with red squares occurring with probability $p$. Then $\mathbb E[T] = n^2 (n-1)^2 p(1-p)^2$ which is optimized for $p = 1/3$. This means that there exists a coloring with $T \ge \frac{4}{27} n^2(n-1)^2$, which hints the importance of $p=1/3$. In addition, once we convince ourselves that $T = \frac{4}{27} n^4$ is optimal, it suggests that global double counting methods should work well; if $\mathbb E[T] = \frac{4}{27} n^4 - O(n^3)$ but $T \le \frac{4}{27} n^4$ then $T$ should stay basically the same as the random colorings vary.

Take the bipartite graph interpretation with a bipartite graph with $n=999$ vertices on each side and an edge between two vertices if their corresponding row and column intersect at a red square in the table. We wish to compute $\sum_{a-b}(n-d_a)(n-d_b)$ over all $a$ on one side with degree $d_a$ connected to $b$ on the other side with degree $d_b$. But note that $\sum_{a-b}(n-d_a)(n-d_b)\le\sum_{a-b}\left(\frac{(n-d_a)^2}2+\frac{(n-d_b)^2}2\right)$ by AM-GM. Meanwhile, we have that $\sum_{a-b}\frac{(n-d_a)^2}2=\sum_{k=1}^n\frac{d_{a_k}(n-d_{a_k})^2}2$, where $d_{a_k}$ is the degree of the $k$th vertex on the $a$ side. Note that again by AM-GM, $\frac{t(n-t)^2}2\le\frac{2n^3}{27}$, so $\sum_{a-b}\frac{(n-d_a)^2}2\le\frac{2n^4}{27}$. Similarly, $\sum_{a-b}\frac{(n-d_b)^2}2\le\frac{2n^4}{27}$, so the whole sum is at most $\frac{4n^4}{27}$. For our construction, we want all degrees to equal $\frac n3$, so we may tile the $999\time 99$ square with $3\times 3$ squares and color the three diagonal squares of each red.

This is same as the above solution. I claim the magic number is $12 \times 333^4 = \boxed{443112444}$. This is achieved (for example) when you color the cell in $i$-th row and $j$-th column red iff $\lfloor \frac{i}{333} \rfloor = \lfloor \frac{j}{333} \rfloor$. Now we prove that this is optimal. Replace $999$ by $3n$. Construct a bipartite graph $G = (R, C)$ with $R_iC_j$ ($1 \leq i,j \leq 3n$) joined iff the cell at $i$-th row and $j$-th column is colored red. Let $Q_n$ denote the quantity defined in the question. Now $$ Q_n = \sum_{(u,v) \not \in G, u \in R, v \in C} \text{deg}[u] \text{deg}[v] $$$$ \leq \sum_{(u,v) \not \in G, u \in R, v \in C}\frac{ (\text{deg}[u])^2 + (\text{deg}[v])^2 }{2} \text{ (AM-GM)} $$$$ = \sum_{u \in G}\frac{ (\text{deg}[u])^2(3n - \text{deg}[u])}{2} \text{ (Easy double counting)}$$Now note that by taking derivatives, $f(x) = x^2(3n-x)$ has maximum value $4n^2$, so $$Q_n \leq \sum_{u \in G} \frac{(\text{deg}[u])^2(3n - \text{deg}[u])}{2} \leq \sum_{u \in G} 2n^3 = |V| \cdot 2n^3 = 12n^4 $$, as desired. For this, the equality case is same - this is achieved (for example) when you color the cell in $i$-th row and $j$-th column red iff $\lfloor \frac{i}{n} \rfloor = \lfloor \frac{j}{n} \rfloor$.

We want to count the number of ways to pick a red square, and then pick a white square in its row and a white square in its column. Let $A_k$ be the number of whites in row $k$, and $B_k$ the number of whites in column $k$. Note that these two sets of variables are not completely independent. The count is \begin{align*} \sum_{\substack{1\le x,y \le 999 \\ (x,y) \text{ red}}} A_xB_y &\le \frac12 \sum_{\substack{1\le x,y \le 999 \\ (x,y) \text{ red}}} A_x^2+B_y^2 \\ &=\frac12 \sum_{\substack{1\le x,y \le 999 \\ (x,y) \text{ red}}} A_x^2 + \frac12 \sum_{\substack{1\le x,y \le 999 \\ (x,y) \text{ red}}} B_y^2. \end{align*}We have split up the $A$'s and $B$'s. The number of reds in row $x$ is $999-A_x$, and similarly the number of reds in column $y$ is $999-B_y$. The expression becomes \begin{align*} \frac12 \sum_{x=1}^{999} (999-A_x)A_x^2 + \frac12 \sum_{y=1}^{999} (999-B_y)B_y^2. \end{align*}We have \[ (999-x)x^2 = 4 \left[(999-x)\cdot \tfrac{x}{2} \cdot \tfrac{x}{2}\right] \le 4\left( \tfrac{999}{3}\right)^3\]by AM-GM. Therefore, the count is at most \[ \frac12 \cdot 999\cdot 4\left( \frac{999}{3}\right)^3 + \frac12 \cdot 999\cdot 4\left( \frac{999}{3}\right)^3 = 12\cdot 333^4.\]We achieve equality when all the bounds are equalities: we need $A_x=B_y$ for all $x,y$, and $999-A_x=\tfrac12 A_x$, i.e. $A_x=666$. So the number of whites in each row and each column is 666. This is achieved by splitting the $999\times 999$ grid into 9 $333\times 333$ sub-grids, and making the 3 diagonal sub-grids red.

This was rather straightforward for a $C3$

The answer is $\frac{4\cdot 999^2}{27}$. Replace $999$ by $n$. Define $r_1,r_2,...,r_n$ and $c_1,c_2,...,c_n$ be the number of red cells in each row and column. Notice that \begin{align*} T&=\sum_{(i,j)\text{ red }}(n-r_i)(n-c_j)\\ &=\sum_{i=1}^n\frac{r_i+c_i}{2}n^2-(\sum_{i=1}^n(r_i^2+c_i^2)n)+\sum_{(i,j)\text{red}}r_ic_j\\ &\sum_{i=1}^n\frac{r_i+c_i}{2}n^2-\sum_{i=1}^n(r_i^2+c_i^2)n+\frac{r_i^3+c_i^3}{2}\\ &=\frac{1}{2}\sum_{i=1}^nr_i(n-r_i)^2+c_i(n-c_i)^2\\ &=2\sum_{i=1}^nr_i\left(\frac{n-r_i}{2}\right)^2+c_i\left(\frac{n-c_i}{2}\right)^2\\ &\leq 2\cdot2\cdot\frac{1}{3}^3\cdot n^3\cdot n\\ &=\frac{4n^2}{27} \end{align*} On the other hand, letting $r_i=c_i=333$ it is easy to see that all the inequalites become equalities, so $T=\frac{4\cdot999^2}{27}$ if the cells are $(i,i),...,(i+332)$ for all $1\leq i\leq 999$.

Let $r_i$ and $c_i$ denote the number of white cells in row $i$ and column $i,$ respectively. Note that over all red cells, $$T = \sum_{i,j} r_ic_i \le \sum_{i,j} \frac{r_i^2+c_i^2}{2} = \frac{1}{2}\sum_{i=1}^{999} r_i^2(999-r_i) + c_i^2(999-c_i).$$Note that taking the derivative of $f(x) = x^2(999-x)$ and evaluating critical points in $[0,999]$ gives $f(x)$ is maximized when $x=666.$ As a result, $$T\le \frac{2\cdot 999 \cdot666^2\cdot 333}{2} = 999\cdot 333 \cdot 666^2.$$Indeed, equality occurs by coloring the three $333\times 333$ subgrids of $1\le i,j\le 333,$ $334\le i,j\le 666,$ $667\le i,j \le 999$ red.

Let $a_n$ be the number of white cells in row $n$ and $b_n$ the number of white cells in column $n$. Note that, by AM-GM, $xy\le\frac12(x^2+y^2)$ and: $$(999-x)x^2=4\cdot(999-x)\cdot\frac x2\cdot\frac x2\le4\left(\frac{(999-x)+\frac x2+\frac x2}3\right)^3=147704148$$so: \begin{align*} T&\le\sum_{(i,j)\text{ red}}a_ib_j\\ &\le\frac12\sum_{(i,j)\text{ red}}(a_i^2+b_j^2)\\ &=\frac12\sum_{(i,j)\text{ red}}a_i^2+\frac12\sum_{(i,j)\text{ red}}b_j^2\\ &=\frac12\sum_{i=1}^{999}(999-a_i)a_i^2+\frac12\sum_{j=1}^{999}(999-b_j)b_j^2\\ &\le\frac12\sum_{i=1}^{999}(999-a_i)147704148+\frac12\sum_{j=1}^{999}147704148\\ &=147556443852 \end{align*}Equality is attained when the table is divided into $9$ squares and only the squares on the main diagonal are red.

The answer is $T \leq 12\cdot 333^4$. As a construction, number the rows/columns in the obvious way and color $(x,y)$ red iff $x \equiv y \pmod{3}$, so we have $999\cdot 333$ red cells to pick for $C_2$ and each one has $666$ choices for each of $C_1$ and $C_3$. It remains to prove the bound. First, note that $(A-x)x^2 \leq \tfrac{4A^3}{27}$, which is true because $$A=\frac{(A-x)+\frac{x}{2}+\frac{x}{2}}{3} \underset{\text{AM-GM}}{\geq} \sqrt[3]{\frac{(A-x)x^2}{4}}.$$Now suppose that there are $r_i$ white cells in row $i$ and $c_i$ white cells in row $i$. Then $$T=\sum_{(i,j)\text{ red}} r_ic_j \implies T^2=\left(\sum_{(i,j)\text{ red}} r_ic_j\right)^2 \leq \left(\sum_{(i,j)\text{ red}} r_i^2\right)\left(\sum_{(i,j)\text{ red}} c_j^2\right)$$by Cauchy-Schwarz. Since row $i$ gets counted $999-r_i$ times, we have $$\sum_{(i,j)\text{ red}} r_i^2=\sum_{i=1}^{999} (999-r_i)r_i^2 \leq \sum_{i=1}^{999}\frac{4}{27}\cdot 999^3=12\cdot 333^4.$$Likewise, $\sum_{(i,j)\text{ red}} r_i^2 \leq 12\cdot 333^4$, hence $T^2 \leq (12\cdot 333^4)^2 \implies T \leq 12 \cdot 333^4$, which is the desired bound. $\blacksquare$

Set $n=333.$ We claim that the answer is $12n^4.$ Construction: split the $3n\times 3n$ table into nine $n\times n$ grids. Along the diagonal, put three grids as all red, and everything else blue. It is clear that $T=12n^4.$ $~$ Consider any red and the row and column it is in and color the white ones in the same row pink and the white ones in the same column magenta. Note that this triple (pink, red, magenta) will be counted by $T$ so the number of triples containing that particular red one will be the number of whites in the same row times the number of reds in the same row. $~$ Let row $i$ have $r_i$ whites, and column $j$ have $c_j$, and our answer is \[\sum_{(i,j)\text{ is red}}r_ic_j\]Note that \[2\sum_{(i,j)\text{ is red}}r_ic_j\le \sum_{(i,j)\text{ is red}}r_i^2+\sum_{(i,j)\text{ is red}}c_i^2\le \sum(3n-r_i)r_i^2+\sum(3n-c_i)c_i^2\le 2(n\cdot (2n)^2)(3n)=24n^4\]so our claim is proved.

We consider the general $3n\times 3n$ case. We claim that the answer is, in general, $12n^4$. This is clearly achieved if we tile the entire grid with $3\times 3$s of the form: \[\begin{bmatrix} R & W & W\\ W & R & W\\ W & W & R \end{bmatrix}\]which has $3n^2$ reds, each of which has $2n\times 2n = 4n^2$ pairs of adjacent whites. We now prove that this is optimal. Let $\mathcal{R}$ be the set of $(x,y)$ coordinates of all red cells. Let $r_x$ be the number of white cells in row $x$ and $c_y$ be the number of white cells in column $y$. Then, clearly each red cells contributes $r_x c_y$ to $T$, which taken all together gives: \[T = \sum_{(r,c)\in \mathcal{R}} r_xc_y \leq \sum_{(r,c)\in \mathcal{R}} \frac12 (r_x^2+c_y^2) = \frac12 \sum_{x=1}^{3n} (3n-r_x)r_x^2 + \frac12 \sum_{y=1}^{3n} (3n-c_y)c_y^2\]However, note that $(3n-r_x) \cdot r_x^2 = 4\cdot (3n-r_x) \cdot (\frac12 r_x) \cdot (\frac12 r_x) \leq 4\cdot n^3$, so \[T\leq 2\cdot \frac12 \cdot 3n \cdot 4n^3 = 12n^3\]and we're done. $\blacksquare$.

The answer in general is \frac4{27}n^4 in nxn grids, using global techniques. Take x_k,y_k the number of white cells with x-coordinate i and y-coordinate i, respectively (with the usual assignation of first column has x coordinate 1, etc.), and take R the set of red cells with coordinates i,j. Then T=\sum_{(i,j)\in R}x_iy_j\le\frac12\sum_{\ldots}x_i^2+y_j^2=\frac12(\sum(n-x_i)x_i^2+\sum(n-y_i)y_i^2\stackrel{\text{AM-GM}}{\le}\frac{4}{27}n^4; plugging in 999 gives the answer.

We claim that in general, if $999$ is replaced with $3k$, then the answer is $12k^4$. Note that the quanitity is equal to $$\sum_{red}(\text{white in row})(\text{white in column}).$$ The value of $12k^4$ is achieved with a configuration that has exactly $k$ red cells in each row and each column, as it would give a value of $$(3k)(k)(2k)^2=12k^4,$$since each of the $3k^2$ red cells has a value of $(2k)^2$ in the above sum. Now, for the bound, we have $$\sum_{red}(\text{white in row})(\text{white in column})\leq \sum_{red}\frac{1}{2}((\text{white in row})^2+(\text{white in column})^2)$$ $$=\frac{1}{2}(\sum_{red}(\text{white in row})^2 + \sum_{red}(\text{white in column})^2).$$ Now, consider the sum $$\sum_{red}(\text{white in row})^2.$$If a row has $r$ red cells and $3k-r$ white cells, then the row contributes $r(3k-r)^2$ to this sum. By Weighted AM-GM, we have $$r(3k-r)^2\leq k(2k)^2=4k^3,$$so each row contributes at most $4k^3$ to this sum. Hence, we have $$\sum_{red}(\text{white in row})^2\leq 12k^4.$$Similarly, $$\sum_{red}(\text{white in column})^2\leq 12k^4,$$which means that $$=\frac{1}{2}(\sum_{red}(\text{white in row})^2 + \sum_{red}(\text{white in column})^2)\leq 12k^4,$$as desired

$\color{magenta}\boxed {\textbf{SOLUTION C3}}$ Let, In a $n\times n$ grid there are $a_i, b_j$ white squares in $i$th row and $j$th column respectively. So, there are $(n-a_i)$ red cells in $i$th row and $(n-b_j)$ red cells in $j$th column. Let $S = \{ (i,j) \text{ red} \}$ $$T=\sum_{(i,j) \in S} a_ib_j \le \frac{1}{2} \sum_{(i,j) \in S} a_i^{2} + b_j^{2}= \frac{1}{2} \sum_{i=1}^{n} (n-a_i)a_i^2 + \frac{1}{2} \sum_{j=1}^{n} (n-b_j) b_j^2$$ And, $$\frac{1}{2} \sum_{i=1}^{n} (n-a_i)a_i^2=\frac{1}{4} \sum_{i=1}^{n} (2n-2a_i)a_i.a_i \le \frac{n}{4} \cdot (\frac{2n}{3})^3 = \frac{2n^4}{27}$$$$\frac{1}{2} \sum_{j=1}^{n} (n-b_j)b_j^2= \frac{1}{4} \sum_{j=1}^{n} (2n-2b_j)b_j.b_j \le \frac{n}{4} \cdot (\frac{2n}{3})^3 = \frac{2n^4}{27}$$Hence, $T\le \frac{2n^4}{27}+ \frac{2n^4}{27} = \frac{4n^4}{27}$ Equality holds if and only if $a_i=b_j=\frac{2n}{3}$ For, $n=999$, there are $666$ white squares in each row and column. So, the maximum value of $T$ is $T=\frac{4\cdot 999^4}{27}$