ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 97804
Темы:    [ Отношение порядка ]
[ Обход графов ]
[ Упорядочивание по возрастанию (убыванию) ]
[ Перестановки и подстановки (прочее) ]
Сложность: 4
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Коганов И.

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


Решение

  а) Занумеруем города в произвольном порядке и для каждой пары городов оставим направление движения от меньшего номера к большему.

  б) Повесим на город A номер, равный количеству городов, из которых ведёт путь в A. Очевидно, все номера разные, поэтому они пробегают все значения от 0 до  N – 1.

  в) Единственный способ – обходить города от большего к меньшему в соответствии с установленной нумерацией.

  г) Число способов нумерации равно числу перестановок из N элементов.

Замечания

В 7-8 классах давались пп. а, б и в (3 + 1 + 5 баллов), а в 9-10 классах – пп. а, б и г (2 + 1 + 4 балла).

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1983
выпуск
Номер 8
Задача
Номер М819
олимпиада
Название Турнир городов
Турнир
Дата 1982/1983
Номер 4
вариант
Вариант 9-10 класс
Задача
Номер 3
олимпиада
Название Турнир городов
Турнир
Дата 1982/1983
Номер 4
вариант
Вариант второй тур, 7-8 класс
Задача
Номер 3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .