олимпиада - Еще о разрезании на клетки

Введем функцию $%P(m,n)$% - минимальное кол-во разрезов прямоугольника размером $%m$%x$%n$% на единичные квадратики.
Очевидно, что если на некотором шаге разрезания у нас есть куча квадратиков $%m_i$%x$%n_i$%, то всего нам понадобится $%\max{P(m_i,n_i)}$% разрезаний, т.е. нас всегда будет интересовать самая "трудная" фигура.
Также понятно, что $%P(k,n)\geq P(m,n)$% при $%k>m$%.
Допустим, на некотором шаге мы разрезаем прямоугольник $%m$%x$%n$% на два: $%k$%x$%n$% и $%(m-k)$%x$%n$%. Тогда $%P(m,n)=\max(P(k,n),P(m-k,n))=P(\max(k,m-k),n)$%. Устремляя к минимуму $%\max(k,m-k)$%, получаем $%k=[\frac{m}{2}]$%.
$%P(m,n)=P(n,m)$%, следовательно, нас не интересует порядок разрезания по вертикали и горизонтали.
Из вышесказанного можно сделать вывод, что самый эффективный способ разрезания прямоугольника - на равные или практически равные части. А этот способ дает ровно $%N(m)+N(n)$% разрезаний, ч.т.д.
Применительно к первому вопросу: $%P(k)=P(k,1)=N(k)+N(1)=N(k)$%.