На плоскости отметили 4n точек, после чего соединили отрезками все пары точек, расстояние между которыми равно одному. Оказалось, что среди любых n + 1 точек обязательно есть две, соединённые отрезком. Докажите, что всего проведено не менее 26n/3 отрезков.

задан 23 Сен '15 22:46

Первый вопрос, который сразу же возникает, состоит в том, возможна ли такая конфигурация, и если да, то при каких n? Ясно, что при n=1 такой конструкции на плоскости нет, и тогда из условия следует что угодно. При n=2 понятно как построить 7 точек; по-видимому, 8 уже нельзя.

Вот здесь разбирается задача, где сначала даётся оценка 6n, а далее она усилена до 7n. Возможно, её как-то можно усилить ещё за счёт применения похожих приёмов.

(25 Сен '15 22:39) falcao

@falcao интересно, что оценки получаются не сразу, а последовательно, но если для 5 и 6 способ один, то с 7 вводятся дополнительные понятия, видимо для более продвинутой оценки указанной в условии нужно еще какие-то идеи из дистанционных графов применять

(26 Сен '15 3:42) sapere aude
1

@sapere aude: оценка 6n верна для любого случая, и она оптимальна, то есть там просто не надо использовать плоскую специфику (берём n тетраэдров). А дальше уже используются какие-то свойства плоских графов, но как бы по минимуму. Есть ощущение, что аналогичными средствами эту оценку можно ещё усилить. Но я пока не придумал конкретного способа.

(26 Сен '15 8:58) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,231
×164

задан
23 Сен '15 22:46

показан
385 раз

обновлен
26 Сен '15 8:58

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

по почте:

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

по RSS:

Ответы

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

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