Question

На шахматной доске 8х8 нарисованы по клеточкам 17 не налегающих друг на друга двухклеточных прямоугольников. Докажите, что на доске найдутся две имеющие общую сторону клетки, одна из которых лежит в од-ном из нарисованных прямоугольников, а другая — в другом.​

Answer 1

Ответ:

Наличие искомых клеток возможно только при соприкасающихся прямоугольниках. Предположим, что мы имеем не соприкасающиеся прямоугольника, значит вокруг каждого прямоугольника мы имеем как минимум 3 пустых клетки. Следовательно, общая площадь доски должна быть: 85 клеток, что противоречит условию, т.к. размер поля 8*8=64. Следовательно

Answer 2

Довольно простая задача на оценку. Это олимпиада и ты должен решать задачи сам, так что изволь соблюдать регламент проведения и решай сам.

Answer 3

Давайте докажем это утверждение от противного.

Предположим, что на доске нет таких двух клеток, одна из которых лежит в одном прямоугольнике, а другая — в другом, и имеют общую сторону. Это означает, что каждый прямоугольник занимает какой-то свой "регион" на доске, который не имеет общих клеток с другими прямоугольниками.

Теперь обратим внимание на то, что каждый прямоугольник состоит из двух клеток, которые, в сумме, занимают 34 клетки (17 прямоугольников по 2 клетки). Доска 8х8 имеет 64 клетки. Если каждый прямоугольник занимает свой уникальный регион, то это означает, что остается 64 - 34 = 30 клеток, которые не могут быть покрыты этими прямоугольниками.

Теперь мы сталкиваемся с противоречием, потому что у нас есть 30 клеток, которые не могут быть покрыты прямоугольниками, и при этом у нас больше нет свободных клеток для дополнительных прямоугольников. Это означает, что наше предположение о том, что нет двух клеток с общей стороной в разных прямоугольниках, неверно.

Таким образом, мы пришли к выводу, что должны существовать две клетки, одна из которых лежит в одном из нарисованных прямоугольников, а другая – в другом, и они имеют общую сторону.