Задача
Некоторые клетки белого прямоугольника размером 3×7 произвольным образом покрасили в чёрный цвет. Докажите, что обязательно найдутся четыре клетки одного цвета, центры которых являются вершинами некоторого прямоугольника со сторонами, параллельными сторонам исходного прямоугольника.
Решение
Рассмотрим первые две строки. Если в образованном ими прямоугольнике два столбца белые (чёрные), то нужный прямоугольник найден.
В противном случае по крайней мере в пяти столбцах расположены клетки разного цвета. Тогда, не менее чем в трёх столбцах чёрная и белая клетки будут располагаться в одинаковом порядке, например, сверху – чёрная, снизу – белая.
Рассмотрим три эти столбца и третью строку. В третьей строке в рассмотренных столбцах есть хотя бы две клетки одного цвета. Если они чёрные, то искомый прямоугольник образуют их центры и центры чёрных клеток первой строки, а если они белые, то искомый прямоугольник образуют их центры вместе с центрами белых клеток второй строки.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь