2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Многоугольники из точек на окружности
Сообщение08.11.2017, 23:53 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Многоугольники из точек на окружности
Сообщение09.11.2017, 00:00 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Многоугольники из точек на окружности
Сообщение09.11.2017, 01:36 
Аватара пользователя


01/12/11
6803
Ярдена Шуламит, шуламила и будет шуламить!
Dmitriy40
Большое спасибо!

 Профиль  
                  
 
 Re: Многоугольники из точек на окружности
Сообщение10.12.2017, 20:42 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Многоугольники из точек на окружности
Сообщение10.12.2017, 21:42 
Заслуженный участник


20/08/14
4545
Россия, Москва
Null в сообщении #1273760 писал(а):
Не рассмотрен случай когда у шестиугольника и квадрата нет общих вершин.
А его и не надо рассматривать, т.к. при этом количество точек не может уменьшиться, они обе в любом случае не попадут в пятиугольник одновременно, зато обе уйдут из шестиугольника.
Можно сказать я писал не полное доказательство, а лишь подсчёт минимума, пропуская очевидные моменты (несовпадение точек пятиугольника с любыми прочими фигурами). Возможно это стоило оговорить явно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group