Question

Задача на графы.
замок в форме треугольника со стороной 50 метров разбит на 100 треугольных залов со сторонами 5 метров. В каждой стенке между залами есть дверь. Какое наибольшее число залов сможет
бойти турист, не заходя ни в какой зал дважды.

Answer 1

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

Ответ. 91 зал.