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
Problem
Source: ELMO Shortlist 2013: Problem C5, by Ray Li
Tags: induction, strong induction, combinatorics unsolved, combinatorics
chaotic_iak
23.07.2013 08:33
Wait, either a and b contradict each other or I have the wrong interpretation of the word "unique". By "unique" do you mean there exist $2012^2$ different integers $a_{i,j}$ or there exists exactly one $2012^2$-tuple of integers $a_{i,j}$?
hyperbolictangent
23.07.2013 16:37
a) Let $T(x, y)$ be the total napkin thickness at $(x, y)$. We show the $a_{i, j}$ are uniquely determined by strong induction on $i + j$. Clearly $a_{1, 1}$ is uniquely determined; it must equal $T(1, 1)$. Suppose the $a_{i, j}$ have been uniquely determined for all $i, j$ with $i + j < N$; then $a_{k, N - k}$ must satisfy \[T(k, N - k) = \sum_{i = 1}^{k}{\sum_{j = 1}^{N - k}{a_{i, j}}}\] where all other $a_{i, j}$ in the sum satisfy $i + j < N$ - clearly this fixes $a_{k, N - k}$. b) Because total thickness at a square and the definition of $\{a_{i, j, k}\}$ is additive, we can define a set of integers $a_{i, j, k}$ where for $k$ fixed, $a_{i, j, k}$ is the $a_{i, j}$ value corresponding to just the $k$-th napkin. Clearly setting \[a_{i, j} = \sum_{k}{a_{i, j}}\] for $i, j \in [2012]^2$ satisfies the condition on the $a_{i, j}$ and is the unique set of integers which does so. For $k$ fixed (i.e. a single napkin is being considered), the set $a_{i, j, k}$ where $i$, $j$ vary in $[2012]$ is (thankfully) quite tame; it's easy to see there are exactly $4$ non-zero members located roughly at the corners of the napkin. Then $500000$ napkins together produce at most \[4(500000) = 2000000 < \frac{1}{2}(2012)^2\] non-zero $a_{i, j}$ terms as desired.
Pathological
28.10.2019 03:48
Here is another way to solve (b). Let $t_{i, j}$ be the total thickness at $(i, j)$. Note that for $i, j > 1$, we have that $a_{i, j} = t_{i, j} - t_{i, j-1} - t_{i-1, j} + t_{i-1, j-1}.$ Now, notice that as we place a napkin onto the grid, $t_{i, j} - t_{i, j-1} - t_{i-1, j} + t_{i-1, j-1}$ is unchanged unless one of the corners of the napkin is at the common corner of cells $(i, j)$ and $(i-1, j-1).$ We will say that a napkin corrupts $(i, j)$ if it has a corner at this point. Note that if a pair $(i, j)$ is not corrupted, $a_{i, j} = 0.$ Clearly, at most $4 \cdot 500000 = 2000000$ distinct cells are corrupted, and so there are at least $2011^2 - 2000000 > \frac12 2012^2$ cells $(i, j)$ with $i, j >1$ and $a_{i, j} = 0$. We're done. $\square$