Red and White Cells 1

Algebra Level 5

In a 150 × 150 150\times150 square table some cells are white and the remaining ones are red. Let T T be the number of triples ( C 1 , C 2 , C 3 ) (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_1 and C 3 C_3 white and C 2 C_2 red. Find the maximum value T T can attain.

Note: This problem is in IMO shortlist, but the numbers are changed.

If you like this problem, check out Red and White Cells 2 !


The answer is 75000000.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Culver Kwan
Mar 6, 2020

Let A m , n A_{m,n} be 0 0 if the colour of the cell on row m m column n n is red or otherwise 1 1 where 1 m , n 150 1\le m,n\le150 ,and R m = j = 1 150 A m , j , C n = i = 1 150 A i , n , S = i = 1 150 R i = j = 1 150 C j R_m=\sum^{150}_{j=1}A_{m,j}, C_n=\sum^{150}_{i=1}A_{i,n}, S=\sum^{150}_{i=1}R_i=\sum^{150}_{j=1}C_j T = i = 1 150 j = 1 150 ( 1 A i , j ) R i C j 1 2 i = 1 150 j = 1 150 ( 1 A i , j ) ( R i 2 + C j 2 ) = 1 2 ( i = 1 150 R i 2 j = 1 150 ( 1 A i , j ) + j = 1 150 C j 2 i = 1 150 ( 1 A i , j ) ) = 1 2 ( i = 1 150 R i 2 ( 150 R i ) + j = 1 150 C j 2 ( 150 C j ) ) = 2 ( i = 1 150 R i 2 R i 2 ( 150 R i ) + j = 1 150 C j 2 C j 2 ( 150 C j ) ) 2 ( i = 1 150 ( R i 2 + R i 2 + ( 150 R i ) 3 ) 3 + j = 1 150 ( C j 2 + C j 2 + ( 150 C j ) 3 ) 3 ) = 2 ( 150 5 0 3 + 150 5 0 3 ) = 75000000 \begin{aligned}T&=\sum^{150}_{i=1}\sum^{150}_{j=1}(1-A_{i,j})R_iC_j\\&\le\frac{1}{2}\sum^{150}_{i=1}\sum^{150}_{j=1}(1-A_{i,j})(R^2_i+C^2_j)\\&=\frac{1}{2}\bigg(\sum^{150}_{i=1}R^2_i\sum^{150}_{j=1}(1-A_{i,j})+\sum^{150}_{j=1}C^2_j\sum^{150}_{i=1}(1-A_{i,j})\bigg)\\&=\frac{1}{2}\bigg(\sum^{150}_{i=1}R^2_i(150-R_i)+\sum^{150}_{j=1}C^2_j(150-C_j)\bigg)\\&=2\bigg(\sum^{150}_{i=1}\frac{R_i}{2}\cdot\frac{R_i}{2}\cdot(150-R_i)+\sum^{150}_{j=1}\frac{C_j}{2}\cdot\frac{C_j}{2}\cdot(150-C_j)\bigg)\\&\le2\Bigg(\sum^{150}_{i=1}\bigg(\frac{\frac{R_i}{2}+\frac{R_i}{2}+(150-R_i)}{3}\bigg)^3+\sum^{150}_{j=1}\bigg(\frac{\frac{C_j}{2}+\frac{C_j}{2}+(150-C_j)}{3}\bigg)^3\Bigg)\\&=2(150\cdot50^3+150\cdot50^3)\\&=75000000\end{aligned} Equality holds when R i = C j = 100 R_i=C_j=100 for 1 < i , j < 150 1<i,j<150 .

The following is an example: The cell in row m m column n n is red if m n 1 , 2 , 3 , . . . , 50 ( m o d 150 ) m-n\equiv1,2,3,...,50\pmod{150} or otherwise white.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...