Задача
В поселке 20 жительниц. 1 марта одна из них узнала интересную новость и сообщила её всем своим подругам. 2 марта те сообщили новость всем своим подругам, и так далее. Может ли так случиться, что:
а) 15 марта ещё не все жительницы будут знать новость, а 18 марта уже все?
б) 25 марта ещё не все жительницы будут знать новость, а 28 марта уже все?
Решение
а) Пример. Пусть 1-я дружит только со 2-й, 2-я – еще и с 3-й, 3-я – с 4-й, ..., 16-я – с 17-й, а 17-я – еще и с остальными тремя. б) Кратчайший путь соединяющий две данные вершины графа, не может содержать какую-либо вершину дважды. Поэтому все женщины, которые в принципе могут узнать новость, будут знать её не позже 20 марта.
Ответ
а) Может; б) не может.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь