1 A2 ......... A = Ak = Bk ................ An Bn
за умовою 2).: k? l => B k ? B l , інакше m k і m l мали б 2 загальні зупинки: B і B k = B l
за умовою 1).: будь-яка зупинка m? збігається з однією з B k , тому що будь-яка зупинка m ? може бути з'єднана маршрутом з B, а через B проходять тільки маршрути m 1 , m 2 , ..., m n => зупинка m? з'єднана до B якимось m k. =>
=> дана зупинка є B k .
Т.ч., B 1 , B 2 , ...., B n -всі зупинки < span align = "justify"> m? , m? має n зупинок?.
Ми, в умовах задачі № 4 => число маршрутів 57 = n (n-1) +1, де n - число зупинок на кожному маршруті. З цього випливає: n = 8. p align="justify"> Задача № 6.
Чи можна прокласти в місті 10 автобусних маршрутів і встановити на них зупинки так, що які б 8 маршрутів не були взяті, знайдеться зупинка, яка не належить жодному з цих маршрутів, а будь-які 9 маршрутів проходять через всі зупинки?
Рішення.
Можливо, наприклад, розглянемо 10 прямих на площині у = kx + k 2 , де k = 1,2 , ..., 10 - це маршрути автобусів.
Будь-які дві з цих прямих перетинаються (тому прямі не паралельні, тому що у них різні k) в одній точці.
Нехай точки перетину прямих і тільки вони будуть зупинками. p align="justify"> Ніякі 3 прямі не мають спільну точку перетину, тому що система лінійних рівнянь
у = k1x + k12у-k1x = k12несовместна
у = k2x + k22 <=> у-k2x = k22по теоремі
у = k3x + k32у-k3x = k32Кронекера - Капеллі.
