Пред­по­ло­жим, что какой-то завод X со­еди­нен ав­то­бус­ны­ми марш­ру­та­ми не более чем с 146 за­во­да­ми. Тогда чет­вер­ка за­во­дов, со­сто­я­щая из X и каких-то трех, с ко­то­ры­ми он не со­еди­нен, не удо­вле­тво­ря­ет усло­вию за­да­чи, по­сколь­ку X не может быть в паре ни с одним из трех остав­ших­ся за­во­дов. По­это­му каж­дый завод со­еди­нен хотя бы с 147 за­во­да­ми. Сле­до­ва­тель­но, всего пар за­во­дов, со­еди­нен­ных ав­то­бус­ны­ми марш­ру­та­ми, не мень­ше, чем

По­ка­жем те­перь, что может быть ровно 11 025 пар за­во­дов. За­ну­ме­ру­ем за­во­ды чис­ла­ми от 1 до 150 и со­еди­ним ав­то­бус­ны­ми марш­ру­та­ми вое за­во­ды, кроме пер­во­го и 150-го, а также за­во­дов, но­ме­ра ко­то­рых от­ли­ча­ют­ся на еди­ни­цу. Про­ве­рим, что эта кон­струк­ция удо­вле­тво­ря­ет усло­вию за­да­чи. По­сколь­ку каж­дый завод со­еди­нен ав­то­бус­ны­ми марш­ру­та­ми с 147 за­во­да­ми, общее ко­ли­че­ство пар со­еди­нен­ных за­во­дов в точ­но­сти и равно

Возь­мем те­перь любую чет­вер­ку за­во­дов. Воз­мож­ны два слу­чая.

1)  Есть завод, не со­еди­нен­ный с двумя из трех осталь­ных за­во­дов. Пусть завод A не со­еди­нен с за­во­да­ми В и C, но cоеди­нен с за­во­дом D. Тогда за­во­ды В и С долж­ны быть cоеди­не­ны между cобой, так как остат­ки от де­ле­ния их но­ме­ров на 150 раз­ли­ча­ют­ся на 2. По­это­му пары (A, D) и (B, C) нам под­хо­дят.

2)  Во за­во­ды со­еди­не­ны с не менее чем двумя из трех осталь­ных за­во­дов. Пусть завод А со­еди­нен с за­во­дам и В и С. По пред­по­ло­же­нию завод D дол­жен быть cоеди­нен с В или С. Если он со­еди­нен с В. то нам по­дой­дут пары (A, C) и (B, D) а если с C, то пары (A, B) и (C, D).

Ответ: 11 025.