Problem 1920

Let $m=39$, then $2011=52 m-17$. We begin with an example showing that there can exist $3986729$ cells carrying the same positive number.

To describe it, we number the columns from the left to the right and the rows from the bottom to the top by $1,2, \ldots, 2011$. We will denote each napkin by the coordinates of its lower left cell. There are four kinds of napkins: first, we take all napkins $(52 i+36,52 j+1)$ with $0 \leq j \leq i \leq m-2$; second, we use all napkins $(52 i+1,52 j+36)$ with $0 \leq i \leq j \leq m-2$; third, we use all napkins $(52 i+36,52 i+36)$ with $0 \leq i \leq m-2$; and finally the napkin $(1,1)$. Different groups of napkins are shown by different types of hatchings in the picture.

Now except for those squares that carry two or more different hatchings, all squares have the number $1$ written into them. The number of these exceptional cells is easily computed to be $\left(52^{2}-35^{2}\right) m-17^{2}=57392$.

We are left to prove that $3986729$ is an upper bound for the number of cells containing the same number. Consider any configuration of napkins and any positive integer $M$. Suppose there are $g$ cells with a number different from $M$. Then it suffices to show $g \geq 57392$. Throughout the solution, a line will mean either a row or a column.

Consider any line $\ell$. Let $a_{1}, \ldots, a_{52 m-17}$ be the numbers written into its consecutive cells. For $i=1,2, \ldots, 52$, let $s_{i}=\sum_{t \equiv i(\bmod 52)} a_{t}$. Note that $s_{1}, \ldots, s_{35}$ have $m$ terms each, while $s_{36}, \ldots, s_{52}$ have $m-1$ terms each. Every napkin intersecting $\ell$ contributes exactly $1$ to each $s_{i}$; hence the number $s$ of all those napkins satisfies $s_{1}=\cdots=s_{52}=s$. Call the line $\ell$ rich if $s>(m-1) M$ and poor otherwise.

Suppose now that $\ell$ is rich. Then in each of the sums $s_{36}, \ldots, s_{52}$ there exists a term greater than $M$; consider all these terms and call the corresponding cells the rich bad cells for this line. So, each rich line contains at least $17$ cells that are bad for this line.

If, on the other hand, $\ell$ is poor, then certainly $s<m M$ so in each of the sums $s_{1}, \ldots, s_{35}$ there exists a term less than $M$; consider all these terms and call the corresponding cells the poor bad cells for this line. So, each poor line contains at least $35$ cells that are bad for this line.

Let us call all indices congruent to $1,2, \ldots$, or $35$ modulo $52$ small, and all other indices, i.e. those congruent to $36,37, \ldots$, or $52$ modulo $52$, big. Recall that we have numbered the columns from the left to the right and the rows from the bottom to the top using the numbers $1,2, \ldots, 52 m-17$; we say that a line is big or small depending on whether its index is big or small. By definition, all rich bad cells for the rows belong to the big columns, while the poor ones belong to the small columns, and vice versa.

In each line, we put a strawberry on each cell that is bad for this line. In addition, for each small rich line we put an extra strawberry on each of its (rich) bad cells. A cell gets the strawberries from its row and its column independently.

Notice now that a cell with a strawberry on it contains a number different from $M$. If this cell gets a strawberry by the extra rule, then it contains a number greater than $M$. Moreover, it is either in a small row and in a big column, or vice versa. Suppose that it is in a small row, then it is not bad for its column. So it has not more than two strawberries in this case. On the other hand, if the extra rule is not applied to some cell, then it also has not more than two strawberries. So, the total number $N$ of strawberries is at most $2 g$.

We shall now estimate $N$ in a different way. For each of the $2 \cdot 35 m$ small lines, we have introduced at least $34$ strawberries if it is rich and at least $35$ strawberries if it is poor, so at least $34$ strawberries in any case. Similarly, for each of the $2 \cdot 17(m-1)$ big lines, we put at least $\min (17,35)=17$ strawberries. Summing over all lines we obtain
$$2 g \geq N \geq 2(35 m \cdot 34+17(m-1) \cdot 17)=2(1479 m-289)=2 \cdot 57392$$
as desired.

We present a different proof of the estimate which is the hard part of the problem. Let $S=35$, $H=17$, $m=39$; so the table size is $2011=S m+H(m-1)$, and the napkin size is $52=S+H$. Fix any positive integer $M$ and call a cell vicious if it contains a number distinct from $M$. We will prove that there are at least $H^{2}(m-1)+2 S H m$ vicious cells.

Firstly, we introduce some terminology. As in the previous solution, we number rows and columns and we use the same notions of small and big indices and lines; so, an index is small if it is congruent to one of the numbers $1,2, \ldots, S$ modulo $(S+H)$. The numbers $1,2, \ldots, S+H$ will be known as residues. For two residues $i$ and $j$, we say that a cell is of type $(i, j)$ if the index of its row is congruent to $i$ and the index of its column to $j$ modulo $(S+H)$. The number of vicious cells of this type is denoted by $v_{ij}$.

Let $s, s'$ be two variables ranging over small residues and let $h, h'$ be two variables ranging over big residues. A cell is said to be of class $A, B, C$, or $D$ if its type is of shape $(s, s')$, $(s, h)$, $(h, s)$, or $(h, h')$, respectively. The numbers of vicious cells belonging to these classes are denoted in this order by $a, b, c$, and $d$. Observe that each cell belongs to exactly one class.

Claim 1. We have
$$m \leq \frac{a}{S^{2}}+\frac{b+c}{2 S H} . \tag{1}$$
Proof. Consider an arbitrary small row $r$. Denote the numbers of vicious cells on $r$ belonging to the classes $A$ and $B$ by $\alpha$ and $\beta$, respectively. As in the previous solution, we obtain that $\alpha \geq S$ or $\beta \geq H$. So in each case we have $\frac{\alpha}{S}+\frac{\beta}{H} \geq 1$.

Performing this argument separately for each small row and adding up all the obtained inequalities, we get $\frac{a}{S}+\frac{b}{H} \geq m S$. Interchanging rows and columns we similarly get $\frac{a}{S}+\frac{c}{H} \geq m S$. Summing these inequalities and dividing by $2 S$ we get what we have claimed.

Claim 2. Fix two small residues $s, s'$ and two big residues $h, h'$. Then $2 m-1 \leq v_{s s'}+v_{s h'}+v_{h h'}$.

Proof. Each napkin covers exactly one cell of type $(s, s')$. Removing all napkins covering a vicious cell of this type, we get another collection of napkins, which covers each cell of type $(s, s')$ either $0$ or $M$ times depending on whether the cell is vicious or not. Hence $(m^{2}-v_{s s'}) M$ napkins are left and throughout the proof of Claim 2 we will consider only these remaining napkins. Now, using a red pen, write in each cell the number of napkins covering it. Notice that a cell containing a red number greater than $M$ is surely vicious.

We call two cells neighbors if they can be simultaneously covered by some napkin. So, each cell of type $(h, h')$ has not more than four neighbors of type $(s, s')$, while each cell of type $(s, h')$ has not more than two neighbors of each of the types $(s, s')$ and $(h, h')$. Therefore, each red number at a cell of type $(h, h')$ does not exceed $4 M$, while each red number at a cell of type $(s, h')$ does not exceed $2 M$.

Let $x, y$, and $z$ be the numbers of cells of type $(h, h')$ whose red number belongs to $(M, 2 M]$, $(2 M, 3 M]$, and $(3 M, 4 M]$, respectively. All these cells are vicious, hence $x+y+z \leq v_{h h'}$. The red numbers appearing in cells of type $(h, h')$ clearly sum up to $(m^{2}-v_{s s'}) M$. Bounding each of these numbers by a multiple of $M$ we get
$$(m^{2}-v_{s s'}) M \leq ((m-1)^{2}-(x+y+z)) M+2 x M+3 y M+4 z M,$$
i.e.
$$2 m-1 \leq v_{s s'}+x+2 y+3 z \leq v_{s s'}+v_{h h'}+y+2 z .$$
So, to prove the claim it suffices to prove that $y+2 z \leq v_{s h'}$.

For a cell $\delta$ of type $(h, h')$ and a cell $\beta$ of type $(s, h')$ we say that $\delta$ forces $\beta$ if there are more than $M$ napkins covering both of them. Since each red number in a cell of type $(s, h')$ does not exceed $2 M$, it cannot be forced by more than one cell.

On the other hand, if a red number in a $(h, h')$-cell belongs to $(2 M, 3 M]$, then it forces at least one of its neighbors of type $(s, h')$ (since the sum of red numbers in their cells is greater than $2 M$). Analogously, a $(h, h')$-cell with the red number in $(3 M, 4 M]$ forces both its neighbors of type $(s, h')$, since their red numbers do not exceed $2 M$. Therefore there are at least $y+2 z$ forced cells and clearly all of them are vicious, as desired.

Claim 3. We have
$$2 m-1 \leq \frac{a}{S^{2}}+\frac{b+c}{2 S H}+\frac{d}{H^{2}} \tag{2}$$
Proof. Averaging the previous result over all $S^{2} H^{2}$ possibilities for the quadruple $(s, s', h, h')$, we get $2 m-1 \leq \frac{a}{S^{2}}+\frac{b}{S H}+\frac{d}{H^{2}}$. Due to the symmetry between rows and columns, the same estimate holds with $b$ replaced by $c$. Averaging these two inequalities we arrive at our claim.

Now let us multiply (2) by $H^{2}$, multiply (1) by $(2 S H-H^{2})$ and add them; we get
$H^{2}(2 m-1)+(2 S H-H^{2}) m \leq a \cdot \frac{H^{2}+2 S H-H^{2}}{S^{2}}+(b+c) \frac{H^{2}+2 S H-H^{2}}{2 S H}+d=a \cdot \frac{2 H}{S}+b+c+d$.

The left-hand side is exactly $H^{2}(m-1)+2 S H m$, while the right-hand side does not exceed $a+b+c+d$ since $2 H \leq S$. Hence we come to the desired inequality.