Задача на графы. замок в форме треугольника со стороной 50 метров разбит на 100 треугольных залов со сторонами 5 метров. В каждой стенке между залами есть дверь. Какое наибольшее число залов сможет бойти турист, не заходя ни ...
Задача на графы.
замок в форме треугольника со стороной 50 метров разбит на 100 треугольных залов со сторонами 5 метров. В каждой стенке между залами есть дверь. Какое наибольшее число залов сможет
бойти турист, не заходя ни в какой зал дважды.
Ответ(ы) на вопрос:
Гость
Раскрасим все залы в шахматном порядке. Заметим, что светлых залов 45, темных 55, и при любом порядке обхода цвет залов чередуется. Значит, длина пути (= количество посещённых залов) не может быть больше, чем 45 + (45 + 1) = 91, при этом надо стартовать из тёмного зала, обойти все светлые залы и закончить обход в темном зале. Пример, как обойти 91 зал, изображен на картинке.
Ответ. 91 зал.
Не нашли ответ?
Похожие вопросы