Question

ДАЮ 100 БАЛЛОВ На шахматной доске 8х8 нарисованы по клеточкам 17 не налегающих друг на друга двухклеточных прямоугольников. Докажите, что на доске найдутся две имеющие общую сторону клетки, одна из которых лежит в одном из нарисованных прямоугольников, а другая — в другом.

Answer 1

Ответ:

Наличие искомых клеток возможно только при соприкасающихся прямоугольниках.

Объяснение:

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

Answer 2

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

Рассмотрим доску, как шахматную доску, где каждая клетка представляет одно из четырёх цветов (допустим, черный, белый, красный и синий), чтобы избежать конфликтов между прямоугольниками. Раскрасим клетки доски в следующем порядке:

1. Каждый прямоугольник начнём с одной клетки черного цвета, затем переключимся на белый цвет для следующей клетки.
2. Каждый следующий прямоугольник начнём с одной клетки красного цвета, затем переключимся на синий цвет для следующей клетки.

Таким образом, каждый двухклеточный прямоугольник будет занимать две клетки разных цветов (например, черный и белый), и не будет иметь общих сторон с другими прямоугольниками. Всего у нас есть 17 таких прямоугольников, и такая раскраска доски позволит нам избежать общих сторон между прямоугольниками.

Однако у нас всего четыре различных цвета, и поскольку доска 8x8 имеет 32 клетки одного цвета и 31 клетку другого цвета, то как минимум две клетки разного цвета будут иметь общую сторону.

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