Леонард Эйлер атындағы олимпиада,2014-2015 оқу жылы, қорытынды кезеңнің 1-ші туры

Квадраттың әр қабырғасынан 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 параллельных и равных между собой отрезков примера.