Здравствуйте, Pushkin, Вы писали:

P>

P>На бумаге в клеточку написуем прямоугольник AxB. Какова может быть максимальная длина (в клетках) внутренних стенок, при котором область останется связной (из любой клетки можно попасть в любую другую)?

Нуу,.. сегодня что-то совсем просто ...

Число внутренних границ между клетками A(B-1)+B(A-1)=2AB-A-B,
Число границ между клетками, которые должны остаться незакрытими,
найдем из следующих соображений: представим что клетки — вершины
графа ( AB вершин ). Тогда чтобы его связать надо AB-1 связей —
это число границ, которые должны остаться не перегороженными.

Следивательно число перегородок: A(B-1)+B(A-1)-(AB-1)=AB-A-B+1=(A-1)(B-1).

Пример решения:

+-----+
|* * *|
|     |
|*|*|*|
|     |
|*|*|*|
+-----+