MathLabs

Problem 2

Into each box of a 2012 by 2012 square grid, insert a real number between 0 and 1 inclusive. Split the grid into two non-empty rectangles of boxes by a line parallel to a side of the grid. Suppose that for every such split at least one resulting rectangle has sum at most 1. Determine the maximum possible sum of all inserted numbers.
Step 5 of 5: Bound the total
Previous stepNext step
∑i,jri,j≤R(1,a−1)+R(a+1,n)+C(1,b−1)+C(b+1,n)+ra,b≤5.\sum_{i,j}r_{i,j}\le R(1,a-1)+R(a+1,n)+C(1,b-1)+C(b+1,n)+r_{a,b}\le5.
Detailed analysis

The four disjoint strips and the crossing cell cover the grid. Each strip sum is at most 1 and the crossing cell is at most 1, so the total is at most 5. Together with the construction, the maximum is 5.