2014-06-08
На клетчатой бумаге отмечены произвольные $n$ клеток. Доказать, что из них всегда можно выбрать не менее чем $n/4$ клеток, попарно не соприкасающихся друг с другом (соприкасающимися считаются клетки, имеющие хотя бы одну общую вершину).
Решение:
Разобьем всю плоскость на одинаковые квадраты, состоящие из четырех клеток каждый. Далее, в каждом из этих квадратов «левую верхнюю» клетку назовем черной, «правую верхнюю» - белой, «левую нижнюю» - красной, а «правую нижнюю» - синей. Тогда, с одной стороны, любые две клетки одного цвета не соприкасаются. С другой стороны, среди отмеченных клеток можно выбрать не менее четверти таких, которые имеют одинаковый цвет (в противном случае всего клеток было бы менее чем $4 \cdot (n/4) = n$).