В королевстве есть города, некоторые из которых соединены между собой дорогами с...

+674 голосов
4.8m просмотров

В королевстве есть города, некоторые из которых соединены между собой дорогами с односторонним движением. К сожалению, дороги построили так, что невозможно объехать все города, даже если посещать один и тот же город несколько раз. В связи с этим было принято решение разделить королевство на два княжества A и B, отнеся каждый город к одному из двух княжеств (в каждом княжестве должен быть хотя бы один город). Докажите, что можно сделать это так, чтобы из княжества A нельзя было попасть в княжество B


Математика (170 баллов) | 4.8m просмотров
Дан 1 ответ
+122 голосов

Ответ:

рассмотрим город А из него ми можем попасть в некоторие города . Из этих некоторие ( ранее изпользиваная група) городов кроме А и их самих некуда нельзя не куда попасть иначе из А вте города можно попасть противоречие=> если все остольное города пойдут в иное княжество(А) а эти в оставшиеся с оставшейся городов не попасть в города из княжества А