Зарядка для ума: как пройти через закрытые двери

Сможете ли вы решить простую задачку?

В квадратном замке 25 одинаковых квадратных комнат. Между любыми соседними комнатами есть дверь. Некоторые из этих дверей сторож запирает на ночь. Какое максимальное число дверей он может запереть, чтобы ночью можно было пройти из любой комнаты замка в любую другую, пройдя не более чем через 7 других комнат?

Зарядку для ума опубликовала русская служба BBC.

Решение. Если центры комнат изобразить на отдельном рисунке точками, а открытые двери между соседними комнатами обозначить отрезками, соединяющими соответствующие точки, то получится граф.

В этом графе 25 точек (по числу комнат замка), и для того, чтобы из любой можно было пройти в любую другую (такое условие называется связностью графа) должно быть не менее 24 соединяющих их отрезков, то есть не менее 24 открытых дверей.

Вот картинка замка, на которой запертые двери показаны сплошными линиями, а незапертые - пунктирными.

В исходном замке дверей всего 40 - двадцать на "вертикальных" стенках и столько же на "горизонтальных".

Следовательно, сторож может закрыть не более 40-24=16. Осталось привести пример, когда такого количества запертых дверей хватит для того, чтобы путь между любыми двумя комнатами проходил не более чем через 7 других комнат.