2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.





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


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

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


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

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


01/12/11
6092
Нацерет-Иллит
Dmitriy40
Большое спасибо!

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


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

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

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


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

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

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



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

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


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

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