Problem 1578

Let $a$ and $b$ be lucky. If $b \ge 2a$, then a $b \times b$ square contains $[b/a]^2$ squares of size $a \times a$, so at least $[b/a]^2 \cdot a > b$ black cells. This is impossible. Thus, the ratio of any two lucky numbers is less than $2$, which yields that there are at most $1008$ of them.

An example is provided by a white table with one of the two middle rows painted in black.

Рассмотрим произвольное окрашивание таблицы. Пусть нашлось хотя бы два удачных числа, и $a$ — наименьшее из них, а $b$ — наибольшее.

Поделим $b$ на $a$ с остатком: $b = qa + r$, где $0 \le r < a$. Предположим, что $q \ge 2$. В произвольном квадрате $b \times b$ можно расположить $q^2$ пересекающихся квадратов $a \times a$. В этих квадратах будет ровно $q^2 a$ чёрных клеток. Однако $q^2 a > (q+1)a > qa + r = b$; значит, в квадрате $b \times b$ будет больше, чем $b$ чёрных клеток, что невозможно. Итак, $q < 2$, то есть $b < 2a$.

Общее количество удачных чисел не превосходит количества натуральных чисел от $a$ до $b$, то есть оно не больше $b - a + 1 < b - b/2 + 1 = b/2 + 1 \le 1009$. Значит, это количество не больше $1008$.

Осталось привести пример раскраски, для которой найдутся $1008$ удачных чисел. Окрасим чёрным все клетки $1008$-й строки и только их. Рассмотрим произвольный квадрат со стороной $d \ge 1009$. Он пересекается с $1008$-ой строкой, значит в нём есть целая строка отмеченных клеток, то есть их как раз $d$ штук. Значит, все числа от $1009$ до $2016$ являются удачными, и таких чисел как раз $1008$.