Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя RodionGork

Автор RodionGork, 10 лет назад, По-русски

Если соединять вершины пятиугольника отрезками через одну, получается звездочка с 5 пересечениями между этими отрезками, как в детстве рисовали.

Если взять семиугольник, то вершины можно соединять через одну или через две. Получатся разные звёздочки с 7 или 14 пересечениями, если я не ошибаюсь. Ну и так далее.

А правда ли что для любых построенных таким образом звёздочек (ну по крайней мере если число вершин и шаг соединения вершин — который 1 для N-угольника и 2 для пятиконечной звезды — взаимнопросты) никакие три отрезка не будут пересекаться в одной точке?

UPD: спасибо Sammarize за уточнение — речь о правильных многоугольниках и звёздах, конечно.

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Если многоугольник произвольный, то конечно неправда. Что нам мешает рассмотреть три пересекающихся отрезка AB, CD и EF, а потом рассмотреть семиугольник ACEBDFG (с произвольным G)?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, спасибо за уточненние — правильный многоугольник конечно.

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Может немного не по теме, но когда придумывал вот эту задачу для школьников, то нашли доказательство факта, что в случае нечётного числа сторон у правильного многоугольника не будет ни одной точки, в которой пересекутся более двух диагоналей.

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    Занятно... Я почти ту же задачу придумал (но видимо гораздо позже — только вчера) и этим вопросом естественно заинтересовался. А что, с чётным числом лучей есть контрпримеры? Например звёзды типа 8-3 или 16-5 (подразумевая что пентаграмма описывается формулой 5-2) — они тоже одной ломанной линией описываются (в отличие от звезды давида скажем или восьмиконечной звезды 8-2)

    UPD: а, понял, для вашей задачи действительно контрпримером будет хотя бы восьмиугольник, из-за того что проводятся все возможные диагонали.

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Если я не ошибаюсь, три такие диагонали могут пересекаться только в центре. Действительно, пусть разные диагонали AB, CD, EF проходят через точку X.

Понятно, что все эти точки различны (иначе две диагонали пересекаются в вершине, т. е. третья тоже должна проходить через вершину; легко понять, что это невозможно).

Так как точки A, B, C, D, E и F лежат на одной окружности, то AX * XB = CX * XD = EX * XF (всё это есть минус степень X относительно окружности. Но также AX + XB = CX + XD = EX + XF, так как AB = CD = EF (их можно перевести друг в друга поворотами).

Но по теореме Виета система уравнений вида x + y = a, xy = b имеет не более двух решений, а если их ровно два, то они отличаютя перестановкой x и y.

Отсюда легко понять, что три из точек A, B, C, D, E, F равноудалены от X, т. е. X — центр описанной окружности нашего правильного многоугольника. Тогда все наши диагонали являются диаметрами описаанной окружности многоугольника.