Олимпиада имени Леонарда Эйлера2014-2015 учебный год, I тур заключительного этапа

На каждой стороне квадрата выбрано по 100 точек, из каждой выбранной точки внутрь квадрата проведён отрезок, перпендикулярный соответствующей стороне квадрата. Оказалось, что никакие два из проведённых отрезков не лежат на одной прямой. Отметим все точки пересечения этих отрезков. При каком наибольшем $k < 200$ может случиться так, что на каждом проведённом отрезке лежит ровно $k$ отмеченных точек? ( И. Богданов, Н. Авилов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. При $k = 150$.
Оценка. Допустим, возможен пример с $k > 150$. Сопоставим ему таблицу $200 \times 200$, строки которой соответствуют горизонтальным отрезкам (упорядоченным снизу вверх), а столбцы — вертикальным (упорядоченным слева направо). В ячейке таблицы стоит $1$, если соответствующие отрезки пересекаются, и $0$ — если нет. По нашему предположению в каждой строке и каждом столбце по $200 - k < 50$ нулей. Заметим, что среди строк от $51$ до $150$ есть хотя бы одна, которая и начинается, и заканчивается на $1$ (иначе мы имеем в первом и последнем столбцах вместе минимум $100$ нулей).
Соответствующий ей горизонтальный отрезок $T$ пересекает как самый левый, так и самый правый вертикальные отрезки. Но в этой строке есть и нолики, значит, некоторый отрезок $X$ «недотягивает» до $T$ сверху или снизу. Тогда в соответствующем отрезку $X$ столбце либо сверху, либо снизу от нашей строки стоят только нули, а, значит, их не менее 50. Противоречие. На рисунке ниже каждый из отрезков изображает 50 параллельных и равных между собой отрезков примера.