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