Учеба и наука
В Стране 400 городов. Любые два города Страны соединены дорогой. От Страны отделилась независимая Республика, причем количество дорог, соединяющих города этой Республики, равно количеству дорог, - вопрос №1807390
ведущих из Республики в остальные города Страны. Сколько городов в Республике?
январь 17, 2016 г.
-
Всего ответов: 2
-
Выведем формулу подсчета количества дорог в республике, в которой m городов
Пронумеруем города от одного до m.
Нужно посчитать количество неповторяющихся пар чисел (x, y), где
x <> y
1 <= x < m
1 < y <= m
(1, 1) (1, 2) … (1, m)
(2, 3) (2, 4)… (2, m)
..
(m — 1, m)
Всего таких пар: (m — 1) + (m — 2) + … + 1 = (m — 1) * m/2 (арифметическая прогрессия)То есть m городов соединены (m – 1) * m/ 2 дорогами.
Если в отделившейся республике m городов, то в стране осталось (400 – m) городов.Чтобы узнать, сколько дорог ведет из республики в страну, надо кол-во городов республики умножить на количество городов страны, т к из каждого города республики ведет по одной дороге в каждый город страны
Значит, из республики в страну ведет m * (400 – m) дорог, а в самой республике (m – 1) * m/ 2.
m(400 – m) = (m – 1) * m/ 2
3m^2 – 801m = 0
3m(m – 267) = 0
Корень m = 0 не подходит, значит m = 267
267 городов
-
Имеем полный граф.
Пусть отделилась республика с n вершинами. Количество ребер в республике n(n-1)/2. Количество оставшихся городов 400-n. Каждый из этих городов соединен с каждым из n городов республики, т.е. (400-n)n дорогами.
По условию:
n(n-1)/2=(400-n)n
Решая уравнение, получим n=267.
Похожие вопросы
Несколько учеников стоят в очереди в школьных буфет. Перед каким-то учеником стоят семеро, после какого-то другого стоят шестеро. Один ученик стоит...
декабрь 24, 2015 г.
Решено
Несколько учеников стоят в очереди в школьных буфет. Перед каким-то учеником стоят пятеро, после какого-то другого стоят четверо. Один ученик стоит...
декабрь 24, 2015 г.