На плоскости дано N точек. Оказалось, что между ними ровно n различных расстояний . Докажите , что N <= n^2 + 2.

задан 23 Июн '16 16:39

10|600 символов нужно символов осталось
1

Рассмотрим две точки. Все остальные точки - это точки пересечения двух множеств концентрических окружностей. Получаем оценку $%2n^2+2$%.

ссылка

отвечен 23 Июн '16 17:19

Истинно олимпиадное решение: коротко, и очень красиво!

(23 Июн '16 18:12) falcao
2

Нужна оценка n^2+2, а не 2n^2 + 2

(23 Июн '16 18:50) Xela
2

Xela: рассмотрим не какие попало две точки, а образующие сторону выпуклой оболочки. Тогда половина точек пересечения окружностей заведомо не принадлежит нашему множеству.

(23 Июн '16 19:00) Fedor Petrov
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×135

задан
23 Июн '16 16:39

показан
686 раз

обновлен
23 Июн '16 19:00

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru