Дан связный граф на 2016 вершин. За одну операцию можно выбрать две вершины на максимальном (по количеству ребер) расстоянии и соединить ребром. Может ли после N операций максимальное расстояние оказаться больше S при: а) N = 1, S = 1100; б) N = 2, S = 2000; в) N = 3, S = 805; г) N = 1, S = 1700?

задан 13 Авг 10:31

Откуда эта задача? 5 дней назад задача появилась на беспринципных ресурсах, решающих за читеров олимпиадные задачи

(14 Авг 10:22) spades

Это задача из материалов ЛМШ-2016 за 6 класс

(14 Авг 10:25) ocelot335

6-й класс? Она явно не для шестиклассников
Ага, спасибо, нашел. Значит это я сильно поглупел))

(14 Авг 10:27) spades

Ну я её именно там нашёл.

(14 Авг 10:29) ocelot335

@spades: если кто-то включил задачу в список для 6 класса, это означает только то, что он знает решение, которое должно быть понятно в рамках знаний 6-классника. Но это не значит, что такое решение легко придумать.

(14 Авг 11:22) falcao
10|600 символов нужно символов осталось
0

а) Проведем из одной вершины три луча, на каждом из которых расположим примерно поровну оставшихся точек
в) Аналогично, только из вершины проведем 5 лучей. На каждом луче будет по 403 точки, 5 вершин тремя ребрами связными сделать не сможем, поэтому после трех процедур расстояние останется равным 806
г) Если после одной процедуры максимальное расстояние осталось больше 1700 - значит существовали три вершины А, В и С для которых r(AB), r(BC), r(AC) >=1700.
Возьмем точку, для которой сумма расстояний до А, В и С минимальна. Поскольку r - метрика, то выполняется неравенство треугольника: r(OA)+r(OB)>=r(AB), r(OA)+r(OC)>=r(AC), r(OC)+r(OB)>=r(CB). Откуда r(OA)+r(OB)+ r(OC)>=2550.
Поскольку суммарное расстояние до точек А, В и С превышает общее количество точек, то по крайней мере два из кратчайших путей из точки О до точек А, В и С пересекаются. Можно считать, что это пути из О к А и В и пусть точка пересечения O'. Тогда
r(O'A) = r(OA)-r(OO'),
r(O'B) = r(OB)-r(OO'),
r(O'С) <= r(OС)+r(OO')
Складывая эти неравенства получаем, что суммарное расстояние от O' до точек А, В и С меньше чем от точки О, что противоречит выбору точки О. Противоречие.

ссылка

отвечен 14 Авг 13:36

изменен 14 Авг 13:42

в г) я считал, что максимальный путь после операции остался в одной из ранее максимально удаленных вершин, но также возможен случай r(AB), r(CD) > 1700, но он вроде бы очевиден (?). По крайней мере, я его сразу отмел, из каких-то общих соображений...

(14 Авг 13:54) spades

В этом случае доказательство такое: схематично кратчайший путь от А к В и C к D можно представить AO-OO'-O'B и CO-OO'-O'D, где ОО' - общая часть путей. По условию оба пути больше 1700, скаладывая, получим, что длина общей части OO' больше чем 1700+1700-2016=1384, а значит на долю остальных четырех путей остается не более 732 вершин. Но тогда путь из С в D можно провести так: СО-ОА-АВ-BO'-O'D и он будет не длиннее 733.

(14 Авг 16:49) spades
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×480

задан
13 Авг 10:31

показан
107 раз

обновлен
14 Авг 16:51

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

по почте:

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

по RSS:

Ответы

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

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