В королевстве 16 городов. Король хочет построить такую систему дорог, чтобы из каждого города можно было попасть в каждый, минуя не более одного промежуточного города, и чтобы из каждого города выходило не более пяти дорог.
  а) Докажите, что это возможно.
  б) Докажите, что если в формулировке заменить число 5 на число 4, то желание короля станет неосуществимым.

   Решение

Темы:    [ Ориентированные графы ] [ Четность и нечетность ]

Сложность: 3+ Классы: 8,9,10

Прислать комментарий

Условие

В секретной службе работают n агентов – 001, 002, ..., 007, ..., n. Первый агент следит за тем, кто следит за вторым, второй – за тем, кто следит за третьим, и т.д., n-й – за тем, кто следит за первым. Докажите, что n – нечётное число.

Подсказка

Предполагая, что первый агент следит за k-м агентом, восстановите всю схему слежки.

Решение

Обозначим агентов точками и проведём стрелку от агента A к агенту B в том случае, когда A следит за B. Поскольку каждый агент следит ровно за одним другим, мы получим некоторый цикл (или несколько циклов) из стрелок. Согласно условию, если начать движение по стрелкам, начиная с первого агента и проходя за один раз по двум стрелкам, мы встретим подряд всех агентов с номерами 2, 3, ..., n, и в конце снова придём к первому агенту (это, в частности, означает, что цикл только один). Но в случае чётного числа агентов таким образом мы обойдём только половину цикла.

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