Дано: каждый город соединен с каждым дорогой, и король хочет ввести одностороннее движение так, чтобы нельзя было вернуться в город, выехав из него.
Найти: можно ли так сделать.
Решение:
Предположим, что такое одностороннее движение возможно.
Пусть в государстве есть n городов. Если мы выезжаем из какого-либо города, то у нас должна быть возможность по этой системе дорог вернуться обратно в этот город. Таким образом, у каждого города должен быть выход в каждый другой город.
Если мы рассмотрим город A, то он должен иметь выход в каждый другой город. Итак, для города A должно быть n - 1 выходов. Аналогично, для любого другого города тоже должно быть n - 1 выходов.
Таким образом, чтобы удовлетворить условиям задачи, число выходов из каждого города должно быть равно числу городов минус один (n - 1). Но это возможно только если в государстве всего один город.
Ответ:
Невозможно ввести одностороннее движение на дорогах таким образом, чтобы из каждого города нельзя было вернуться.