Всем привет!
Многие проголосовали за разбор геометрических задач с Romanian Masters of Mathematics этого года. Сегодня разберу пятую задачу, по комбинаторной геометрии. Мне она показалась не очень трудной, хотя если углубляться во все детали, то писанины может выйти очень много.
Посмотреть на геометрические задачи RMofM-2020 можно тут. Следить за публикациями и влиять на порядок разбора задач можно на телеграм-канале Олимпиадная геометрия.
Напомню условие.
По сути в задаче требуется доказать, что к любому выпуклому многоугольнику с вершинами в целых точках можно добавить целую вершину так, чтобы многоугольник остался выпуклым, при этом старые вершины могли бы попасть на границу нового многоугольника.
Где может лежать потенциально дополнительная вершина? Ну понятно, надо взять сторону AB, провести соседние с ней стороны и посмотреть, какая образуется область, примыкающая по отрезку AB к многоугольнику. Именно в этой области хочется найти дополнительную вершину.
Если область оказывается неограниченной, то утверждение, с одной стороны, более или менее очевидно, а, с другой стороны, может быть проверено рассуждениями, аналогичными приведенным ниже. Поэтому давайте предполагать, что сторона многоугольника и продолжения двух соседствующих с ней всегда образуют треугольник, примыкающий снаружи к многоугольнику.
Наша задача найти целую точку, лежащую внутри одного из таких треугольников, но не лежащую на границе исходного многоугольника. Интуитивно понятно, что хочется найти точку в каком-то смысле ближайшую к границе многоугольника. Так сделаем же это.
Для каждой стороны AB многоугольника рассмотрим целую точку (одну из), ближайшую к прямой AB, но не лежащую на AB. На самом деле можно даже найти соответствующее расстояние исходя из формулы Пика и числа целых точек, попавших на отрезок AB, но нам это не понадобится. Среди ближайших точек существует точка, лежащая снаружи от многоугольника, проекция которой на прямую AB лежит на отрезке AB. Действительно, точки можно отражать относительно середины AB и сдвигать на вектор, идущий по отрезку AB. Такими операциями всегда можно добиться желаемого.
Итак, для каждой стороны построили такую точку. Возьмем теперь минимальное из получившихся расстояний. Пусть оно получилось как раз у отрезка AB и точки X. Утверждается, что точка X тогда искомая.
Если это не так, то точка X не попадает внутрь треугольника, построенного выше по стороне AB. Обозначим вершины, соседние с A и B через C и D соответственно. Тогда либо точка A содержится строго внутри треугольника BXC, либо точка B содержится строго внутри треугольника AXD (либо и то и другое одновременно). Предположим, что точка A содержится внутри треугольника BXC.
Но тогда расстояние от точки X до прямой CA меньше расстояния от точки X до прямой AB, поскольку перпендикуляр короче наклонной. Это противоречит выбору точки X и завершает доказательство.