In a white $2016 \times 2016$ table, some cells are painted black. We call a natural number $k$ successful if $k$ $\leq 2016$, and in each of the grid squares with side $k$ located in the table, exactly $k$ cells are painted black. (For example, if all cells are black, then the only successful number is 1.) What is the maximum number of numbers that can be successful?
Evaluation. Consider an arbitrary coloring of the table. Suppose there are at least two successful numbers, and let $a$ be the smallest of them, and $b$ be the largest.

Divide $b$ by $a$ with a remainder: $b = q a + r$, where $0 \leq r < a$. If $r \neq 0$, then $r$ is a successful number, and $a < r < b$, which contradicts the minimality of $a$. Therefore, $r = 0$, and $b = q a$.

If $q \geq 2$, then $(q+1) a > q a + r = b$; hence, in the square $b \times b$, there will be more than $b$ black cells, which is impossible. Therefore, $q < 2$, which means $b < 2a$.

The total number of successful numbers does not exceed the number of natural numbers from $a$ to $b$, that is, it is no more than $b - a + 1$. Since $b < 2a$, we have $b - a + 1 = b - b/2 + 1 = b/2 + 1 \leq 1009$. Thus, this number is no more than 1008.

An example of a coloring for which there will be 1008 successful numbers. Color black all the cells in the 1008th row and only them. Consider an arbitrary square with side $d \geq 1009$. It intersects with the 1008th row, so it contains a whole row of marked cells, which are exactly $d$ in number. Therefore, all numbers from 1009 to 2016 are successful, and there are exactly 1008 such numbers.

## Answer

1008 numbers.