m
в). Будь-який маршрут, що проходить через B, повинен мати загальну зупинку А k з маршрутом m, тобто збігається з одним із m k .
Таким чином, m 1 , m 2 , ....., m n - всі різні маршрути через B?.
Вважаємо кількість маршрутів. br/>
(n-1)
....
m
...............................
.............
(n-1) (n-1)
- небудь маршрут.
Вище доведено, що через кожну А до проходить n маршрутів, тобто (N-1) без урахування маршруту m.
З умови 2) будь-який маршрут, відмінний від m, проходить рівно через одну А до, тобто всі безліч маршрутів складається з m і n непересічних класів по (n-1) маршрутом.
Загальна кількість маршрутів n (n-1) +1
Завдання № 5.
У місті налічується 57 автобусних маршрутів. Відомо, що:
) з будь-якої зупинки можна без пересадки потрапити на будь-яку іншу;
) для будь-якої пари маршрутів знайдеться, і притому тільки одна, зупинка, на якій можна пересісти з одного з цих маршрутів па інший:
) на кожному маршруті не менше трьох зупинок. Скільки зупинок має кожен з 57 маршрутів? p align="justify"> Рішення.
Нехай m - один з маршрутів - має n зупинок. Тоді будь-який інший маршрут m ? теж має n зупинок.
Доказ: за умовою 2). m і m ? персекаются в єдиній зупинці A.
З Є m: С? А не буває маршрутів
з однієї зупинки
D Є m?: D? А
За умовою 1). m?? - маршрут, що з'єднує С і D, а за умовою 3). m?? має хоча б одну зупинку B відмінну від С і D. p> B m, B m?, т.к. інакше m?? мав би з m і m? більше однієї загальної зупинки.
m?
D
m??
B
Сam
Застосуємо міркування рішення задачі № 4 (другого докази). Отже m 1 , ..., m n - всі різні маршрути через B.
Тоді за умовою 2).:
Bk = mk? m?
B m?
В В
m1 Bn
m? m2mn
B1
B2...
