В стране 150 городов. Некоторые соединены дорогами (1 дорога проходит только через 2 города). Из любых 4-х городов можно выделить 2 пары так, чтобы каждая пара была соединена дорогой. Найти минимальное кол-во дорог.

задан 25 Фев '15 0:29

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

Текст решения восстановлен.

Если вершина $%a$% не соединена с $%b$%, $%c$%, $%d$%, то для четвёрки этих городов не найдётся соединения по парам. Значит, каждый город соединён по меньшей мере со 147 городами, и всего дорог не менее $%\frac{150\cdot147}2=11025$%.

Пример соединения с таким количеством дорог: рассматриваем 150-угольник, и в качестве соединений не берём его стороны, а берём все диагонали. Их оказывается именно столько, сколько указано выше. При этом любая четвёрка городов $%a$%, $%b$%, $%c$%, $%d$% в порядке следования по кругу может быть соединена попарно диагоналями $%a-c$% и $%b-d$%.

ссылка

отвечен 25 Фев '15 1:50

изменен 28 Мар '15 5:29

@falcao: эта задача предлагалась в этом году на олимпиаде СПбГУ. Существует несколько дат проведения в разных городах (я писала в самую первую 22.02 (в Питере)) и выложила свой вариант. Мой друг поехал на иную площадку. Сегодня прислал вариант, и, как оказалось, задания те же самые! Прошу вас удалить ответ во избежание утечки заданий! (в прошлом году везде варианты были разные, можете посмотреть на сайте).

(26 Фев '15 22:49) stander

@stander: сейчас обычно стараются "синхронизировать" сроки -- скажем, так бывает на областном туре школьной олимпиады. Если этого не сделать, то всё тут же "просочится" в соцсетях. А у удалённых ответов остаётся копия в "кэше", и так далее.

В принципе, это сравнительно простая задача. Но если Вы считаете уместным удалить решение, не удаляя сам вопрос, я могу это сделать (а потом, когда все туры пройдут, поместить снова, чтобы не пропадало).

(26 Фев '15 23:14) falcao

Я считаю - удалять ничего не надо. Организаторы олимпиад должны учитывать соцсети

(26 Фев '15 23:19) Роман83

@Роман83: я вообще-то тоже не люблю удалять уже написанное, но в данном случае готов сделать исключение из правила.

Сейчас надо прилагать большие усилия во избежание "утечек". Люди стали очень "изощрённые", организаторы не всегда с этим справляются :)

(26 Фев '15 23:24) falcao

@falcao: у меня решена ровно половина. Поэтому, возможно, решается вопрос о моем ЧЕСТНО заработанном призерстве. 22 марта -- последний день (площадка - Москва).

(27 Фев '15 0:04) stander

Какие книги или статьи по графам можно почитать, чтобы научиться решать задачи приблизительно такого же уровня?

Например, в списке рекомендованной литературы часто пишут книгу Оре "Теория графов". Книгу купил, но там - "сухая" теория и научиться решать олимпиадные задачи по графам используя только Оре не реально.

(28 Мар '15 20:03) Роман83

@Роман83: боюсь, что при решении задач на знакомства или задач приведённого здесь типа, никакие книги не помогут. Теоретических сведений, нужных для их решения, очень мало, и они общеизвестны. Однако задачи на эту тему могут быть весьма трудными (я знаю много таких примеров). Получается странная вещь: вроде бы вся "база" есть, всё понятно, а решить иной раз очень долго не можешь.

(28 Мар '15 20:16) falcao

@falcao: спасибо.

(28 Мар '15 20:18) Роман83
1

@Роман83: если хотите подумать,могу такую задачу предложить. Она известная, поэтому я не хочу её делать специальным вопросом. Но это пример относительно сложной задачи о знакомствах, как мне представляется.

Есть 12 человек, и среди любых 9 найдутся 5, которые попарно знакомы. Доказать, что найдутся 6 попарно знакомых.

(28 Мар '15 20:34) falcao
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×3,339
×477
×337

задан
25 Фев '15 0:29

показан
726 раз

обновлен
28 Мар '15 20:34

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

по почте:

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

по RSS:

Ответы

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

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