|
|
 |
Условие
На клетчатой плоскости отметили 40 клеток. Всегда ли найдётся клетчатый прямоугольник, содержащий ровно 20 отмеченных клеток?
Решение
Контрпример 1. Рассмотрим клетчатый квадрат 11×11 и удалим из него внутренний центральный квадрат 9×9, оставив только рамку толщиной 1. Допустим, что есть клетчатый прямоугольник, содержащий ровно 20 из этих 40 клеток. Пусть в нём есть клетки из обеих вертикальных сторон рамки. Тогда каждая горизонтальная сторона рамки либо полностью включена в прямоугольник, либо вовсе не включена. Если включена ровно одна горизонтальная сторона, число клеток в прямоугольнике нечётно, если обе – клеток 40 (слишком много), а если ни одной – максимум 9 + 9 = 18 (слишком мало).
Значит, в прямоугольнике могут быть клетки лишь из одной вертикальной стороны рамки, и, аналогично, лишь из одной горизонтальной стороны. Но эти стороны соседние, и суммарно в них максимум 19 клеток – слишком мало. Противоречие.
Контрпример 2. Рассмотрим клетчатый прямоугольник [1, 14] × [1, 3], и удалим из него клетки (7, 1) и (7, 3). Останется ровно 40 клеток. Предположим, что нашёлся клетчатый прямоугольник, в котором ровно 20 отмеченных клеток. Он может затрагивать одну, две или три горизонтали с номерами 1, 2, 3. Если он затрагивает одну горизонталь, то в нём не более 14 отмеченных клеток.
Если он задевает 2 горизонтали (одна из них – вторая), то он задевает вертикаль с номером №7 (иначе в нём не более 14 клеток). Тогда эта вертикаль вносит в прямоугольник нечётное число отмеченных клеток, а остальные – чётное. Поэтому общее число отмеченных клеток в прямоугольнике нечётно.
Если он задевает все три горизонтали, то число отмеченных клеток в нём либо кратно 3 (если он не задевает 7-й вертикали), либо имеет остаток 1 при делении на 3. В каждом из случаев получаем противоречие.
Ответ
Не всегда.
Замечания
Есть и другие контрпримеры. Например, подходит квадрат 7×7 с вырезанным центральным квадратом 3×3, но доказательство более длинное.
