Леонард Эйлер атындағы олимпиада,
2014-2015 оқу жылы, қорытынды кезеңнің 1-ші туры
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1. Ответ. При k=150.
Оценка. Допустим, возможен пример с k>150. Сопоставим ему таблицу 200×200, строки которой соответствуют горизонтальным отрезкам (упорядоченным снизу вверх), а столбцы — вертикальным (упорядоченным слева направо). В ячейке таблицы стоит 1, если соответствующие отрезки пересекаются, и 0 — если нет. По нашему предположению в каждой строке и каждом столбце по 200−k<50 нулей. Заметим, что среди строк от 51 до 150 есть хотя бы одна, которая и начинается, и заканчивается на 1 (иначе мы имеем в первом и последнем столбцах вместе минимум 100 нулей).
Соответствующий ей горизонтальный отрезок T пересекает как самый левый, так и самый правый вертикальные отрезки. Но в этой строке есть и нолики, значит, некоторый отрезок X «недотягивает» до T сверху или снизу. Тогда в соответствующем отрезку X столбце либо сверху, либо снизу от нашей строки стоят только нули, а, значит, их не менее 50. Противоречие.
На рисунке ниже каждый из отрезков изображает 50 параллельных и равных между собой отрезков примера.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.