In a square table some cells are white and the remaining ones are red. Let be the number of triples of cells, the first two in the same row and the last two in the same column, with and white and red. Find the maximum value 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 !
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.
Let A m , n be 0 if the colour of the cell on row m column n is red or otherwise 1 where 1 ≤ m , n ≤ 1 5 0 ,and R m = j = 1 ∑ 1 5 0 A m , j , C n = i = 1 ∑ 1 5 0 A i , n , S = i = 1 ∑ 1 5 0 R i = j = 1 ∑ 1 5 0 C j T = i = 1 ∑ 1 5 0 j = 1 ∑ 1 5 0 ( 1 − A i , j ) R i C j ≤ 2 1 i = 1 ∑ 1 5 0 j = 1 ∑ 1 5 0 ( 1 − A i , j ) ( R i 2 + C j 2 ) = 2 1 ( i = 1 ∑ 1 5 0 R i 2 j = 1 ∑ 1 5 0 ( 1 − A i , j ) + j = 1 ∑ 1 5 0 C j 2 i = 1 ∑ 1 5 0 ( 1 − A i , j ) ) = 2 1 ( i = 1 ∑ 1 5 0 R i 2 ( 1 5 0 − R i ) + j = 1 ∑ 1 5 0 C j 2 ( 1 5 0 − C j ) ) = 2 ( i = 1 ∑ 1 5 0 2 R i ⋅ 2 R i ⋅ ( 1 5 0 − R i ) + j = 1 ∑ 1 5 0 2 C j ⋅ 2 C j ⋅ ( 1 5 0 − C j ) ) ≤ 2 ( i = 1 ∑ 1 5 0 ( 3 2 R i + 2 R i + ( 1 5 0 − R i ) ) 3 + j = 1 ∑ 1 5 0 ( 3 2 C j + 2 C j + ( 1 5 0 − C j ) ) 3 ) = 2 ( 1 5 0 ⋅ 5 0 3 + 1 5 0 ⋅ 5 0 3 ) = 7 5 0 0 0 0 0 0 Equality holds when R i = C j = 1 0 0 for 1 < i , j < 1 5 0 .
The following is an example: The cell in row m column n is red if m − n ≡ 1 , 2 , 3 , . . . , 5 0 ( m o d 1 5 0 ) or otherwise white.