Splitting a grid into two rectangles
by liberator, Nov 1, 2014, 11:57 AM
Problem: Into each box of a 
square grid, a real number greater than or equal to 
and less than or equal to 
is inserted. Consider splitting the grid into 
non-empty rectangles consisting of boxes of the grid by drawing a line parallel either to the horizontal or the vertical side of the grid. Suppose that for at least one of the resulting rectangles the sum of the numbers in the boxes within the rectangle is less than or equal to , no matter how the grid is split into such rectangles. Determine the maximum possible value for the sum of all the numbers inserted into the boxes.
[Asian Pacific Mathematical Olympiad 2012 Problem 2]
square grid, a real number greater than or equal to 
and less than or equal to 
is inserted. Consider splitting the grid into 
non-empty rectangles consisting of boxes of the grid by drawing a line parallel either to the horizontal or the vertical side of the grid. Suppose that for at least one of the resulting rectangles the sum of the numbers in the boxes within the rectangle is less than or equal to , no matter how the grid is split into such rectangles. Determine the maximum possible value for the sum of all the numbers inserted into the boxes.[Asian Pacific Mathematical Olympiad 2012 Problem 2]
may be achieved in the following configuration:![[asy]
/* APMO 2012 Problem 2, free script by liberator, 1 November 2014 */
unitsize(0.8cm);
defaultpen(fontsize(16pt));
/* Draw objects */
draw(Line((0,0), (0,3), 0.2, 0));
draw(Line((1,0), (1,3), 0.2, 0));
draw(Line((2,0), (2,3), 0.2, 0));
draw(Line((3,0), (3,3), 0.2, 0));
draw(Line((0,0), (3,0), 0, 0.2));
draw(Line((0,1), (3,1), 0, 0.2));
draw(Line((0,2), (3,2), 0, 0.2));
draw(Line((0,3), (3,3), 0, 0.2));
/* Label objects */
label("$0$", (0,0), 1.8*dir(45));
label("$1$", (0,1), 1.8*dir(45));
label("$0$", (0,2), 1.8*dir(45));
label("$1$", (1,0), 1.8*dir(45));
label("$1$", (1,1), 1.8*dir(45));
label("$1$", (1,2), 1.8*dir(45));
label("$0$", (2,0), 1.8*dir(45));
label("$1$", (2,1), 1.8*dir(45));
label("$0$", (2,2), 1.8*dir(45));
label("$\vdots$", (1,0), 1.8*dir(-45));
label("$\cdots$", (3,1), 1.8*dir(45));
[/asy]](http://latex.artofproblemsolving.com/2/6/7/267f93f0847bf09829e19827d728b1cbb15db295.png)
is attainable.
board. Choose ![\[\ell = \max_{1 \leq j \leq n} \left \{ j: \sum_{i=1}^{j-1} C_i \leq 1 \right \},\]](http://latex.artofproblemsolving.com/9/e/b/9ebfc2d0de59ce4ac35996de09cf10590a3628cd.png)
where 
denotes the sum of the entries in column 
.![\[ \ell' = \min_{\ell \leq j \leq n} \left \{j: \sum_{i= j+1}^n C_i \leq 1 \right \}.\]](http://latex.artofproblemsolving.com/a/8/3/a834ba7b76acf395fa2505953e8fae0d0d9652ee.png)
If 
,![\[\sum_{i=1}^{\ell} C_i > 1, \sum_{i= \ell +1}^n C_i > 1,\]](http://latex.artofproblemsolving.com/1/c/e/1ce4d8a5f86ef3413b93cfe9feaf86a48f780284.png)
which contradicts the problem requirement. Hence 
.
denotes the sum of the entries in row 
an integer 
such that ![\[\sum_{i=1}^{m-1} R_i \leq 1, \sum_{i= m+1}^n R_i \leq 1.\]](http://latex.artofproblemsolving.com/f/3/2/f32e4825452e3216406c0cd4eedf035494c1f6f1.png)
Considering the value of the entry in column 
,
,![\[1 \geq k- \left (\sum_{i=1}^{\ell-1} C_i + \sum_{i= \ell +1}^n C_i + \sum_{i=1}^{m-1} R_i + \sum_{i= m+1}^n R_i \right ) \geq k - 4.\]](http://latex.artofproblemsolving.com/f/3/9/f39b4917329ffb5393e84e89b54c52d6839fa46f.png)
Therefore 
;
,This post has been edited 1 time. Last edited by liberator, Nov 1, 2014, 11:57 AM
October 2018
April 2018