Пересечение отрезков и прямых
Ошибка.
Попробуйте повторить позже
На плоскости нарисована замкнутая 222-звенная ломаная. Известно, что два соседних звена ломаной перпендикулярны друг другу, а также никакие два звена ломаной не лежат на одной прямой. Какое наибольшее количество точек самопересечений может иметь такая ломаная?
Источники:
Подсказка 1
Сразу же можно заметить, что у нас отрезки ломаной имеют всего 2 направления. Тогда можем для удобства рассмотреть такую плоскость, что одни отрезки горизонтальные, а другие — вертикальные. Тогда какие отрезки пересекаются в каждой точке самопересечения и сколько всего отрезков каждого вида?
Подсказка 2
Да, верно! Каждая точка самопересечения — это пересечение вертикального и горизонтального отрезка, а каждого типа по 111 штук. Пронумеруем горизонтальные отрезки и посмотрим на произвольный (пусть k-ый) из них. Попробуйте оценить, сколько точек самопересечения с горизонтальными отрезками выше k-ого образуют вертикальные отрезки, пересекающий данный.
Подсказка 3
Точно! Не более 2(k-1) точек самопересечения. Отлично! Теперь мы можем оценить общее кол-во точек самопересечения. Однако наша оценка работает хорошо только для первой половины отрезков. Попробуйте для второй половину оценить аналогично, только снизу.
Подсказка 4
Так, попробуем ещё докрутить оценку для центрального (то есть 56-ого) горизонтального отрезка. У нас из всех 111 вертикальных отрезка 2 выходят из нашего. Тогда как мы можем оценить кол-во точек пересечения для 56-ого горизонтального отрезка?
Подсказка 5
Мы получаем не больше 109 точек самопересечения. Тогда всего таких точек не больше 6049. Осталось построить пример так, чтобы на каждом ходу нашей оценки выполнялось равенство.
Оценка. Для начала докажем, что больше 
самопересечений быть не может. Назовём звенья одного направления горизонтальными, а
звенья второго направления — вертикальными. Расположим плоскость так, чтобы горизонтальные звенья действительно стали
горизонтальными. Заметим сразу две вещи:
каждая точка самопересечения — это пересечение вертикального и горизонтального звена; 
горизонтальные и вертикальные звенья
чередуются, поэтому каждых по 
штук.
Пронумеруем сверху вниз горизонтальные звенья от 
до 
. Посмотрим на звено с номером 
. Каждое пересекающее его
вертикальное ребро должно иметь над ним конец, совпадающий с концов некоторого горизонтального ребра. Горизонтальных рёбер выше
всего 
, поэтому на 
-м ребре не более 
точек самопересечений. Эта оценка хорошо работает для 
от 
до 
: на них
суммарно не более
точек самопересечений. Аналогичными рассуждениями (но рассматривая нижние концы вертикальных звений) доказывается, что и на
звеньях с 
по 
суммарно не более 
точек самопересечений.
Для ребра с номером 
немного улучшим оценку: всего существует 
вертикальных рёбер, но два из них выходят из концов 
-го
звена, поэтому не могут его пересекать. Итого, на 
звене не более 
точек самопересечений. Значит, суммарно их не больше
Пример. Пронумеруем и вертикальные звенья тоже. Пусть 
-е вертикальное ребро соединяет 
и 
горизонтальные звенья; 
-е
вертикальное ребро — 
и 
горизонтальные звенья; 
-е вертикальное ребро — 
и 
горизонтальные звенья; 
-е
вертикальное ребро — 
и 
горизонтальные звенья; 
-е вертикальное ребро — 
и 
горизонтальные звенья; 
-е
вертикальное ребро — 
и 
горизонтальные звенья; 
-е вертикальное ребро — 
и 
горизонтальные звенья; 
-е
вертикальное ребро — 
и 
горизонтальные звенья; 
-е вертикальное ребро — 
и 
горизонтальные
звенья.
Аналогичный пример для 
-звенной ломаной на картинке ниже:
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
