ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66996
Темы:    [ Геометрия на клетчатой бумаге ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 3
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

На клетчатой плоскости отметили 40 клеток. Всегда ли найдётся клетчатый прямоугольник, содержащий ровно 20 отмеченных клеток?

Решение 1

Рассмотрим клетчатый квадрат размером $11\times11$ и удалим из него внутренний центральный квадрат $9\times9$, оставив только рамку толщиной 1. В рамке будет как раз 40 клеток. Докажем, что на плоскости нет клетчатого прямоугольника, содержащего ровно 20 из этих 40 клеток.

Допустим, такой прямоугольник есть. Пусть в нём есть клетки из обеих вертикальных сторон рамки. Тогда каждая горизонтальная сторона рамки либо полностью включена в прямоугольник, либо вовсе не включена. Если включена ровно одна горизонтальная сторона, число клеток в прямоугольнике нечётно, если обе – клеток 40 (слишком много), а если ни одной – клеток максимум 9+9=18 (слишком мало).

Значит, в прямоугольнике могут быть клетки лишь из одной вертикальной стороны рамки, и, аналогично, лишь из одной горизонтальной стороны рамки. Но эти стороны соседние, и суммарно в них максимум 19 клеток – слишком мало. Противоречие.


Решение 2

Рассмотрим клетчатый прямоугольник $[1,14]\times[1,3]$, и удалим из него клетки $(7,1)$ и $(7,3)$. Останется ровно 40 клеток. Предположим, что нашёлся клетчатый прямоугольник, в котором ровно 20 отмеченных клеток. Он может затрагивать одну, две или три горизонтали с номерами $1,2,3$.

Если он затрагивает одну горизонталь, то в нём не более $14$ отмеченных клеток.

Если он задевает 2 горизонтали (одна из них – вторая), то он задевает вертикаль с номером $7$ (иначе в нём не более $14$ клеток). Тогда эта вертикаль вносит в прямоугольник нечётное число отмеченных клеток, а остальные – чётное. Поэтому общее число отмеченных клеток в прямоугольнике нечётно.

Если он задевает все три горизонтали, то число отмеченных клеток в нём либо кратно $3$ (если он не задевает $7$-й вертикали), либо имеет остаток $1$ при делении на $3$ (иначе).

В каждом из случаев получаем противоречие.

Ответ

Нет.

Замечания

Возможны другие решения. Например, подходит квадрат $7\times7$ с вырезанным центральным квадратом $3\times3$, но доказательство более длинное.

Источники и прецеденты использования

олимпиада
Название Турнир городов
номер/год
Номер 41
Год 2019/20
тур
Вариант устный тур
задача
Номер 3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .