ELMO SL 2013 C5

There is a $2012\times 2012$ grid with rows numbered $1,2,\dots 2012$ and columns numbered $1,2,\dots, 2012$ , and we place some rectangular napkins on it such that the sides of the napkins all lie on grid lines. Each napkin has a positive integer thickness. (in micrometers!)

(a) Show that there exist $2012^2$ unique integers $a_{i,j}$ where $i,j \in [1,2012]$ such that for all $x,y\in [1,2012]$ , the sum $$\sum _{i=1}^{x} \sum_{j=1}^{y} a_{i,j}$$ is equal to the sum of the thicknesses of all the napkins that cover the grid square in row $x$ and column $y$ . (b) Show that if we use at most $500,000$ napkins, at least half of the $a_{i,j}$ will be $0$ .

Proposed by Ray Li