Not all are red

Algebra Level 4

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$ and $C_3$ white and $C_2$ red.

The maximum value $T$ can attain is

$\large\ \frac { a { \times 999 }^{ a } }{ b }$ , where $a, b$ are natural numbers.

Find $a + b$

The answer is 31.

1 solution

Patrick Corn
Mar 15, 2018

Divide the table into nine $333 \times 333$ blocks. Color the top left, middle, and bottom right blocks red. Then there are $3 \times 333 \times 333$ red squares, each with $666 \times 666$ possibilities for $(C_1,C_3).$ So in this case $T = 3 \times 333 \times 333 \times 666 \times 666 = \frac{4 \times 999^4}{27}.$ I am not sure how to prove that this gives the maximum value of $T.$

Here is one observation: if each row and column have the same number of red squares, then the total number of triples is $999^4$ times $p(1-p)^2,$ where $p$ is the probability that a square in a given row/column is red. It's an easy calculus problem to maximize this with respect to $p,$ which happens when $p=1/3$ and $p(1-p)^2 = 4/27.$

Not all are red

The answer is 31.

1 solution

0 pending reports