Консультация № 195400
28.04.2019, 01:15
0.00 руб.
0 4 1
Здравствуйте, уважаемые эксперты! Помогите решить задачу
В стране 10 городов, некоторые из них соединены дорогой с односторонним
движением, в каждый город ровно одна дорога входит и из каждого города ровно
одна дорога выходит. В каждом городе находится по автомобилисту. Каждый день
каждый автомобилист проезжает одну дорогу. Найдите наименьшее натуральное N
такое, что ровно через N дней все автомобилисты будут в тех городах, из которых
начинали движение, вне зависимости от того, как именно проложены дороги

Обсуждение

давно
Советник
165461
578
28.04.2019, 06:41
общий
это ответ
Здравствуйте, wwesmack!

Такая прокладка дорог возможна, если они образуют кольца. Может быть одно кольцо, включающее все города,
два кольца, в одно из которых входит, например 7 городов, в другое - 3, и так далее.
Чтобы при обходе кольца автомобилист вернулся в исходный пункт, необходимо, чтобы количество дней N
было кратно числу городов в кольце.
При произвольной раскладке дорог, в одно из колец могжет войти любое число городов от 2 до 10.
Поэтому наименьшее N должно быть наименьшим общим кратным этих чисел, N = 5*7*8*9 = 2520.
давно
Мастер-Эксперт
17387
18345
28.04.2019, 07:13
общий
Адресаты:
Сергей Евгеньевич!

Вы сообщили в своём ответе:
Цитата: Лангваген Сергей Евгеньевич
При произвольной раскладке дорог, в одно из колец могжет войти любое число городов от 2 до 10.

По-моему, от трёх до десяти, потому что иначе не выполняется это условие:
Цитата: wwesmack
в каждый город ровно одна дорога входит и из каждого города ровно одна дорога выходит

Извините, пожалуйста, если я ошибаюсь.
Об авторе:
Facta loquuntur.
давно
Советник
165461
578
28.04.2019, 08:11
общий
28.04.2019, 08:11
Адресаты:

Так тоже можно, разве нет?
давно
Мастер-Эксперт
17387
18345
28.04.2019, 08:26
общий
Адресаты:
Не стану спорить; я почему-то рассматривал неориентированные графы. Но тогда я сам себе противоречу.
Об авторе:
Facta loquuntur.
Форма ответа