Олимпиадная задача по комбинаторной геометрии: план дворца шаха, 6×6, 5–7 классы

  Рассмотрим произвольный маршрут из левого нижнего угла дворца в правый верхний. Так как надо "подняться" на 5 горизонталей и "сместиться вправо" на 5 вертикалей, то придётся пройти, как минимум, через 10 дверей, посетив при этом не меньше, чем 11 комнат (включая начальную и конечную).

   11 комнат размером 1×1 не могли превратиться в 5 комнат размером 2×1. Следовательно, тот же маршрут в перестроенном дворце должен проходить, как минимум, через 6 комнат, а значит, не менее, чем через 5 дверей.

  Такая перестройка дворца действительно возможна (см. рисунок).

  В этом случае действительно можно попасть из каждой комнаты в любую другую, пройдя не более чем через 5 дверей. Обозначим центральные комнаты цифрой 0, связанные с ними дверью – цифрой 1, а связанные дверью с комнатами "типа" 1 – цифрой 2. Поскольку оказались обозначены все комнаты, то из каждой комнаты можно попасть в одну из центральных, пройдя не более двух дверей. Значит, из каждой комнаты можно попасть в любую другую, построив маршрут через центральные комнаты и пройдя тем самым не более, чем через 5 дверей (пятая дверь потребуется в случае, если придётся перейти из одной центральной комнаты в другую).

N = 5.