№1. У деякій країні будь-які два
міста зв’язані між собою,
автобусом, потягом або літаком.
Відомо, що не існує міста, яке забезпечене усіма 3 видами транспорту, а також
одночасно не існує таких 3 міст, будь – які два з яких пов’язані одним тим
самим типом транспорту. Визначте, яка максимальна кількість міст у цій країні,
якщо відомо, що кожен тип транспорту присутній у транспортній системі.
Розв'язання: Припустимо, що може бути 5 міст, то з міста не
виходять З лінії однакового транспорту. Якщо А з'єднаний з Б, В, Г, наприклад,
літаком, то yсі ці три міста не можуть бути з'єднані літаком. Якщо Б i В -
потягом, то В i Г не можуть бути з'єднані автобусом (суперечність з містом В),
а тому yci три міста з'єднані потягом - знову суперечність. Тому з кожного
міста виходить по 2 гілки двох типів транспорту. Тому хоч один тип транспорту
обслуговує принаймні 3 міста. Якщо він обслуговує рівно 2 міста, то з кожного міста
виходить рівно 1 лінія, суперечність. Якщо він обслуговує 3 міста, то вони
повинні бути з’єднані одним видом - суперечність. Для чотирьох приклад можна побудувати. Зробіть це самостійно.
Немає коментарів:
Дописати коментар