Условие
На бесконечном листе клетчатой бумаги
N клеток
окрашено в черный цвет. Докажите, что из этого листа
можно вырезать конечное число квадратов так, что будут
выполняться два условия: 1) все черные клетки лежат в вырезанных
квадратах; 2) в любом вырезанном квадрате
K площадь черных клеток
составит не менее 1/5 и не более 4/5 площади
K.
Решение
Возьмем какой-нибудь достаточно большой квадрат со
стороной 2
n так, чтобы все черные клетки лежали внутри его
и составляли менее 0, 2 его площади. Разрежем этот квадрат на
четыре одинаковых квадрата. Каждый из них окрашен менее чем
на 0, 8. Те из них, которые окрашены более чем на 0, 2, оставляем,
а остальные режем дальше таким же образом. Полученные квадраты
2×2 будут окрашены на 1/4, 1/2, 3/4 или не будут окрашены
вовсе. Из листа бумаги нужно вырезать те полученные квадраты,
в которых есть окрашенные клетки.
Замечания
Задача допускает обобщение на трехмерный случай с заменой 1/5 на 1/9
и 4/5 на 8/9.
Источники и прецеденты использования
