2014-06-08
а) Пусть каждая клетка прямоугольной доски размером $4 \times 7$ окрашена в белый или черный цвет. Доказать, что на доске обязательно найдется прямоугольник, образованный горизонтальными и вертикальными линиями доски, все четыре угловые клетки которого окрашены в одинаковый цвет.
б) Привести пример раскраски прямоугольной доски размером $4 \times 6$, для которой указанного в п. а) прямоугольника не существует.
Решение:
а) Рассмотрим всевозможные пары одноцветных клеток, расположенных в одном столбце (считаем, что столбцы имеют высоту 4, а строки - длину 7). В каждом столбце имеется не менее двух таких пар, а значит, всего на доске их по крайней мере 14. Следовательно, существует такой цвет, который имеют не менее 7 из рассматриваемых пар. Так как количество вариантов расположения пары клеток в столбце равно 6, то существуют два столбца с одноцветными одинаково расположенными парами, что и требовалось доказать.
б) См. рис.