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