This is a method very much like the first official solution, although with less fruit (no strawberries here) and more motivation. Very difficult problem. The answer is $2011^2 - 39 \cdot (35 \cdot 34) - 38 \cdot 17^2$. Call the number that appears most frequently in the grid $N$. In each cell with a number less than $N$ we write a minus, and in each cell with a number greater than $N$ we write a plus. Let $S$ be the number of cells with a plus or minus; we wish to show that $S \geq 39 \cdot (35 \cdot 34) + 38 \cdot 17^2$. We first consider an individual row or column of the table, which is effectively the same as a $1 \times 2011$ table having napkins of size $1 \times 52$. Notice that $2011 = 39 \cdot 35 + 38 \cdot 17$. Number the squares of the table $0, 1, 2, \ldots, 2010$, and consider each number's remainder when divided by 52. There are 39 squares for each remainder $0$ to $34$; color these white. Similarly there are 38 for each remainder $35$ to $51$; color these black. Each napkin covers exactly one square with each residue. Then if there are less than $39N$ napkins, there are at least 35 white squares with a minus; call such a row deficient. Similarly if there are more than $38N$ napkins, there are at least 17 black squares with a plus; call such a row or column dense. Clearly each row or column is either deficient or dense, possibly both. In the original table, color all squares white which are white for both the row and column, and likewise black for those which are black for both the row and column. If a square is white for the row and black for the column, color it red, and color the remaining squares blue. Thus, each row either has red and white squares or blue and black squares. Likewise, each column has blue and white squares or red and black squares. Let $A$ be the number of rows with white squares; note there are also $A$ such columns and that $A = 39 \cdot 35$. Define $B = 2011 - A$, the number of rows (or columns) with black squares. Consider all deficient rows or columns containing white squares, and suppose there are $a$ such rows and $b$ such columns. WLOG $a \geq b$. Then there are at least $35a$ minuses in the white squares. The other $A - a$ rows with white squares are dense, so they have at least 17 plusses in red squares. Similarly the other $A - b$ columns are dense, with at least 17 plusses in blue squares. Finally, consider the $B$ columns with black squares. Each has either 35 minuses in red squares or 17 plusses in red squares, neither of which we have counted yet. So there are at least 17 marked squares in each of these columns. Summing all of this up, \[ S \geq 35a + 17(A - a) + 17(A - b) + 17B = 18a - 17b + 17 (2A + B) \geq 17(2A+B). \] The last inequality follows from $a \geq b \geq 0$. It can be checked that $17(2A+B)$ is equal to the bound we need, so we are done. EDIT: I just realized I completely forgot to describe how to construct the bound I claimed. Let the rows and columns be numbered $0$ to $2010$. First, place napkins with top left corner on $(52k, 52m)$ for $k,m \geq 0$ and $k+m \leq 38$. This basically makes a staircase shape in the top left corner. Then do the same staircase in the bottom right: all napkins with top left corner on $(52k+35,52m+35)$ with $k+m \geq 38$ and $k,m \leq 38$. Finally, place a sequence of napkins along the top right - bottom left diagonal: $(52k+35, 52m)$ for all $k,m \geq 0$ with $k+m = 38$, and a final one on $(0, 1960)$.

The pitfall for this problem is that you will think that the answer is 1994^2. But it is indeed 3986729. Is there any nice solution not differentiating the dense and defecient row? I used about 1 week to solve it. (similar to first solution posted, the main idea is to consider mod 52)

How do you come up with the number 3986729?

By finding the construction I described in the edit to my post, then counting up how many squares have exactly one napkin covering them. You get the expression I gave as the answer in my post, which is indeed 3986729.

The answer is a flashy \[ \boxed{2011^2 - [(17 \cdot 157) + 37 \cdot (52^2-35^2)] = 3986729} \]Another (more illuminating) way to say this is \[ \boxed{2011^2 - [39 \cdot 2 \cdot (17 \cdot 35) + 38 \cdot 17^2]} \]However, the nicest way I've found to showcase the answer is \[ \boxed{1994^2 + 37 \cdot (17^2)} \]as this shows the improvement from the unoptimized $1994^2$, a $k$ one may have come up first.

The major illusion in this problem is the existence of $2011$ and $52$ --- I didn't realize their significance and function(s) until 3-4 hours in.

First we introduce some relatively basic notations. Let the cells that contain the same nonzero number is covered by $A$ napkins. We alter $k$'s definition to be $52$ and $n$ to be $2011$. We also differentiate between $\textbf{compliant}$, $\textbf{positive}$ and $\textbf{negative}$ cells; compliant if it is covered by $A$ napkins, and positive/negative if its number is strictly more/less than $A$. Also, name the rows/columns to be $r_i,c_j$, with $r_1$ to $r_{2011}$ sorted from top-to-bottom and $c_1$ to $c_{2011}$ from left-to-right. (Too lazy to follow standard Cartesian Coordinates, sorry for that) Our main ingredient in proving the bound will not be $\textbf{entire napkins}$; but the relative covering of the napkins $\textbf{projected}$ into each row $\textbf{and}$ column. $\color{yellow} \rule{7.5cm}{2pt}$ $\color{magenta} \clubsuit$ $ \boxed{\textbf{The Convoluted Grouping of Strips.}}$ $\color{magenta} \clubsuit$ $\color{yellow} \rule{7.5cm}{2pt}$ Following the configuration mentioned above (we omit the definitons of the layers and opt for a clearer one), define $c = 35$ and $m = 17$ ($c$ stands for corner, $m$ stands for middle). In each row (and column), call the first $c$ cells to be corner cells, next $m$ to be middle cells, next $c$ to be corner cells, and et cetera, until we have $39$ sets of corner cells and $38$ of middles. We Claim that each row (and column) to have either $m$ positive cells among its (set of) middle cells, or $c$ negative cells among its (set of) corner cells. $\color{green} \rule{25cm}{0.2pt}$ $\color{green} \spadesuit$ $\boxed{\textbf{Proof.}}$ $\color{green} \spadesuit$

If each index $36 \leq j \leq 52$ has a positive cell with position $j \pmod{52}$, there are at least $17$ positive cells. Otherwise, there is an index $j$ where all its $38$ cells having a number of at most $A$. In turn, there are at most $38A$ napkins covering that row, and so all $39$ cells from each index $i, 1 \leq i \leq 35$ cannot all be compliant or positive. So, there are at least one negative cell from each index, implying the result. $\blacksquare$ $\color{blue} \rule{5.2cm}{2pt}$ $\color{blue} \clubsuit$ $\color{blue} \boxed{\textbf{Computing in Regions.}}$ $\color{blue} \clubsuit$ $\color{blue} \rule{5.2cm}{2pt}$ Here we prove that the total number of noncompliant cells is at least \[ 39 \cdot 2 \cdot (17 \cdot 35) + 38 \cdot 17^2 \]a.k.a. the number being substracted in the answer's second form. We take this a bit further: define a cell to be type $CC,CM,MC$ or $MM$ if it belongs to a $c$-row and $c$-column, and so on. Define $P_X$ and $N_X$ where \[ X \in \{CC,CM,MC,MM\} \]to be the set of positive and negative cells in type-$X$ cells. We prove that \[ |P_{MM}| + |P_{MC}| + |N_{MC}| + |P_{CM}| + |N_{CM}| + |N_{CC}| \]is at least the number mentioned earlier. $\blacksquare$ $\blacksquare$ $\color{blue} \spadesuit$ $\color{blue} \boxed{\textbf{Proof.}}$ $\color{blue}\spadesuit$ The computation is also easier than it may seem (on the first official Shortlist Solution, or at the post above.) Variable Spam Incoming! Call the rows having $m$ positive cells among its middle cells to be a $\textit{positive-centered}$ row, and rows having $c$ negative cells among its corner cells to be a $\textit{negatively-cornered}$ row. Also, call a row to be a $\textit{middle}$ or $\textit{corner}$ row by a similar procedure (to its cell counterpart). First, we bound the sum of the $\color{blue} \text{first, third and fifth term}$. Let there are $a_m,b_m$ positive-centered rows and columns among the middle rows and columns, respectively. So, there are at least $38m-a_m$ and $38m-b_m$ negative-corned rows and columns (among the same rows/columns). By easy position-tracking we get that all the $m$ positive cells/$c$ negative cells obtained from $\color{magenta} \clubsuit$ $ \boxed{\textbf{The Convoluted Grouping of Strips}}$ $\color{magenta} \clubsuit$ must lie on $P_{MM}$ or $N_{MC} \cup N_{CM}$. Moreover, each positive cell in $P_{MM}$ may be counted twice (a.k.a. belonging to some positive-centered row and column, simultaneously) while each negative cell in the latter union-set may only contribute once. Summing, their total cardinality must be at least \[ \dfrac{m \cdot a_m + m \cdot b_m}{2} + c \cdot (38m-a_m) + c \cdot (38m-b_m) \]which attains minimality if $a_m, b_m$ maximum (they equalling $38m$); as $-c + \dfrac{m}{2} \leq 0$. The same reasoning can be applied to bound the total of the $\color{blue} \text{second, fourth and sixth}$ term. Letting $a_c$ and $b_c$ as the counterparts of $a_m,b_m$, we get that their sum is at least \[ \dfrac{c \cdot (39c-a_c) + c \cdot (39c-b_c)}{2} + m \cdot a_c + m \cdot b_c \]which attains minimality if $a_c,b_c$ maximum; as $-\dfrac{c}{2}+m \leq 0$. When these all are satisfied, the sum of $\color{blue} \text{all six terms}$ is \[ m \cdot 38m + 2 \cdot c \cdot (0) + c \cdot 0 + 2 \cdot m \cdot 39c \]as claimed. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$

Although I was unable to solve this one, I still wrote it up after reading the solution. Below is a slightly shorter solution than the above two, though it follows the same ideas in post #2. The answer is \[ 2011^2 - ((52^2-35^2) \cdot 39 - 17^2). \] Construction: Construct two ``staircase" like shapes at two of the opposite corners. Bound: Toss the configuration on the coordinate plane. Let $M$ be the maximum number of cells with the same nonzero number. We give each cell $C$ a Cartesian product of colors: Color 1: orange if the number at $C$ is equal to $M$, red if the number at $C$ is greater than $M$, blue if the number at $C$ less than $M$. Color 2: black if the $x$-coordinate of $C$ is in $\{1, 2, \dots, 35\}$ mod $52$, white otherwise. Color 3: black if the $y$-coordinate of $C$ is in $\{1, 2, \dots, 35\}$ mod $52$, white otherwise. Now consider a row or column of the grid; we will ``solve the problem" for this portion of the grid. Problem 1: [2011 C7, 1D] The answer to the problem except that ``napkins" are replaced with $1 \times 52$ strips is either $17$ or $35$. In particular, either each black residue has some blue cell, or some white residue has some red cell (or both). Proof. Note that for every strip added, every residue modulo $52$ has a total sum of numbers written down increased by $1$. Thus, the sum of the numbers written down at each residue is equal; let $S$ denote this sum. Note that there are $39$ black residues and $38$ white. If $S < 39M$, then by PHP, each black residue has some blue cell, and if $S > 38M$, then each white residue has some red cell. Let $r$ denote the number of rows with each black (Color 3) $x$-residue having some blue cell and no white $x$-residue having some red cell; analogously define $c$. Note that there are $39 \cdot 35$ black rows and $39 \cdot 35$ black columns. We do casework on the non-orange cells: (blue, black, black): There are at least $35\max(r, c)$ such cells; take the greater of the number of ``good" rows and ``good columns" and apply Problem 1 to show that there are at least $35\max(r, c)$. (red, white, black): By similar logic, there are at least $17(39 \cdot 35 - c)$ such cells. (red, black, white): By similar logic, there are at least $17(39 \cdot 35 - r)$ such cells. (---, white, white): In this case, each column with Color $3$ black entirely have at least $17$ non-orange cells, so there are at least $17(2011-39 \cdot 35)$ such cells. everything else: We consider this count to be at least $0$. All in all, the number of non-orange cells is at least $(52^2-35^2) \cdot 39 - 17^2$, as desired.

This problem is so goated. We claim the answer is \[ 2011^2 - 38 \cdot 17^2 - 2 \cdot 39 \cdot (17 \cdot 35) = \boxed{3986729}. \]Divide the grid into subsquares alternating from $35$ to $17$ to $35$ and so forth to $35$ (noting that $2011 \equiv 35 \pmod{52}$). Suppose instead that there are $k$ occurences of $17$ between $k+1$ occurences of $35$. Construction Represent and color the $17 \times 17$ with the color red and the $35 \times 35$ with the color white. Then we take napkins as follows: [asy][asy] int N = 7; for (int i = 0; i <= N; ++i) { draw((0,i)--(N,i)); draw((i,0)--(i,N)); for (int j = 0; j < N; ++j) { if (i == N) { continue; } if (i % 2 == 1 && j % 2 == 1) { filldraw(shift(i,j)*unitsquare, red+white); } if ((i + j) % 2 == 1) { filldraw(shift(i,j)*unitsquare, blue+white); } } } real eps = 0.1; path p = (eps,eps)--(eps,2-eps)--(2-eps,2-eps)--(2-eps,eps)--cycle; pen pe1 = black+linewidth(2); pen pe2 = orange+linewidth(2); pen pe3 = green+linewidth(2); pen pe4 = purple+linewidth(2); pen f1 = black+opacity(0.2); [/asy][/asy] [asy][asy] int N = 7; for (int i = 0; i <= N; ++i) { draw((0,i)--(N,i)); draw((i,0)--(i,N)); for (int j = 0; j < N; ++j) { if (i == N) { continue; } if (i % 2 == 1 && j % 2 == 1) { filldraw(shift(i,j)*unitsquare, red+white); } if ((i + j) % 2 == 1) { filldraw(shift(i,j)*unitsquare, blue+white); } } } real eps = 0.1; path p = (eps,eps)--(eps,2-eps)--(2-eps,2-eps)--(2-eps,eps)--cycle; pen pe1 = black+linewidth(2); pen pe2 = orange+linewidth(2); pen pe3 = green+linewidth(2); pen pe4 = purple+linewidth(2); pen f1 = black+opacity(0.2); filldraw(shift(0,5)*p, pe1); filldraw(shift(0,4)*p, pe2); filldraw(shift(1,5)*p, pe3); filldraw(shift(2,3)*p, pe1); filldraw(shift(2,2)*p, pe2); filldraw(shift(3,3)*p, pe3); filldraw(shift(4,1)*p, pe1); filldraw(shift(4,0)*p, pe2); filldraw(shift(5,1)*p, pe3); filldraw(shift(5,0)*p, pe1); filldraw(shift(0,0)*p, pe4); filldraw(shift(2,0)*p, pe4); filldraw(shift(0,2)*p, pe4); filldraw(shift(5,5)*p, pe4); filldraw(shift(3,5)*p, pe4); filldraw(shift(5,3)*p, pe4); [/asy][/asy] Every square is covered exactly once except for the $k$ squares which have $17^2$ cells, which are covered three times, and $2(k+1)$ occurences of the purple squares which have $17 \cdot 35$ cells, so we obtain the desired result for $k = 38$. Bound Fix any number $t$ so we are counting the napkin cells with $t$ cells. We first prove the following one dimensional claim: Claim: Suppose we cover $17k + 35(k+1)$ cells colored alternating as above in a row with $1 \times 52$ sticks, which alternates between white or blue with the $1 \times 35$ runs white and the $1 \times 17$ runs blue. Then either there exist at least $17$ blue cells that are covered more than $t$ times, and if not there are at least $17$ white cells that are covered less than $t$ times. Proof. Note that each stick covers $52$ consecutive residues, but the residues in white cells occur $k+1$ times and the residues in blue cells occur $k$ times. This means that either the sum of the white cells isn't $(k+1)t$ or the sum of the blue cells isn't $kt$ since the sum is equal over all cells of the same residue, and we can finish by size. $\blacksquare$ We now use this claim on each row / column of length $17$ or $35$, to lower bound the number of invalid cells, where each row / column can claim some fractional part of each cell that doesn't contain $t$. For each of the $17k$ columns which intersect a red square, we can claim either at least $17$ red cells, or at least $17$ blue cells which are covered less than $t$ times. Then for each of the $2 \cdot 35 \cdot (k+1)$ rows or columns that doesn't contain a red square, either we can claim $17$ blue cells which are covered more than $t$ times, or $35$ white cells, which we can claim half of. Since we end up claiming at least $17$ regardless of which row / column, we get at least $17(17k + 2 \cdot 35 \cdot (k+1))$ cells, which finishes.