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

Проект МЦНМО
при участии
школы 57
Задача 65956
Темы:    [ Раскраски ]
[ Принцип Дирихле (прочее) ]
Сложность: 4-
Классы: 8,9
В корзину
Прислать комментарий

Условие

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


Решение

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

Замечания

9 баллов

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

олимпиада
Название Московская математическая регата
год
Год 2016/17
класс
Класс 8
задача
Номер 8.4.3

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

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