1 варіант -
всі решки
В
= 0
- очевидно
- коефіцієнт при
? p> - коефіцієнт при xn:
В
= 1
Завдання № 4. p align="justify"> Автобусна мережа міста влаштована так. що:
) з будь-якої зупинки можна потрапити на будь-яку іншу бід пересадки;
) для будь-якої пари маршрутів знайдеться і притому єдина зупинка, на якій можна пересісти з одного з цих маршрутів на інший;
) на кожному маршруті рівно п зупинок. Скільки автобусних маршрутів в місті?
Рішення. p align="justify"> Варіант I.
У місті один маршрут, що з'єднує всі n зупинок. Виконані вимоги умови задачі: 1) і 3) - очевидно, 2) - за принципом В«все чорти зеленіВ». p align="justify"> Варіант II.
У місті більше 1 маршруту. Тоді з умов 1) і 2) завдання випливає, що для будь-якої зупинки існує маршрут, який не містить її. p align="justify"> Доказ: А - довільна зупинка.
] A Є m (А-зупинка на маршруті m)
m?? m (більше 1 маршруту)
В
А m? - Все доведено, тобто знайшовся маршрут, який не містить А.
A Є m?
A Є m?
B Є m?: У? A не буває маршрутів з однієї зупинки. p> C Є m: С? A
В
За умовою 1): m??, що з'єднує В і С. За умовою 2): А m??, інакше m і m?? мали б 2 загальні зупинки А і С.
А m?? знайшовся маршрут, який не містить А?.
З умов завдання випливає, що через кожну зупинку проходить рівно n маршрутів. p> Доказ:] B - довільна зупинка. m: B m (доведено вище)
B
m
A1 A2 ........ An
За умовою 3) m має n зупинок: A 1 , A 2 , ...., A n
За умовою 1) mk - маршрут, що з'єднує B і Ak, де k 1,2, ..., n.
За умовою 2) a) такий маршрут mk - єдиний, тому що, інакше mk і m? k мають 2 загальні зупинки В і Ak.
б). при k? lm k ? m l, тому інакше m k = m l = m ? і m мають 2 загальні зупинки А k і A < i align = "justify"> l
В
А k ...
