On a square table of 2011 by 2011 cells we place a finite number of napkins that each cover a square of 52 by 52 cells. In each cell we write the number of napkins covering it, and we record the maximal number \( k \) of cells that all contain the same nonzero number. Considering all possible napkin configurations, what is the largest value of \( k \)? Answer. \( 2011^2 - \left( \left( 52^2 - 35^2 \right) \cdot 39 - 17^2 \right) = 4044121 - 57392 = 3986729 \).
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. ![](https://cdn.mathpix.com/cropped/2024_04_17_481ddb3576adc2313a2eg-40.jpg?height=577&width=580&top_left_y=1022&top_left_x=744) 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 lowerleft 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. 

Comment. The same reasoning applies also if we replace 52 by $R$ and 2011 by $R m-H$, where $m, R$, and $H$ are integers with $m, R \geq 1$ and $0 \leq H \leq \frac{1}{3} R$. More detailed information is provided after the next solution.