В стране есть несколько городов, соединённых дорогами. Город называется захолустным, если из него выходит только одна дорога, и узловым, если из него выходит не менее трёх дорог. Известно, что в этой стране 101101101 захолустный город. При каком наименьшем количестве узловых городов можно заведомо утверждать, что в стране найдутся несколько городов, связанных циклическим маршрутом?
В стране есть несколько городов, соединённых дорогами. Город называется захолустным, если из него выходит только одна дорога, и узловым, если из него выходит не менее трёх дорог. Известно, что в этой стране 101101101 захолустный город. При каком наименьшем количестве узловых городов можно заведомо утверждать, что в стране найдутся несколько городов, связанных циклическим маршрутом?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для того чтобы в стране был циклический маршрут, необходимо чтобы по крайней мере два города были узловыми, так как циклический маршрут состоит как минимум из двух узловых городов.
Предположим, что в стране все остальные города кроме узловых являются захолустными. Тогда у нас есть 101101101 захолустный город, значит общее количество городов в стране равно 101101101 + количество узловых городов.
Так как общее количество городов должно делиться на 2 (для того чтобы образовать циклический маршрут), то и количество узловых городов должно делиться на 2. Поэтому для уверенного нахождения циклического маршрута необходимо минимум 2 узловых города.
Ответ: 2 узловых города.