В стране Оптимайзии все города соединены дорогами с односторонним движением (каждый с каждым). Докажите, что есть город, из которого в любой другой можно проехать не более чем за две поездки.


+ -

решение

Ваши ответы на задачу

ответов: 9

KoKos 2016-05-26 01:06:38 пишет:

[скрыто]

Tov Kronsteen 2016-05-25 18:12:04 пишет:

[скрыто]

igv105 2011-12-13 20:08:16 пишет:

[скрыто]

Админ: красиво!

малыш 2011-10-14 09:21:15 пишет:

из любого города можно проехать в любой другой город за 2 поездки!!!
Во первых городов не меньше 3(иначе бессмыслица получается)!!!
В каждом городе как минимум 2 дороги, и обязательно хотябы по одной можно заехать в город и хотябы по одной выехать!!!
допустим что в город, который нужно попасть не идет дороги, значит нужно найти город в который мы можем заехать из нашего города и из этого города можно добраться уже до конечного, куда нам нужно!!! при любых раскладах такие города есть!!! иначе были бы тупики

Админ: мало восклицательных знаков, не убедительно :)

я 2011-06-17 07:05:42 пишет:

в этой стране 4 города

Админ: почему?

Очевидность 2011-04-13 12:56:37 пишет:

Рассмотрим савокупность городов в стране-это граф. Вершины-города, ребра-дороги. Каждые 2 города соединены дорогой с односторонним движением. Из А вершины - выходит всего лишь одно ребро в другую вершину. В Б вершину - приходят n ребер (максимальное кол-во дорог) Если мы рассмотрим крайний случай: из А в Б вершину можно проехать не более чем за две поездки, значит А является тем самым "городом".

Reds on tour 2011-04-13 11:39:23 пишет:

Рассмотрим искомый город А: 1) Все дороги в другие города ведут ИЗ А (вернутся нельзя). Значит из А в любой другой доберешься за 1 поездку. Условию удовлетворяет. 2) Все дороги кроме одной ведут из А. Одна (скажем, из Б) - ведет в А. Тогда, чтобы попасть из А в Б, должно выполнять условие хотя бы одной дороги в Б. Если оно не выполняется, и все дороги ведут только из Б, следовательно Б - искомый город. 3) При равновесном варианте - 50% из, 50% в город, любой из городов страны будет соответствовать условию.

Кристина 2011-04-08 22:33:24 пишет:

если по пути не останавливаться в городах, то можно проехать за одну поездку... или если в этой стране всего два города

Админ: вопрос не об этом

Дмитрий 2011-04-06 11:00:58 пишет:

Что значит "односторонним движением (каждый с каждым)"? Каждый город соединен со всеми другими, но при этом направление дорог неизвестно?

Админ: именно так

Добавьте комментарий:

© 2009-201x Логические задачи