|
|
 |
Условие
В белой таблице 2016×2016 некоторые клетки окрасили чёрным. Назовём натуральное число k удачным, если k ≤ 2016, и в каждом из клетчатых квадратов со стороной k, расположенных в таблице, окрашено ровно k клеток. (Например, если все клетки чёрные, то удачным является только число 1.) Какое наибольшее количество чисел могут быть удачными?
Решение
Оценка. Рассмотрим произвольное окрашивание таблицы. Пусть нашлось хотя бы два удачных числа, и a – наименьшее из них, а b – наибольшее.
Поделим b на a с остатком: b = qa + r, где 0 ≤ r < a. Предположим, что q ≥ 2. В произвольном квадрате b×b можно расположить q² непересекающихся квадратов a×a. В этих квадратах будет ровно q²a чёрных клеток. Однако q²a > (q + 1)a > qa + r = b; значит, в квадрате b×b будет больше чем b чёрных клеток, что невозможно. Итак, q < 2, то есть b < 2a.
Общее количество удачных чисел не превосходит количества натуральных чисел от a до b, то есть оно не больше b – a + 1. b – b/2 + 1 = b/2 + 1 ≤ 1009. Значит, это количество не больше 1008.
Пример раскраски, для которой найдутся 1008 удачных чисел. Окрасим чёрным все клетки 1008-й строки и только их. Рассмотрим произвольный квадрат со стороной d ≥ 1009. Он пересекается с 1008-й строкой, значит, в нём есть целая строка отмеченных клеток, их как раз d штук. Следовательно, все числа от 1009 до 2016 являются удачными, и таких чисел как раз 1008.
Ответ
1008 чисел.
