Задача 32859

Темы:    [ Ориентированные графы ] [ Обход графов ]

Сложность: 2+ Классы: 7

Условие

В поселке 20 жительниц. 1 марта одна из них узнала интересную новость и сообщила её всем своим подругам. 2 марта те сообщили новость всем своим подругам, и так далее. Может ли так случиться, что:
  а) 15 марта ещё не все жительницы будут знать новость, а 18 марта уже все?
  б) 25 марта ещё не все жительницы будут знать новость, а 28 марта уже все?

Решение

а) Пример. Пусть 1-я дружит только со 2-й, 2-я – еще и с 3-й, 3-я – с 4-й, ..., 16-я – с 17-й, а 17-я – еще и с остальными тремя.

б) Кратчайший путь соединяющий две данные вершины графа, не может содержать какую-либо вершину дважды. Поэтому все женщины, которые в принципе могут узнать новость, будут знать её не позже 20 марта.

Ответ

а) Может;  б) не может.

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

Кружок
Название	ВМШ 57 школы
класс
Класс	7
год
Год	1999/00
Место проведения	57 школа
занятие
Номер	4
Название	Графы
Тема	Неизвестная тема
задача
Номер	02