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