Многоугольники из точек на окружности

[Ktina]

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

[Dmitriy40]

Треугольник поглощается шестиугольником, лишних точек не нужно.
Для квадрата можно использовать две точки шестиугольника (любые противоположные), нужно ещё две.
Для пятиугольника из 8-ми точек можно использовать максимум одну, нужно ещё 4.
Итого надо 12 точек.

[Ktina]

Dmitriy40
Большое спасибо!

[Null]

Dmitriy40 в сообщении #1263662 писал(а):

Треугольник поглощается шестиугольником, лишних точек не нужно.
Для квадрата можно использовать две точки шестиугольника (любые противоположные), нужно ещё две.
Для пятиугольника из 8-ми точек можно использовать максимум одну, нужно ещё 4.
Итого надо 12 точек.

Не рассмотрен случай когда у шестиугольника и квадрата нет общих вершин. Жадный алгоритм не обязан работать.

[Dmitriy40]

Null в сообщении #1273760 писал(а):

Не рассмотрен случай когда у шестиугольника и квадрата нет общих вершин.

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