Question

У країні побудована залізниця таким чином що потяги по кожній лінії що з'єднує два міста їздять лише в одному напрямі у зворотному напрямі рух по цій колії заборонений відомо що не від кожного міста країни можна залізницею дістатися до будь-якого іншого місця навіть шляхом через інші міста.Чи завжди можна відокремити частину міст у країні (може навіть одне місто) таким чином щоб із одного міста іншої частини не можна дістатися в жодне місто відокремленої частини ???​

Answer 1

Відповідь: завжди.
Розв’язання. За умовою в країні є міста «А» та «Б» такі, що від «А» не можливо дістатися до «Б». Відокремимо усі ті міста, до яких не можна дістатися з міста «А». Зрозуміло, що відокремлена частина міст не порожня, бо туди входить принаймні одне місто «Б». Покажемо, що воно задовольняє умові. Якщо з деякого міста «В» невідокремленої частини можна було б дістатися до деякого міста «Г» відокремленої частини, то ми могли б міста «Г» дістатися з міста «А». Дійсно, оскільки «В» не відокремлене, то від нього є шлях до «А», а від «В» є шлях до «Г». Але за побудовою, місто «Г» з відокремленої частини, тобто до нього дістатися з міста «А» не можливо. Одержана суперечність завершує доведення.