В городе 111 автобусных маршрутов. Известно, что:
1. с любой остановки на любую другую остановку можно попасть без пересадки
2. для любой пары маршрутов найдется, и притом только одна, остановка, на которой можно пересесть с одного из этих маршрутов на другой
3. на каждом маршруте не менее трёх остановок.

Сколько остановок имеет каждый из 111 маршрутов?

3

а нетт

111?

111+1

Футбольные команды сыграли друг с другом в один круг. Получилось 111 туров. Сколько команд приняло участие в турнире?

(5) твоя задача не корректна, а моя корректна

111-1=110

(6) Все равно в (4) правильный ответ.

(8) конечно же нет

только у меня сомнения, что условие 1. выполнимо при остальных
(4) если у любой ветки 112 остановок, то условие 2. не выполнимо

110 маршрутов по 56 остановок и 1 по 110?

(0) есть вариант 110 по 3 и 1 по 110

(11)(12) вы это от потолка придумываете?

(13) а с чего ты это взял? я написал "есть вариант". он у меня на потолке не нарисован

(14) ну это неверный вариант

(13) квадратная сетка 56х56, две крайних смежных стороны - один маршрут

(15) а, кстати да

(16) остановки на диагоналях квадратов сетки не имеют общего маршрута

(18) Ах да, с любой остановки на любую без пересадки.
Тогда я не понял:
из условия 1 следует, что все остановки должны лежать на одном маршруте, тогда любой другой маршрут будет пересекать первый как минимум на трех остановках, что противоречит 2.

(0) Гугль знает все, и то, что остановок 11... Не зря на ЕГЭ запрещают им пользоваться ;)

(19) "из условия 1 следует, что все остановки должны лежать на одном маршруте" - чушь
(20) читерство не приветствуется

(21) Дык поэтому я решение и не привел. Подразумевается, что главное не ответ, не так ли?

P.S. Использование уже накопленных знаний - не читерство. Если бы каждый ученый изобретал велосипед - наука бы на месте стояла. Да и вообще, это получилось случайно - я искал теорию графов, а там в примерах очень похожая задачка, что я мог поделать? ;)

(22) согласен, ответ не главное

давать подсказку?

(24) Пока не надо.

Всего 111 маршрутов. Пар маршрутов 111*110/2=6105
Каждая пара пересекается на отдельной остановке.
Значит всего пересадочных остановок 6105.
Каждый маршрут пересекается с каждым. То есть в каждом маршруте не меньше 110 станций. Что и дает 6105 пересадочных остановок.
Теперь осталось доказать что не может быть остановок без пересадок. Если есть остановка без пересадок, то так как с неё можно добраться до любой станции, то должен быть маршрут содержащий все станции, причем естественно только один. Но так как с каждым из остальных маршрутов он должен пересекаться только на одной станции, то выходит что все остальные станции состоят только из одной остановки. Что противоречит условию.

(26)
>Каждый маршрут пересекается с каждым. То есть в каждом маршруте не меньше 110 станций.

Не обязательно. На одной станции можно пересечься несколькими маршрутами.

(27) Да, меня сглюкнуло.

(27)(28) Можем взять любые две станции, и слить их в одну.
То есть решение не одно, а их много.

вот один из вариантов - 110 маршрутов по 2 станции и один маршрут из 110 станций.

вариантов, соответственно, можно кучу сделать

всего в городе 111 остановок

(31) Вариант с пересечением в одной станции максимум двух маршрутов единственный - (26)
Вариант (30) не проходит по третьему условию.
И думаю просто в условии ошибка, забыли написать что на одной станции максимум одна пересадка.

(32) тогда 110 маршрутов по 3 остановки и один с 220.

а, не кольцо и разомкнутое кольцо не подходят - только одна пересадка

(32) нет там ошибки такой

(31) всего да, хотя и неочевидно

(36) Чем вариант (26) плох? Или условие с любой на любую не пройдет?

(37) "Каждая пара пересекается на отдельной остановке" это неверно, там может быть более 2-х маршрутов на одной остановке

10
Конечная геометрия?!

10*10+10+1=111

Ой. Ответ 10+1=11

(39) да

На самом деле задача некорректна, для 111 маршрутов такой системы нет.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8684

Неправильное я число подобрал, жаль.

Для 73 есть или для 133

(38) Этот пункт никак не может отмести решение в (26)

(0) 5000 на каждом маршруте.

(43) Минимальное число маршрутов и остановок, удовлетворяющее условиям задачи, это 7/7, полагаю.

(44) вот пусть есть общая остановка для маршрутов 1 и 2, обозначим её (1;2) и есть остановка (3;4) какой маршрут их соединяет?

(47) см. вопрос в (37)

(48) или я не понимаю или "1. с любой остановки на любую другую остановку можно попасть без пересадки"
где у тебя так?

(49) Я и пишу, что это правило наверно не выполнится.

Непонятки: на одной остановке могут пересечься толька 2 маршрута или больше?

(0) у тс снова условие кривое: одновременное выполнение пунктов 1 и 2 означает, что:
1. есть маршрут, который содержит все остановки
2. все другие маршруты содержат только 1 остановку (уже бред)
3. пунк автоматом идет лесом

(52) Нет там такого условия. Пункт 1. звучит совсем иначе.
Для любой пары остановок существует маршрут их содержащий. Разницы не видишь? Это не значит что все пары остановок собраны в одном маршруте.

(0) Маршруты идут по одному кругу, а остановок на одну меньше, чем маршрутов, т.е. 110

+(54), хотя не, там ограничение по пересадкам, в 1 остановку, надо подумать

+(54) и еще я подумал, сколько в сумме остановок

Посидел подумал и не понял, зачем цифра 111.
Представьте три маршрута в вите трех лучей из центра (типа знака Мерседеса).
Удовлетворяет всем трем условиям задачи. Все маршруты пересекаются в одной точке, которая является общей пересадкой, и в то же время она только одна. И из всех точек можно попасть во все без пересадки.
111 тут или 3 маршрута не важно, т.к. можно сделать больше лучей из центра и все равно 3 остановки

Или вопрос именно в том, сколько всего остановок в городе, а не на маршрутах?

(57) Прикольно.

(57) А как с одного луча попасть на другой без пересадки?

(60) Начал разбирать и понял, что не одна точка пересадки получается)

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

(62) твой первый вывод ошибочен

(63) тогда не выполнится первое условие

(63) давай ответ короче с объяснением, раб день кончается))

Чтобы не было еще новых "опровержений" условия приведу пример, заменив в условии 111 на 7.
Всего 7 условий и 7 остановок, на каждом маршруте по 3 остановки:
http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Fano_plane.svg/600px-Fano_plane.svg.png

+(66) 7 маршрутов и 7 остановок

(67) осталось прописать, где там маршруты

(67) это задача или ее решение (если решение то ничего не понятно

(66) есть какое-то читерство в том, что маршруты могут пересекаться или идти по одному пути, если без общих остановок сколько угодно раз

(68) маршруты там прямые и окружность, всего 7

(69) это пример для малых значений, решения нет, извините, я ошибся, см (43)

(53) да, протупил

в любом случае, расходимся, нас на****ли

1 пункт некорректен

(74) каждая сволочь хочет об этом написать, см пример (66)