10.4. In each cell of a $100 \times 100$ square, a certain natural number is written. A rectangle, whose sides lie along the grid lines, is called good if the sum of the numbers in all its cells is divisible by 17. It is allowed to simultaneously color all the cells in some good rectangle. It is forbidden to color a cell more than once. What is the largest $d$ such that at least $d$ cells can be colored for any arrangement of the numbers?

(P. Zusmanovich, F. Petrov)
10.4. Answer. $9744=100^{2}-16^{2}$ cells.

Lemma. Suppose a strip $1 \times k$ is filled with natural numbers. Then in it, one can paint several non-overlapping good rectangles, containing no less than $k-16$ cells.

Proof. Induction on $k$. For $k \leqslant 16$, nothing needs to be painted. Let $k \geqslant 17$. Suppose the numbers in the 17 leftmost cells are $a_{1}, \ldots, a_{17}$. Among the numbers $0, a_{1}, a_{1}+a_{2}, \ldots, a_{1}+\ldots+a_{17}$, there will be a difference of the form $a_{i}+a_{i+1}+\ldots+a_{j}$ that is divisible by 17. Remove the cells from the $i$-th to the $j$-th from the strip. Consider the remaining cells as one strip of length $k-(j-i+1)$. Applying the induction hypothesis to it, we can paint several good rectangles such that no more than 16 cells remain unpainted. Then in the original strip, we can paint the same cells, as well as the cells from the $i$-th to the $j$-th (they either form a new good rectangle or fall inside an old one).

Now let's move on to the problem. We will show that no more than $16^{2}=256$ cells can remain unpainted. Consider a strip $1 \times 100$, in which the cells contain the sums of the numbers in the columns of the original square. Applying the lemma to it, we will find several good rectangles. Then in the original square, we can paint the corresponding rectangles of height 100. After this, no more than 16 columns will remain unpainted. Now apply the lemma to each of them separately; in each column, no more than 16 cells will remain unpainted, i.e., no more than 256 cells in total.

It remains to provide an example of an arrangement in which it is impossible to leave fewer than 256 cells unpainted. Place ones in some $16 \times 16$ square, and zeros in all other cells. Consider an arbitrary rectangle $P$; if it contains a one, then it intersects the square by some rectangle $a \times b(1 \leqslant a, b \leqslant 16)$; but then the sum of the numbers in $P$ will be $a b$, which cannot be divisible by 17.

Thus, no cell with a one will be painted,

and therefore, at least 256 cells will remain unpainted.

XXXVI All-Russian Mathematical Olympiad for Schoolchildren