|
|
 |
Условие
Изначально на белой клетчатой плоскости конечное число клеток окрашено в чёрный цвет. На плоскости лежит бумажный клетчатый многоугольник $M$, в котором больше одной клетки. Его можно сдвигать, не поворачивая, в любом направлении на любое расстояние, но так, чтобы после сдвига он лежал "по клеткам". Если после очередного сдвига ровно одна клетка у $M$ лежит на белой клетке плоскости, эту белую клетку окрашивают в чёрный цвет и делают следующий сдвиг. Докажите, что существует такая белая клетка, которая никогда не будет окрашена в чёрный цвет, сколько бы раз мы ни сдвигали $M$ по описанным правилам.
Решение
Центры клеток $M$ будем называть узлами. Рассмотрим выпуклую оболочку $V$ узлов. Можно считать, что одна из сторон $V$ горизонтальна и $V$ лежит над ней.
Проведём горизонтальную прямую $l$ ниже $V$ и докажем, что ни одна клетка ниже $l$ не будет окрашена. Действительно, в момент, когда первая такая клетка $K$ будет окрашена, в неё попадёт узел из $M$. Но другой узел из $M$ окажется на той же высоте или ниже. Следовательно, клетка $K$ в этот момент окрашена не будет.
Замечания
1. Связность фигуры-шаблона не важна. Если фигура не помещается ни в горизонталь, ни в вертикаль, то окрашено будет конечное число клеток.
2. 8 баллов.
