ПитерГор 2014 и ранее

Давайте попробуем для начала угадать ответ. При каком варианте расположения прямых мы точно покроем ими все узлы? Наверное, когда эти прямые будут идти только по вертикальным или горизонтальным линиям сетки. Давайте считать, что вертикальными, потом нам ещё понадобится это дальше по решению. Но тогда количество таких прямых будет не больше, чем из-за того, что диагональ равна Теперь подумаем, не может ли быть меньшее количество прямых?
Давайте докажем сначала, что прямых не хватит. Построим контрпример. Возьмём координатную плоскость и расположим квадрат, диагональ которого расположена на оси от точки до Его сторона равна поэтому его можно накрыть салфеткой со стороной Проверим, что узлы, принадлежащие квадрату, нельзя покрыть прямыми. На диагонали расположено узла. Если диагональ не лежит ни на одной из проведённых прямых, то эти узлы должны покрываться различными прямыми, что невозможно, поскольку прямых всего Поэтому прямая обязательно проведена. Теперь докажем по индукции, что при проведены прямые База уже проверена. Установим переход от к По предположению индукции уже проведены прямые

(всего прямая). Рассмотрим очередную прямую на ней лежит узлов(на каждом шаге их количество уменьшается на 2). Если она не проведена, то эти узлы покрыты различными прямыми, что невозможно, поскольку нам осталось провести прямых. Значит, она проведена. Аналогично должна быть проведена и прямая Итак мы установили, что заведомо проведено прямых. Но при этом точки и всё ещё остались непокрытыми. Они являются вершинами прямоугольника и поэтому не могут быть покрыты одной прямой.

Мы поняли, что меньше, чем прямыми, мы не покроем все узлы. Тогда вопрос, хватит ли нам вертикальной прямой(если забыли почему столько, посмотрите начало решения)? Давайте докажем лемму, что на самом деле если мы покрыли все узлы вертикальными прямыми, то мы можем покрыть все узлы и прямой. Но сделаем это немного по-хитрому.
Лемма. Если салфетку можно накрыть вертикальными прямыми, то самая левая и самая правая из них содержат ровно по одному узлу, накрытому салфеткой.
Доказательство. Предположим, что это не так. Рассмотрим проекции двух смежных сторон салфетки на горизонтальную прямую. Обозначим их за и Тогда на одной из крайних прямых оказалось два или более узла. В таком случае прямая отсекает от салфетки прямоугольный треугольник с гипотенузой, не меньшей Высота этого треугольника не превосходит (так как мы рассматриваем самую правую прямую). Рассмотрим треугольник, который будет образован вертикальной прямой, проходящей через самую правую верхнюю или нижнюю вершину. Образовался снова прямоугольный треугольник подобный нашему исходному. Его же гипотенуза не превосходит диагонали квадрата, а высота равна или и значит, не меньше Мы знаем, что Тогда

т.е. и Записывая пропорциональность высот и гипотенуз в подобных треугольниках и получаем С другой стороны, — противоречие.

Лемма доказана, и тогда получается, что при накрытие вертикальными прямыми они обязательно проходят через два узла в противоположных вершинах квадрата. Но тогда мы можем просто накрыть эти два узла одной прямой, проходящей через диагональ. Победа, мы покрыли узлы прямой!