Задача
В Швамбрании N городов, каждые два соединены дорогой. При этом дороги сходятся лишь в городах (нет перекрёстков, одна дорога поднята эстакадой над другой). Злой волшебник устанавливает на всех дорогах одностороннее движение таким образом, что если из города можно выехать, то в него нельзя вернуться. Доказать, что
а) волшебник может это сделать;
б) найдётся город, из которого можно добраться до всех, и найдётся город, из которого нельзя выехать;
в) существует единственный путь, обходящий все города;
г) волшебник может осуществить своё намерение N! способами.
Решение
а) Занумеруем города в произвольном порядке и для каждой пары городов оставим направление движения от меньшего номера к большему. б) Повесим на город A номер, равный количеству городов, из которых ведёт путь в A. Очевидно, все номера разные, поэтому они пробегают все значения от 0 до N – 1. в) Единственный способ – обходить города от большего к меньшему в соответствии с установленной нумерацией. г) Число способов нумерации равно числу перестановок из N элементов.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь