We say that a ladder of size $n$ is the figure formed by all squares below one of the diagonals of an $n\times n$ square partitioned in $n^2$ unit squares. Clearly any partition considered in the problem is the union of the partition of two ladders of size $2^m$, plus the $2^m$ unit squares in the diagonal. Claim: A ladder of size $n$ can be partitioned in rectangles consisting of unit squares whose perimeter is at least $p_n=2n\log_2n$. Proof: The result is clearly true for $n=2$, since the ladder consists of exactly one unit square with perimeter $4=2\cdot2\cdot\log_22$. For larger ladders, wlog the ladder has a leftmost column of $n-1$ squares and a bottom row of $n-1$ squares. Number the rows and columns such that the bottom row is $1$ and the top row (consisting of exactly one square) is $n-1$, and the leftmost column is $1$ and the rightmost column is $n-1$. The squares forming the border of the ladder are $(i,j)$ ($i$ is the row, $j$ is the column) such that either $i=1$, or $j=1$, or $i+j=n$. Assume the perimeter of the partition is minimum, and consider the rectangle $R$ that contains the square $(1,1)$; its top right square is $(i,j)$, and assume that $i+j<n$. Consider the rectangles (possibly only one) to the right of $R$ having a (possibly partially) common side with $R$. If these rectangles span exactly the right side of $R$, we may move the side of $R$ one square to the right, mantaining the perimeter if there is exactly one rectangle having a partially common side with the right side of $R$, and decreasing it if there are more than one of them; the second case is then absurd since the partition considered has minimum perimeter, while in the first case, we take $R$ and the rectangle to its right, and since they have a common side, we remove this common side transforming the two rectangles into one, absurd since the perimeter would decrease. We conclude that there is at least one rectangle having a side that overlaps partially with the right side of $R$, but continues upwards. Then, the rectangles on top of $R$ have bottom sides overlaping with the top side of $R$, hence the perimeter may be reduced by moving upwards the top side of $R$ (if there are more than one rectangles on top of $R$), or joining $R$ and the rectangle on top of it by removing the top side of $R$ (if there is exactly one rectangle on top of $R$). Contradiction, hence $i+j=n$. The minimum perimeter is then equal, for some $i,j$, to the perimeter of a ladder of size $n-i$, plus the perimeter of a ladder of size $n-j$, plus the perimeter of a rectangle of size $i\times j$, ie, since the claim is true for $n=2$, using $p_k=2k\log_2k$ for all $k<n$ for the inductive step, we find that \[p_n\geq2i+2j+p_{n-i}+p_{n-j}=2i+2j+2(n-i)\log_2(n-i)+2(n-j)\log_2(n-j)\geq 2n+4\frac{n}{2}\log_2\frac{n}{2}=2n+2n\log_2n-2n=2n\log2n,\] where we have used Jensen's inequality since $f(x)=x\log_2x=\frac{x\ln x}{\ln2}$ has second derivative positive $\frac{1}{x\ln2}$ for all $x>0$, and that $\frac{2n-i-j}{2}=\frac{n}{2}$ because $i+j=n$ for minimum partition perimeters. Equality occurs when $i=j$. When $n=2^m$ is a power of $2$, $p_{2^m}=2m2^m$, hence the total perimeter for the partition of the $2^m\times2^m$ square is at least $2p_{2^m}+4\cdot2^m=(m+1)2^{m+2}$. This minimum can be achieved as follows: partition first the $2^m\times2^m$ square in four $2^{m-1}\times2^{m-1}$ squares, two of them contain as diagonals half the diagonal that is formed by individual unit squares of the partition, two of them do not. Take the two squares that do not contain unit squares as rectangles of the partition, and set them as rectangles of the partition, and partition recursively in the same way, the two $2^{m-1}\times2^{m-1}$ squares that have in their diagonals unit squares that are rectangles of the partition.

Let $C_{ij}$ denote the cell on the $i$-th row and the $j$-th row. Assume $C_{ii}$ are the unit cells which form separate rectangles. Now we find the lower bound of the sum of perimeters in partition of $\bigcup_{1\le j<i\le 2^m}C_{ij}$ (the lower part of the figure). Assume that there are $n$ rectangles altogether. Also assume that $r_i$ rectangles contain some cell of the $i$-th row, and $c_j$ rectangles contain some cell of the $j$-th row. In the $i$-th row, each of the $r_i$ rectangles traces 2 unit vertical segments. So the total length of the vertical sides is $2\sum r_i$, and hence the total perimeter is $p=2\sum(r_i+c_i)$. Now we classify subsets of the rectangles as follows. Subset $S$ is of type $i$ if $S$ contains all rectangles which cover some cell of the $i$-th row but do not cover any cell of the $i$-th column. The number of subsets of type $i$ is $2^{n-r_i-c_i}$. No subset $S$ can belong to 2 different types $i>j$ (otherwise $C_{ij}$ belongs to $S$ but doesn't belong to $S$). Hence we have \[2^n\ge\sum2^{n-r_i-c_i}\implies 1\ge\sum\frac1{2^{r_i+c_i}}\] Since the function $\frac1{2^x}$ is convex, then \[\sum\frac1{2^{r_i+c_i}}\ge2^m\cdot\frac1{2^{\frac{\sum(r_i+c_i)}{2^m}}}=\frac{2^m}{2^{\frac{p}{2^{m+1}}}}\] Therefore $1\ge\frac{2^m}{2^{\frac{p}{2^{m+1}}}}$, and we get $p\ge m\cdot2^{m+1}$. Hence the total perimeter in the whole figure is at least $2\cdot(m\cdot2^{m+1})+4\cdot2^m=2^{m+2}(m+1)$. The construction is the same as daniel73's.

Just wondering, but how did you get the intuition to classify the subsets in the manner you did? Is it some standard technique or did something in the problem point you in that direction?

A Generalization: If $2^m$ in the problem's statement is replaced with $n$, where $2^m\le n< 2^{m+1}$, then the smallest possible sum of rectangle perimeters in such a partition will be $4(m+3)n-2^{m+3}$.

Well, can't you just induct? Let $ \mathcal {C} $ be the configuration which achieves the minimal perimeter sum. Divide the square into four equal squares of dimension, $ 2 ^{ m -1} \times 2 ^ { m -1 } $ sharing the center of the chessboard as the corner. Let one such square be $ ABCD $ , ( $ A $ is the center of the chessboard) which doesn't contain the squares along the "one diagonal". Transform $ \mathcal C $ into $ \mathcal C' $ as follows. If a rectangle in $ \mathcal C $ shares only it's boundary with $ ABCD $, or doesn't intersect it at all and doesn't lie in it's interior, leave it as it is. If a rectangle in $ \mathcal C $ is inside $ ABCD $, delete it, except for the sides it shares with the boundary of $ ABCD $. If a rectangle in $ \mathcal C $, intersects the boundary of $ ABCD $, say the side $ AB $, then reduce the rectangle to the one formed by the sides orthogonal to $ AB $ (of the original rectangle), the boudary of $ AB $ which intersects this rectangle, and the side parallel to $ AB $ which was already outside. It can be easily seen that all these procedures strictly decrease the total perimeter. ( Sorry if it's a bit murky, but draw the large square $ ABCD $ and it's obvious ). So, $ \mathcal C' $ contains the large square $ ABCD $ and so the minimal perimeter is achieved when each of the two smaller $ 2 ^ { m -1 } \times 2 ^ { m -1 } $ squares achieve their minimal sum. A simple computation reveals this minimal perimeter sum in $ ( m + 1 ) \cdot 2 ^ { m + 1 } $.

The question is, how do you know that the minimum perimeter is in fact achieved when one of the "big" squares $ABCD$ is in fact one of the rectangles in the partition? Could there be a partition that does not include $ABCD$ and smaller perimeter? Basically, the induction process gives you a sequence of partitions which achieve, for each $m$, a value of the perimeter that turns out to be minimum, but the induction process itself does not guarantee that it is in fact the minimum. Your induction process solves the "easy" part (finding the partition for which the minimum perimeter is obtained), but not the "hard" part (proving that in fact that value of the perimeter is minimum).

I tried to compute the minimum sum of the perimeters with this inequality, but I'm not good at inequalities, so I need some help, and I'm not even quite sure if this argument works. We compute the minimum sum of the perimeters of the rectangles in one of the ladders in a $2^m \times 2^m$ square. Altogether, we need to tile $\frac{(2^m-1)(2^m)}{2}=(2^{m-1})(2^m-1)$ unit squares. This is equal to the sum of their areas. Observe that there must be a minimum of $2^m-1$ rectangles. To see why, shade the top-most square in each column. each rectangle can only contain at most 1 shaded square. Now, label our rectangles $r_1, r_2, r_3, \ldots r_{2^m-1}$. For all $1\le i\le 2^m-1$, let the length of $r_i$ be $a_i$ and let the width of $r_i$ be $b_i$. Then, we have $$\sum\limits_{k=1}^{2^m-1}a_kb_k=(2^{m-1})(2^m-1).$$ Let $a_i+b_i=c_i$. We want to compute the minimum possible value of $$2(a_1+b_1+a_2+b_2+a_3+b_3+\ldots +a_{2^m-1}+b_{2^m-1})=2(c_1+c_2+c_3+\ldots +c_{2^m-1}).$$ By AM-GM, we have $$a_ib_i\le \frac{(c_i)^2}{4}.$$ Summing over all rectangles, we have $$\sum\limits_{k=1}^{2^m-1}a_kb_k = (2^{m-1})(2^m-1) \le \frac{c_1^2+c_2^2+c_3^2+\ldots +c_{2^m-1}^2}{4}$$ Which reduces to $$c_1^2+c_2^2+c_3^2+\ldots +c_{2^m-1}^2 \ge (2^{m+1})(2^m-1).$$ It looks like we're really close, I just don't know how to inequality, so I need some help. Thanks.

Let $f(n)$ be the minimum sum of perimeters needed to tile the part of an $n\times n$ grid below the diagonal. We claim by strong induction that \[ f(2^m+r)=(2m)\cdot 2^m+(2m+4)\cdot r \]for $m\ge 1$ and $0\le r\le 2^m$ (since the values of $f(2^m+2^m)$ and $f(2^{m+1})$ coincide). Note that $f(1)=0$ and $f(2)=4$, and additionally note $f$ is convex. For all tilings of the bottom half of an $n\times n$ grid with minimum perimeter, consider one with $i+j$ maximal, where the rectangle containing the bottom left corner (which we'll mark as $(0,0)$) has top right corner at $(i,j)$. We claim $i+j=n$, or equivalently that the top right corner lies along the diagonal. If this is not the case, either the segment from $(i,j)$ to $(i+1,j)$ or the segment from $(i,j)$ to $(i,j+1)$ is already drawn, as otherwise the cells with bottom left corners at $(i-1,j)$, $(i,j)$, and $(i,j-1)$ are all in the same rectangle, which is impossible. WLOG assume the segment from $(i,j)$ to $(i+1,j)$ is already drawn. Now erase the segment from $(i,0)$ to $(i,j)$, draw in the segment from $(i+1,0)$ to $(i+1,j)$, and erase all segments from $(i,a)$ to $(i+1,a)$ for $0<a<j$. It's not too hard to verify that this creates a new valid tiling that does not increase the sum of perimeters. Since $i+j$ has been increased, this contradicts $i+j<n$, so we can indeed take $(i,j)$ with $i+j=n$. Now this breaks up the bottom half of the grid into three sections: the $i \times j$ rectangle, the subsection above it, and the subsection to its right. Then \[ f(n) =2n + \min_{\substack{i+j=n\\i,j>0}} f(i)+f(j) \]By the inductive hypothesis, $f$ is convex on $1,2,\cdots n-1$. So the minimum occurs when $|i-j|$ is minimal. Thus if $r$ is even, \begin{align*} f(2^m+r)&=2(2^m+r)+2f\left(2^{m-1}+\frac{r}{2}\right)\\ &= 2(2^m+r) + 2\left(2(m-1)\cdot 2^{m-1}+(2m+2)\cdot \frac{r}{2}\right)\\ &=(2m)\cdot 2^{m}+(2m+4)\cdot r \end{align*}and if $r=2k+1$ is odd, \begin{align*} f(2^m+r)&=2(2^m+r)+f(2^{m-1}+k)+f(2^{m-1}+k+1)\\ &=2(2^m+r)+2(m-1)\cdot 2^{m-1}+(2m+2)\cdot k + 2(m-1)\cdot 2^{m-1}+(2m+2)\cdot (k+1)\\ &=(2m)\cdot 2^{m} + (2m+4)\cdot r \end{align*}If $n=2^{m}$, the answer to the initial problem is \[ 4n+2f(n)=(4m+4)\cdot 2^m. \]

I am having difficulty figuring out how to start this problem to arrive at the presented solutions? Can someone explain how they would start such a problem to arrive at solution? thanks

Solved with eisirrational, goodbear, Th3Numb3rThr33. The answer is $2^{m+2}(m+1)$. Say an $n$-staircase consists of the points $(i,j)$ with $i,j>0$ and $i+j\le n$. It suffices to show a $2^m$-staircase has minimum perimeter sum $2^{m+1}m$; then, the minimum perimeter sum of the grid is $2\cdot2^{m+1}m+2^m\cdot4=2^{m+2}(m+1)$. First the construction: for a $2^{m+1}$-staircase, draw a $2^m\times2^m$ rectangel in the bottom-left and draw two $2^m$-staircases in the top and right. [asy][asy] size(5cm); defaultpen(fontsize(10pt)); filldraw( (0,0)--(4,0)--(4,4)--(0,4)--cycle,lightblue+opacity(0.5),lightblue+linewidth(1)); filldraw( (4,0)--(6,0)--(6,2)--(4,2)--cycle,lightred+opacity(0.5),lightred+linewidth(1)); filldraw( (0,4)--(0,6)--(2,6)--(2,4)--cycle,lightred+opacity(0.5),lightred+linewidth(1)); filldraw( (6,0)--(7,0)--(7,1)--(6,1)--cycle,lightgreen+opacity(0.5),heavygreen+linewidth(1)); filldraw( (4,2)--(5,2)--(5,3)--(4,3)--cycle,lightgreen+opacity(0.5),heavygreen+linewidth(1)); filldraw( (0,6)--(0,7)--(1,7)--(1,6)--cycle,lightgreen+opacity(0.5),heavygreen+linewidth(1)); filldraw( (2,4)--(2,5)--(3,5)--(3,4)--cycle,lightgreen+opacity(0.5),heavygreen+linewidth(1)); draw( (7,0)--(0,0)--(0,7)); for (real i=1; i<=8+1e-9; i+=1) { draw( (i,0)--(i,8-i)); draw( (0,i)--(8-i,i)); } [/asy][/asy] It can be seen that the perimeter sum for a $2^m$-staircase is \[2^{m+1}+2\cdot2^m+2^2\cdot2^{m-1}+\cdots+2^{m-1}\cdot4=2^{m+1}m,\]as required. Now we prove the lower bound: let $g(n)$ be the minimum perimeter sum for an $n$-staircase. I claim $g(n)\ge2n\log_2n$, which will suffice. [asy][asy] size(5cm); defaultpen(fontsize(10pt)); filldraw( (0,0)--(2,0)--(2,6)--(0,6)--cycle,lightblue+opacity(0.5),lightblue+linewidth(1)); filldraw( (0,0)--(1,0)--(1,5)--(0,5)--cycle,lightgreen+opacity(0.5),heavygreen+linewidth(1)); draw( (7,0)--(0,0)--(0,7)); for (real i=1; i<=8+1e-9; i+=1) { draw( (i,0)--(i,8-i)); draw( (0,i)--(8-i,i)); } [/asy][/asy] Claim: In some optimal configuration, the rectangle containing the bottom-left cell also contains a cell along the longest diagonal. Proof. As shown above, let the green rectangle be the rectangle containing the bottom-left cell in an optimal configuration, and let the blue rectangle contain a point cell the longest diagonal and also contain the green rectangle. for each rectangle that is entirely contained in the blue rectangle, delete it; for each rectangle that is partially covered by the blue rectangle, delete its intersection with the blue rectangle; and for each rectangle that is not covered in the blue rectangle, keep it. It is not hard to check this does not increase the perimeter sum; one such way is as follows: if the $i$th row intersects $r_i$ rectangles and the $i$th column intersects $c_i$ rectangles, then the perimeter sum is \[2\sum_{i=1}^{n-1}r_i+2\sum_{i=1}^{n-1}c_i.\]It can be seen that no $r_i$ or $c_i$ increases. $\blacksquare$ Hence we may assume the rectangle containing the bottom-left cell contains a cell along the longest diagonal. Let this rectangle have dimensions $a\times b$, so we split the $n$-staircase into an $a$-staircase, a $b$-staircase, and an $a\times b$ rectangle. Since $2n\log_2n$ is convex, \[g(n)\ge2n+\min_{a+b=n}(g(a)+g(b))\ge2n+2g(n/2)\ge2n+2n(\log_2n-1)=2n\log_2n\]by Jensen's inequality. This completes the proof.

Imagine misreading ... Here is the solution for the (harder) question where each diagonal square is in a $1\times n$ for some $n$. The perimeter sum is equal to $2*(\text{total sum of internal boundaries})+(\text{perimeter of square})$, so this question is equivalent to minimizing the former factor. Consider a partition that achieves this minimum, and consider only the squares which lie below the main diagonal. Define extending a rectangle to be increasing its height or width by 1, and call a rectangle maximal if it can't be extended without hitting the main diagonal squares. Finally, define the corner rectangle to be the rectangle which contains the bottom right corner. For convenience, no rectangles with a dimension equal to 1 are maximal. Claim 1: The corner rectangle either has dimension 1 in all minimal cases, or there exists a minimal case where the corner rectangle is maximal. Proof: Consider extending the corner rectangle in a certain direction, WLOG vertically. Note that this extension destroys at least $w$ internal boundaries, and adds at most $w$ internal boundaries, unless there exists a rectangle whose bottom side overlaps the corner rectangle's top edge, but isn't entirely inside of it. But, in the latter case, there can't exist such a rectangle for the right boundary, so we extend rightwards instead. Thus, we can always extend our rectangle while preserving minimality. Once we can no longer extend, then, we must either have a maximal rectangle or a rectangle of dimension 1. Furthermore, we can say that if it has dimension $1$, then the corner rectangle extends all the way to the diagonal. Claim 2: If the corner rectangle has dimension 1 in a minimal arrangement of an $n\times n$, then the number of internal boundaries below the diagonal is at least $\binom{n}{2}$. Proof: WLOG that the corner rectangle is vertical. Then, it contributes at least an internal boundary length of $n-1$. Furthermore, it forms a new corner to the right of it, so we can repeat the proof in Claim 1 to see that the corner rectangle of the new corner is either maximal or a "maximal dimension 1." However, if has $\text{height}>1$, then we can see easily that the configuration is not maximal, as shown below: [asy][asy] pair A,B,C,D,E,F,G,H; A=(0,0); B=(0,0.5); C=(0.1,0.5);D=(0.1,0); E=(0.1,0.2); F=(0.5,0.2);G=(0.5,0); H=(0,0.2); draw(A--B--C--D--A); draw(E--F--G--D); draw((0.6,0.25)--(0.75,0.25)--(0.7,0.28)); draw((0.75,0.25)--(0.7,0.22)); draw((A+(0.8,0))--(G+(0.8,0))--(F+(0.8,0))--(H+(0.8,0))--(A+(0.8,0))); draw((H+(0.8,0))--(B+(0.8,0))--(C+(0.8,0))--(E+(0.8,0))); [/asy][/asy] since by replacing the corner rectangle with the right rectangle, we create a smaller internal boundary sum, contradicting minimality. Thus, the right rectangle also has dimension 1, which contributes at least $n-2$ to the boundary sum. Inducting up, the next rectangle must also have dimension 1 and contributes at least $n-3$, etc. In total then, we get a boundary sum of at least $\binom{n}{2}$, as desired. Claim 2 only considers when the corner rectangle has dimension 1. If it is instead a maximal rectangle, then it contributes $n$ to the boundary sum, and splits the area below the diagonal into 2 regions, in which we can induct. So, if we define a sequence $a_i$ to our lower bound for an $i\times i$, computed with Claim $2$, we have that $a_n=\min\left(\binom{n}{2},n+\min_{2\le i\le{n-2}}a_i+a_{n-i}\right)$. Listing out the first few terms, we have $(a_2,a_3,a_4,a_5,\ldots )=(1,3,6,9,\ldots)$. It is not hard to see that $a_i<\binom{i}{2}$ for $i>4$, and that $a_i-a_{i-1}\le a_{i+1}-a_i$. Given these two properties, we have that we should always take the second argument of the min, and the nested min is minimized at $i=\left\lfloor\frac{n}{2}\right\rfloor$. Thus, if $b_m$ denotes our lower bound for a $2^m\times 2^m$, we have that $b_1=1,b_2=6$, $b_n=2^n+2b_{n-1}$. It is not hard to see that the closed form is $b_m=(m-1)2^m+2^{m-1}$. So, the minimum total internal boundary is $2*b_m$ since we repeat our argument for the upper right corner, and our final minimum is $2^m*4+2^{m+1}+(m-1)2^{m+2}=m2^{m+2}+2^{m+1}$ We can inductively create a construction for this lower bound as follows: Our construction for the $2\times 2$ is two $1\times 2$s, and we construct the $m$ case with two $m-1$ cases in the top left and bottom right, and two $2^{m-1}\times2^{m-1}$ rectangles in the bottom left and top right.

Solution from Twitch Solves ISL: The answer is that $2(2^{m+1} \cdot m) + 4 \cdot 2^m$. The problem is equivalent to showing that a staircase with $2^m-1$ cells on the bottom row requires at least $2^{m+1} \cdot m$ cells to cover. We first prove the lower bound. The general claim is the following: Claim: A staircase with $n-1$ cells on the bottom row requires at least $f(n) = 2n \log_2 n$ total perimeter to tile with rectangles. Proof. The proof is by induction on $n$. Orient the staircase so that the stairs move from the northwest corner to southwest corner. We consider the rectangle $R$ which covers the southwestern cell. Note that if $R$ touches one of the highest cells in any column, then we can proceed by induction in the following way: we have divided the staircase into two smaller staircases with $a-1$ and $b-1$ width, for some $a$ and $b$, with $a+b=n$. So the total perimeter used must then be at least \[ f(a) + f(b) + 2(a+b) = f(a)+f(b) + 2n. \]By Jensen inequality on the convex function $f$, (since $f''(x)$ is a multiple of $1/x$) it follows that we get a lower bound of $2f(n/2) + 2n = f(2n)$ as desired. [asy][asy] size(12cm); filldraw(shift(-10,0)*box( (0.1,0.1), (2.9,4.9) ), palered, red); label("$R$", (-8.5, 0), dir(-90), red); label("$R$", (1, 0), dir(-90), red); draw(box( (0.1,0.1), (2.9,2.9) ), red+dashed); filldraw(box( (0.1,0.1), (1.9,2.9) ), palered, red); filldraw(box( (1.1,3.1), (2.9,4.9) ), palegreen, green); for (int i=0; i<7; ++i) { for (int j=0; j<7-i; ++j) { draw(shift(i-10,j)*unitsquare); draw(shift(i,j)*unitsquare); } } label("$s$", (1.5, 2.5), red); label("$t$", (2.5, 3.5), blue); [/asy][/asy] If $R$ does not have this property, then we will adjust the tiling until it does. Consider the upper right corner $s$ of $R$. The cell $t = s + (1,1)$ as shown is covered by some rectangle and we may assume WLOG that the rectangle covering $t$ does not extend south of $t$, say (as opposed to west; it could be that $t$ does not extend either west or south, or actually the cell $t$ could also be outside the staircase entirely, but the proof remains the same). In that case, we can extend the rectangle $R$ by one cell to the right, as shown, with any rectangles that were once covering those cells being diminished by width $1$ to make room. This is possible because no old rectangles could have crossed the northern border of the new $R$; moreover, the total perimeter cannot increase with such a change. By repeating this adjustment until it is no longer possible, we arrive at the situation described earlier. $\blacksquare$ The proof of the lower bound also gives away the construction. When $n = 2^m-1$, we can split the staircase into an $2^{m-1} \cdot 2^{m-1}$ square plus two staircases with width $2^{m-1}-1$. So the total perimeter within one staircase is at least $2^{m+1} \cdot m$. The construction matches the lower bound, ending the proof.

Generalize to $n\times n$ grids. Focus attention to the lower half staircase of an $n\times n$ grid, call it $S_n$, and suppose the staircase goes from northwest down to southeast. Let $f(n)$ be the minimum perimeter sum in this case. Suppose we have some rectangle tiling with minimal perimeter sum. Let $ABCD$ be the rectangle containing the $1\times 1$ most southeast square, where $A$ is the lower left corner of $S_n$ and $ABCD$ is labeled counterclockwise. The claim is that $C$ is on the main diagonal of $S_n$ (assuming the configuration is optimal).

Suppose to the contrary that the $1\times 1$ square with lower right corner $C$ is in $S_m$ (the case where the $1\times 1$ square with upper left corner in $S_n$ is similar). Let the rectangle containing this square be $WXYZ$, as shown in the figure. We assume that $Z\ne C$ for now, and we will deal with that case later. Let $P$ be the projection of $Z$ and $Q$ the projection of $X$. We now construct a new tiling with smaller perimeter sum, which will be the desired contradiction. Firstly, split any rectangles that cross $XQ$ or $ZP$ through those lines. This adds at most \[2\cdot XQ + 2\cdot ZP\]to the perimeter sum. Now the rectangle $QYPA$ either contains all rectangles in the tiling, or does not intersect them at all. We now erase all rectangles contained within $QYPA$ and add in $QYPA$. The amount of perimeter we lose is clearly at least \[2\cdot (DW+WX+WC+CZ+CB),\]so in this process, we lose at least \[2\cdot (WX+WC+CZ)\]perimeter. This means that our new configuration has lower perimeter sum, as desired. In the case that $Z=C$, the splitting step adds at most \[2\cdot XQ\]to the perimeter sum, and the second step loses at least \[2\cdot(WD+WC+WX)\]perimeter sum, so we lost at least $2\cdot(WC+WX)$ perimeter sum. This means that our new configuration has lower perimeter sum, as desired. Thus, we may assume that $C$ is on the main diagonal. This splits $S_n$ into $S_a$ and $S_{n-a}$ for some $n$, so \[f(n) \ge 2n+\min_{a\in[n-1]}[f(a)+f(n-a)].\]Equality is clearly achieved by simply doing an optimal construction for $S_a$ and $S_{n-a}$, so we in fact have \[f(n) = 2n+\min_{a\in[n-1]}[f(a)+f(n-a)].\]We claim that if $n=2^m+r$ where $0\le r\le 2^m-1$, then \[f(n) = 2mn + 4r.\]This is easy to verify by induction, so we have $f(2^m) = m2^{m+1}$, so the final answer is $\boxed{2m\cdot 2^{m+1}+4\cdot 2^m}$.

The answer is $(m+1)2^{m+2}$. Let $2^m=n$. Indeed, the $2^m$ $1\times 1$ squares divide the board into $2$ parts, each of which is a $n-1\times n-1$ ladder. Therefore, it suffices to show that the minimum perimeter is $\frac{1}{2}((m+1)2^{m+2}-2^{m+2})=m2^{m+1}$. We first set up some notations [asy][asy] size(8cm); real labelscalefactor = 0.5; /* changes label-to-point distance */pen dps = linewidth(0.7) + fontsize(0); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -35.423371958799834, xmax = 22.433614115319543, ymin = -26.189334968757535, ymax = 18.00570035251907; /* image dimensions */pen zzttqq = rgb(0.6,0.2,0); pen fuqqzz = rgb(0.9568627450980393,0,0.6); draw((-14.875203620475027,11.53179416568462)--(-14.875203620475027,4.713573081528168)--(-8.056982536318575,4.713573081528168)--(-8.056982536318575,11.53179416568462)--cycle, linewidth(0.8) + blue); draw((-8.056982536318575,4.713573081528168)--(-14.875203620475027,4.713573081528168)--(-14.875203620475027,-2.104648002628283)--(-8.056982536318575,-2.1046480026282843)--cycle, linewidth(0.8) + zzttqq); draw((-8.056982536318575,-2.1046480026282843)--(-14.875203620475027,-2.104648002628283)--(-14.875203620475027,-8.922869086784733)--(-8.056982536318577,-8.922869086784734)--cycle, linewidth(0.8) + zzttqq); draw((-8.056982536318577,-8.922869086784734)--(-14.875203620475027,-8.922869086784733)--(-14.875203620475029,-15.74109017094118)--(-8.05698253631858,-15.741090170941183)--cycle, linewidth(0.8) + fuqqzz); draw((-8.056982536318575,-2.1046480026282843)--(-8.056982536318577,-8.922869086784734)--(-1.238761452162127,-8.922869086784736)--(-1.2387614521621244,-2.1046480026282866)--cycle, linewidth(0.8) + fuqqzz); draw((-8.056982536318575,4.713573081528168)--(-8.056982536318575,-2.1046480026282843)--(-1.2387614521621235,-2.1046480026282848)--(-1.2387614521621226,4.713573081528168)--cycle, linewidth(0.8) + zzttqq); draw((-8.056982536318575,11.53179416568462)--(-8.056982536318575,4.713573081528168)--(-1.2387614521621235,4.713573081528168)--(-1.2387614521621226,11.53179416568462)--cycle, linewidth(0.8) + zzttqq); draw((-1.2387614521621226,11.53179416568462)--(-1.2387614521621226,4.713573081528168)--(5.579459631994328,4.713573081528168)--(5.579459631994329,11.53179416568462)--cycle, linewidth(0.8) + zzttqq); draw((-1.2387614521621226,4.713573081528168)--(-1.2387614521621244,-2.1046480026282866)--(5.579459631994328,-2.1046480026282888)--(5.579459631994331,4.713573081528165)--cycle, linewidth(0.8) + fuqqzz); draw((5.579459631994329,11.53179416568462)--(5.579459631994328,4.713573081528168)--(12.39768071615078,4.713573081528168)--(12.39768071615078,11.53179416568462)--cycle, linewidth(0.8) + fuqqzz); /* draw figures */draw((-14.875203620475027,11.53179416568462)--(-14.875203620475027,4.713573081528168), linewidth(0.8) + blue); draw((-14.875203620475027,4.713573081528168)--(-8.056982536318575,4.713573081528168), linewidth(0.8) + blue); draw((-8.056982536318575,4.713573081528168)--(-8.056982536318575,11.53179416568462), linewidth(0.8) + blue); draw((-8.056982536318575,11.53179416568462)--(-14.875203620475027,11.53179416568462), linewidth(0.8) + blue); draw((-8.056982536318575,4.713573081528168)--(-14.875203620475027,4.713573081528168), linewidth(0.8) + zzttqq); draw((-14.875203620475027,4.713573081528168)--(-14.875203620475027,-2.104648002628283), linewidth(0.8) + zzttqq); draw((-14.875203620475027,-2.104648002628283)--(-8.056982536318575,-2.1046480026282843), linewidth(0.8) + zzttqq); draw((-8.056982536318575,-2.1046480026282843)--(-8.056982536318575,4.713573081528168), linewidth(0.8) + zzttqq); draw((-8.056982536318575,-2.1046480026282843)--(-14.875203620475027,-2.104648002628283), linewidth(0.8) + zzttqq); draw((-14.875203620475027,-2.104648002628283)--(-14.875203620475027,-8.922869086784733), linewidth(0.8) + zzttqq); draw((-14.875203620475027,-8.922869086784733)--(-8.056982536318577,-8.922869086784734), linewidth(0.8) + zzttqq); draw((-8.056982536318577,-8.922869086784734)--(-8.056982536318575,-2.1046480026282843), linewidth(0.8) + zzttqq); draw((-8.056982536318577,-8.922869086784734)--(-14.875203620475027,-8.922869086784733), linewidth(0.8) + fuqqzz); draw((-14.875203620475027,-8.922869086784733)--(-14.875203620475029,-15.74109017094118), linewidth(0.8) + fuqqzz); draw((-14.875203620475029,-15.74109017094118)--(-8.05698253631858,-15.741090170941183), linewidth(0.8) + fuqqzz); draw((-8.05698253631858,-15.741090170941183)--(-8.056982536318577,-8.922869086784734), linewidth(0.8) + fuqqzz); draw((-8.056982536318575,-2.1046480026282843)--(-8.056982536318577,-8.922869086784734), linewidth(0.8) + fuqqzz); draw((-8.056982536318577,-8.922869086784734)--(-1.238761452162127,-8.922869086784736), linewidth(0.8) + fuqqzz); draw((-1.238761452162127,-8.922869086784736)--(-1.2387614521621244,-2.1046480026282866), linewidth(0.8) + fuqqzz); draw((-1.2387614521621244,-2.1046480026282866)--(-8.056982536318575,-2.1046480026282843), linewidth(0.8) + fuqqzz); draw((-8.056982536318575,4.713573081528168)--(-8.056982536318575,-2.1046480026282843), linewidth(0.8) + zzttqq); draw((-8.056982536318575,-2.1046480026282843)--(-1.2387614521621235,-2.1046480026282848), linewidth(0.8) + zzttqq); draw((-1.2387614521621235,-2.1046480026282848)--(-1.2387614521621226,4.713573081528168), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,4.713573081528168)--(-8.056982536318575,4.713573081528168), linewidth(0.8) + zzttqq); draw((-8.056982536318575,11.53179416568462)--(-8.056982536318575,4.713573081528168), linewidth(0.8) + zzttqq); draw((-8.056982536318575,4.713573081528168)--(-1.2387614521621235,4.713573081528168), linewidth(0.8) + zzttqq); draw((-1.2387614521621235,4.713573081528168)--(-1.2387614521621226,11.53179416568462), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,11.53179416568462)--(-8.056982536318575,11.53179416568462), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,11.53179416568462)--(-1.2387614521621226,4.713573081528168), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,4.713573081528168)--(5.579459631994328,4.713573081528168), linewidth(0.8) + zzttqq); draw((5.579459631994328,4.713573081528168)--(5.579459631994329,11.53179416568462), linewidth(0.8) + zzttqq); draw((5.579459631994329,11.53179416568462)--(-1.2387614521621226,11.53179416568462), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,4.713573081528168)--(-1.2387614521621244,-2.1046480026282866), linewidth(0.8) + fuqqzz); draw((-1.2387614521621244,-2.1046480026282866)--(5.579459631994328,-2.1046480026282888), linewidth(0.8) + fuqqzz); draw((5.579459631994328,-2.1046480026282888)--(5.579459631994331,4.713573081528165), linewidth(0.8) + fuqqzz); draw((5.579459631994331,4.713573081528165)--(-1.2387614521621226,4.713573081528168), linewidth(0.8) + fuqqzz); draw((5.579459631994329,11.53179416568462)--(5.579459631994328,4.713573081528168), linewidth(0.8) + fuqqzz); draw((5.579459631994328,4.713573081528168)--(12.39768071615078,4.713573081528168), linewidth(0.8) + fuqqzz); draw((12.39768071615078,4.713573081528168)--(12.39768071615078,11.53179416568462), linewidth(0.8) + fuqqzz); draw((12.39768071615078,11.53179416568462)--(5.579459631994329,11.53179416568462), linewidth(0.8) + fuqqzz); /* dots and labels */dot((-14.875203620475027,11.53179416568462),dotstyle); dot((-14.875203620475027,4.713573081528168),dotstyle); dot((-8.056982536318575,4.713573081528168),dotstyle); dot((-8.056982536318575,11.53179416568462),dotstyle); dot((-14.875203620475027,-2.104648002628283),dotstyle); dot((-8.056982536318575,-2.1046480026282843),dotstyle); dot((-14.875203620475027,-8.922869086784733),dotstyle); dot((-8.056982536318577,-8.922869086784734),dotstyle); dot((-14.875203620475029,-15.74109017094118),dotstyle); dot((-8.05698253631858,-15.741090170941183),dotstyle); dot((-1.238761452162127,-8.922869086784736),dotstyle); dot((-1.2387614521621244,-2.1046480026282866),dotstyle); dot((-1.2387614521621235,-2.1046480026282848),dotstyle); dot((-1.2387614521621226,4.713573081528168),dotstyle); dot((-1.2387614521621235,4.713573081528168),dotstyle); dot((-1.2387614521621226,11.53179416568462),dotstyle); dot((5.579459631994328,4.713573081528168),dotstyle); dot((5.579459631994329,11.53179416568462),dotstyle); dot((5.579459631994328,-2.1046480026282888),dotstyle); dot((5.579459631994331,4.713573081528165),dotstyle); dot((12.39768071615078,4.713573081528168),dotstyle); dot((12.39768071615078,11.53179416568462),dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy][/asy] We call the blue (top left-hand) cell the corner cell and the pink cells the diagonal cell. ALternatively, we can denote by $(i,j)$ the cell in the $i^{th}$ column from the left and $j^{th}$ column from the top. Then the corner cell will be $(1,1)$ and the diagonal cells will be the cells with $i+j=n+1$ .We consider the partition with the minimum perimeter. Claim. There exists one minimum configuration in which the corner cell is in the same rectangle with one of the diagonal cells. Proof. Consider the rectangle which contains $(1,1)$, call it $R$. Let $(i,j)$ be the vertex diagonally opposite to $(1,1)$ in the rectangle. If $i+j=n+1$ then we are done. Otherwise, consider the cells $(i+1,j),(i,j+1)$, then at least one of them is not in the same rectangle as $(i+1,j+1)$ (if $(i+1,j+1)$) doesn't exist then of course they can't be in the same rectangle.) Suppose $(i,j+1)$ is not. Then, the cells $(x,j+1)$, where $1\leq x\leq i$ are occupied by some rectangles, called them $R_1,...,R_k$, with height $h_1,...,h_k$ [asy][asy] size(6cm); real labelscalefactor = 0.5; /* changes label-to-point distance */pen dps = linewidth(0.7) + fontsize(0); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -1.9103316892425823, xmax = 55.946654384876815, ymin = -69.9259155667844, ymax = -25.730880245507777; /* image dimensions */pen zzttqq = rgb(0.6,0.2,0); pen fuqqzz = rgb(0.9568627450980393,0,0.6); draw((-14.875203620475027,11.53179416568462)--(-14.875203620475027,4.713573081528168)--(-8.056982536318575,4.713573081528168)--(-8.056982536318575,11.53179416568462)--cycle, linewidth(0.8) + blue); draw((-8.056982536318575,4.713573081528168)--(-14.875203620475027,4.713573081528168)--(-14.875203620475027,-2.104648002628283)--(-8.056982536318575,-2.1046480026282843)--cycle, linewidth(0.8) + zzttqq); draw((-8.056982536318575,-2.1046480026282843)--(-14.875203620475027,-2.104648002628283)--(-14.875203620475027,-8.922869086784733)--(-8.056982536318577,-8.922869086784734)--cycle, linewidth(0.8) + zzttqq); draw((-8.056982536318577,-8.922869086784734)--(-14.875203620475027,-8.922869086784733)--(-14.875203620475029,-15.74109017094118)--(-8.05698253631858,-15.741090170941183)--cycle, linewidth(0.8) + fuqqzz); draw((-8.056982536318575,-2.1046480026282843)--(-8.056982536318577,-8.922869086784734)--(-1.238761452162127,-8.922869086784736)--(-1.2387614521621244,-2.1046480026282866)--cycle, linewidth(0.8) + fuqqzz); draw((-8.056982536318575,4.713573081528168)--(-8.056982536318575,-2.1046480026282843)--(-1.2387614521621235,-2.1046480026282848)--(-1.2387614521621226,4.713573081528168)--cycle, linewidth(0.8) + zzttqq); draw((-8.056982536318575,11.53179416568462)--(-8.056982536318575,4.713573081528168)--(-1.2387614521621235,4.713573081528168)--(-1.2387614521621226,11.53179416568462)--cycle, linewidth(0.8) + zzttqq); draw((-1.2387614521621226,11.53179416568462)--(-1.2387614521621226,4.713573081528168)--(5.579459631994328,4.713573081528168)--(5.579459631994329,11.53179416568462)--cycle, linewidth(0.8) + zzttqq); draw((-1.2387614521621226,4.713573081528168)--(-1.2387614521621244,-2.1046480026282866)--(5.579459631994328,-2.1046480026282888)--(5.579459631994331,4.713573081528165)--cycle, linewidth(0.8) + fuqqzz); draw((5.579459631994329,11.53179416568462)--(5.579459631994328,4.713573081528168)--(12.39768071615078,4.713573081528168)--(12.39768071615078,11.53179416568462)--cycle, linewidth(0.8) + fuqqzz); /* draw figures */draw((-14.875203620475027,11.53179416568462)--(-14.875203620475027,4.713573081528168), linewidth(0.8) + blue); draw((-14.875203620475027,4.713573081528168)--(-8.056982536318575,4.713573081528168), linewidth(0.8) + blue); draw((-8.056982536318575,4.713573081528168)--(-8.056982536318575,11.53179416568462), linewidth(0.8) + blue); draw((-8.056982536318575,11.53179416568462)--(-14.875203620475027,11.53179416568462), linewidth(0.8) + blue); draw((-8.056982536318575,4.713573081528168)--(-14.875203620475027,4.713573081528168), linewidth(0.8) + zzttqq); draw((-14.875203620475027,4.713573081528168)--(-14.875203620475027,-2.104648002628283), linewidth(0.8) + zzttqq); draw((-14.875203620475027,-2.104648002628283)--(-8.056982536318575,-2.1046480026282843), linewidth(0.8) + zzttqq); draw((-8.056982536318575,-2.1046480026282843)--(-8.056982536318575,4.713573081528168), linewidth(0.8) + zzttqq); draw((-8.056982536318575,-2.1046480026282843)--(-14.875203620475027,-2.104648002628283), linewidth(0.8) + zzttqq); draw((-14.875203620475027,-2.104648002628283)--(-14.875203620475027,-8.922869086784733), linewidth(0.8) + zzttqq); draw((-14.875203620475027,-8.922869086784733)--(-8.056982536318577,-8.922869086784734), linewidth(0.8) + zzttqq); draw((-8.056982536318577,-8.922869086784734)--(-8.056982536318575,-2.1046480026282843), linewidth(0.8) + zzttqq); draw((-8.056982536318577,-8.922869086784734)--(-14.875203620475027,-8.922869086784733), linewidth(0.8) + fuqqzz); draw((-14.875203620475027,-8.922869086784733)--(-14.875203620475029,-15.74109017094118), linewidth(0.8) + fuqqzz); draw((-14.875203620475029,-15.74109017094118)--(-8.05698253631858,-15.741090170941183), linewidth(0.8) + fuqqzz); draw((-8.05698253631858,-15.741090170941183)--(-8.056982536318577,-8.922869086784734), linewidth(0.8) + fuqqzz); draw((-8.056982536318575,-2.1046480026282843)--(-8.056982536318577,-8.922869086784734), linewidth(0.8) + fuqqzz); draw((-8.056982536318577,-8.922869086784734)--(-1.238761452162127,-8.922869086784736), linewidth(0.8) + fuqqzz); draw((-1.238761452162127,-8.922869086784736)--(-1.2387614521621244,-2.1046480026282866), linewidth(0.8) + fuqqzz); draw((-1.2387614521621244,-2.1046480026282866)--(-8.056982536318575,-2.1046480026282843), linewidth(0.8) + fuqqzz); draw((-8.056982536318575,4.713573081528168)--(-8.056982536318575,-2.1046480026282843), linewidth(0.8) + zzttqq); draw((-8.056982536318575,-2.1046480026282843)--(-1.2387614521621235,-2.1046480026282848), linewidth(0.8) + zzttqq); draw((-1.2387614521621235,-2.1046480026282848)--(-1.2387614521621226,4.713573081528168), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,4.713573081528168)--(-8.056982536318575,4.713573081528168), linewidth(0.8) + zzttqq); draw((-8.056982536318575,11.53179416568462)--(-8.056982536318575,4.713573081528168), linewidth(0.8) + zzttqq); draw((-8.056982536318575,4.713573081528168)--(-1.2387614521621235,4.713573081528168), linewidth(0.8) + zzttqq); draw((-1.2387614521621235,4.713573081528168)--(-1.2387614521621226,11.53179416568462), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,11.53179416568462)--(-8.056982536318575,11.53179416568462), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,11.53179416568462)--(-1.2387614521621226,4.713573081528168), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,4.713573081528168)--(5.579459631994328,4.713573081528168), linewidth(0.8) + zzttqq); draw((5.579459631994328,4.713573081528168)--(5.579459631994329,11.53179416568462), linewidth(0.8) + zzttqq); draw((5.579459631994329,11.53179416568462)--(-1.2387614521621226,11.53179416568462), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,4.713573081528168)--(-1.2387614521621244,-2.1046480026282866), linewidth(0.8) + fuqqzz); draw((-1.2387614521621244,-2.1046480026282866)--(5.579459631994328,-2.1046480026282888), linewidth(0.8) + fuqqzz); draw((5.579459631994328,-2.1046480026282888)--(5.579459631994331,4.713573081528165), linewidth(0.8) + fuqqzz); draw((5.579459631994331,4.713573081528165)--(-1.2387614521621226,4.713573081528168), linewidth(0.8) + fuqqzz); draw((5.579459631994329,11.53179416568462)--(5.579459631994328,4.713573081528168), linewidth(0.8) + fuqqzz); draw((5.579459631994328,4.713573081528168)--(12.39768071615078,4.713573081528168), linewidth(0.8) + fuqqzz); draw((12.39768071615078,4.713573081528168)--(12.39768071615078,11.53179416568462), linewidth(0.8) + fuqqzz); draw((12.39768071615078,11.53179416568462)--(5.579459631994329,11.53179416568462), linewidth(0.8) + fuqqzz); draw((13.8146653182241,-41.63925914227436)--(40.08412096043521,-41.73095008692431), linewidth(0.8)); draw((13.771429180245608,-54.02641267311257)--(18.17735972395736,-54.04179113923373), linewidth(0.8)); draw((18.1921652191575,-49.800016764393966)--(23.63639338824057,-49.819019305996356), linewidth(0.8)); draw((34.21431439638561,-56.548835955258994)--(40.03232971060236,-56.56914316403462), linewidth(0.8)); draw((13.846731046333241,-32.45242803900474)--(13.771429180245608,-54.02641267311257), linewidth(0.8)); draw((18.220595861935852,-41.65463760839552)--(18.17735972395736,-54.04179113923373), linewidth(0.8)); draw((23.664824031018927,-41.6736401499979)--(23.601671075180573,-59.766961997686906), linewidth(0.8)); draw((34.2029526903801,-59.80396472583769)--(34.266105646218456,-41.71064287814868), linewidth(0.8)); draw((40.116186688544346,-32.544118983654684)--(40.03232971060236,-56.56914316403462), linewidth(0.8)); draw((23.601671075180573,-59.766961997686906)--(34.2029526903801,-59.80396472583769), linewidth(0.8)); draw((13.846731046333241,-32.45242803900474)--(40.116186688544346,-32.544118983654684), linewidth(0.8)); /* dots and labels */dot((-14.875203620475027,11.53179416568462),dotstyle); dot((-14.875203620475027,4.713573081528168),dotstyle); dot((-8.056982536318575,4.713573081528168),dotstyle); dot((-8.056982536318575,11.53179416568462),dotstyle); dot((-14.875203620475027,-2.104648002628283),dotstyle); dot((-8.056982536318575,-2.1046480026282843),dotstyle); dot((-14.875203620475027,-8.922869086784733),dotstyle); dot((-8.056982536318577,-8.922869086784734),dotstyle); dot((-14.875203620475029,-15.74109017094118),dotstyle); dot((-8.05698253631858,-15.741090170941183),dotstyle); dot((-1.238761452162127,-8.922869086784736),dotstyle); dot((-1.2387614521621244,-2.1046480026282866),dotstyle); dot((-1.2387614521621235,-2.1046480026282848),dotstyle); dot((-1.2387614521621226,4.713573081528168),dotstyle); dot((-1.2387614521621235,4.713573081528168),dotstyle); dot((-1.2387614521621226,11.53179416568462),dotstyle); dot((5.579459631994328,4.713573081528168),dotstyle); dot((5.579459631994329,11.53179416568462),dotstyle); dot((5.579459631994328,-2.1046480026282888),dotstyle); dot((5.579459631994331,4.713573081528165),dotstyle); dot((12.39768071615078,4.713573081528168),dotstyle); dot((12.39768071615078,11.53179416568462),dotstyle); dot((13.8146653182241,-41.63925914227436),dotstyle); dot((40.08412096043521,-41.73095008692431),dotstyle); dot((13.803192596235494,-44.92619399200999),dotstyle); dot((13.826138040212705,-38.35232429253873),dotstyle); dot((40.072648238446604,-45.01788493665995),linewidth(4pt) + dotstyle); dot((40.09559368242382,-38.44401523718869),linewidth(4pt) + dotstyle); dot((13.846731046333241,-32.45242803900474),dotstyle); dot((40.116186688544346,-32.544118983654684),linewidth(4pt) + dotstyle); dot((18.220595861935852,-41.65463760839552),dotstyle); dot((23.664824031018927,-41.6736401499979),dotstyle); dot((34.266105646218456,-41.71064287814868),dotstyle); dot((13.771429180245608,-54.02641267311257),dotstyle); dot((18.1921652191575,-49.800016764393966),dotstyle); dot((34.21431439638561,-56.548835955258994),dotstyle); dot((23.601671075180573,-59.766961997686906),dotstyle); dot((23.63639338824057,-49.819019305996356),linewidth(4pt) + dotstyle); dot((18.17735972395736,-54.04179113923373),linewidth(4pt) + dotstyle); dot((40.03232971060236,-56.56914316403462),linewidth(4pt) + dotstyle); dot((34.2029526903801,-59.80396472583769),linewidth(4pt) + dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy][/asy] Then we can consider the configuration where we cut off the upper-most row of the rectangles below and replace the rectangle $R$ with $R'$, the one with diagonal being $(1,1)$ and $(i+1,j)$. (as shown in the following figure) [asy][asy] size(6cm); real labelscalefactor = 0.5; /* changes label-to-point distance */pen dps = linewidth(0.7) + fontsize(0); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -1.9103316892425894, xmax = 55.94665438487682, ymin = -69.9259155667844, ymax = -25.730880245507763; /* image dimensions */pen zzttqq = rgb(0.6,0.2,0); pen fuqqzz = rgb(0.9568627450980393,0,0.6); draw((-14.875203620475027,11.53179416568462)--(-14.875203620475027,4.713573081528168)--(-8.056982536318575,4.713573081528168)--(-8.056982536318575,11.53179416568462)--cycle, linewidth(0.8) + blue); draw((-8.056982536318575,4.713573081528168)--(-14.875203620475027,4.713573081528168)--(-14.875203620475027,-2.104648002628283)--(-8.056982536318575,-2.1046480026282843)--cycle, linewidth(0.8) + zzttqq); draw((-8.056982536318575,-2.1046480026282843)--(-14.875203620475027,-2.104648002628283)--(-14.875203620475027,-8.922869086784733)--(-8.056982536318577,-8.922869086784734)--cycle, linewidth(0.8) + zzttqq); draw((-8.056982536318577,-8.922869086784734)--(-14.875203620475027,-8.922869086784733)--(-14.875203620475029,-15.74109017094118)--(-8.05698253631858,-15.741090170941183)--cycle, linewidth(0.8) + fuqqzz); draw((-8.056982536318575,-2.1046480026282843)--(-8.056982536318577,-8.922869086784734)--(-1.238761452162127,-8.922869086784736)--(-1.2387614521621244,-2.1046480026282866)--cycle, linewidth(0.8) + fuqqzz); draw((-8.056982536318575,4.713573081528168)--(-8.056982536318575,-2.1046480026282843)--(-1.2387614521621235,-2.1046480026282848)--(-1.2387614521621226,4.713573081528168)--cycle, linewidth(0.8) + zzttqq); draw((-8.056982536318575,11.53179416568462)--(-8.056982536318575,4.713573081528168)--(-1.2387614521621235,4.713573081528168)--(-1.2387614521621226,11.53179416568462)--cycle, linewidth(0.8) + zzttqq); draw((-1.2387614521621226,11.53179416568462)--(-1.2387614521621226,4.713573081528168)--(5.579459631994328,4.713573081528168)--(5.579459631994329,11.53179416568462)--cycle, linewidth(0.8) + zzttqq); draw((-1.2387614521621226,4.713573081528168)--(-1.2387614521621244,-2.1046480026282866)--(5.579459631994328,-2.1046480026282888)--(5.579459631994331,4.713573081528165)--cycle, linewidth(0.8) + fuqqzz); draw((5.579459631994329,11.53179416568462)--(5.579459631994328,4.713573081528168)--(12.39768071615078,4.713573081528168)--(12.39768071615078,11.53179416568462)--cycle, linewidth(0.8) + fuqqzz); /* draw figures */draw((-14.875203620475027,11.53179416568462)--(-14.875203620475027,4.713573081528168), linewidth(0.8) + blue); draw((-14.875203620475027,4.713573081528168)--(-8.056982536318575,4.713573081528168), linewidth(0.8) + blue); draw((-8.056982536318575,4.713573081528168)--(-8.056982536318575,11.53179416568462), linewidth(0.8) + blue); draw((-8.056982536318575,11.53179416568462)--(-14.875203620475027,11.53179416568462), linewidth(0.8) + blue); draw((-8.056982536318575,4.713573081528168)--(-14.875203620475027,4.713573081528168), linewidth(0.8) + zzttqq); draw((-14.875203620475027,4.713573081528168)--(-14.875203620475027,-2.104648002628283), linewidth(0.8) + zzttqq); draw((-14.875203620475027,-2.104648002628283)--(-8.056982536318575,-2.1046480026282843), linewidth(0.8) + zzttqq); draw((-8.056982536318575,-2.1046480026282843)--(-8.056982536318575,4.713573081528168), linewidth(0.8) + zzttqq); draw((-8.056982536318575,-2.1046480026282843)--(-14.875203620475027,-2.104648002628283), linewidth(0.8) + zzttqq); draw((-14.875203620475027,-2.104648002628283)--(-14.875203620475027,-8.922869086784733), linewidth(0.8) + zzttqq); draw((-14.875203620475027,-8.922869086784733)--(-8.056982536318577,-8.922869086784734), linewidth(0.8) + zzttqq); draw((-8.056982536318577,-8.922869086784734)--(-8.056982536318575,-2.1046480026282843), linewidth(0.8) + zzttqq); draw((-8.056982536318577,-8.922869086784734)--(-14.875203620475027,-8.922869086784733), linewidth(0.8) + fuqqzz); draw((-14.875203620475027,-8.922869086784733)--(-14.875203620475029,-15.74109017094118), linewidth(0.8) + fuqqzz); draw((-14.875203620475029,-15.74109017094118)--(-8.05698253631858,-15.741090170941183), linewidth(0.8) + fuqqzz); draw((-8.05698253631858,-15.741090170941183)--(-8.056982536318577,-8.922869086784734), linewidth(0.8) + fuqqzz); draw((-8.056982536318575,-2.1046480026282843)--(-8.056982536318577,-8.922869086784734), linewidth(0.8) + fuqqzz); draw((-8.056982536318577,-8.922869086784734)--(-1.238761452162127,-8.922869086784736), linewidth(0.8) + fuqqzz); draw((-1.238761452162127,-8.922869086784736)--(-1.2387614521621244,-2.1046480026282866), linewidth(0.8) + fuqqzz); draw((-1.2387614521621244,-2.1046480026282866)--(-8.056982536318575,-2.1046480026282843), linewidth(0.8) + fuqqzz); draw((-8.056982536318575,4.713573081528168)--(-8.056982536318575,-2.1046480026282843), linewidth(0.8) + zzttqq); draw((-8.056982536318575,-2.1046480026282843)--(-1.2387614521621235,-2.1046480026282848), linewidth(0.8) + zzttqq); draw((-1.2387614521621235,-2.1046480026282848)--(-1.2387614521621226,4.713573081528168), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,4.713573081528168)--(-8.056982536318575,4.713573081528168), linewidth(0.8) + zzttqq); draw((-8.056982536318575,11.53179416568462)--(-8.056982536318575,4.713573081528168), linewidth(0.8) + zzttqq); draw((-8.056982536318575,4.713573081528168)--(-1.2387614521621235,4.713573081528168), linewidth(0.8) + zzttqq); draw((-1.2387614521621235,4.713573081528168)--(-1.2387614521621226,11.53179416568462), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,11.53179416568462)--(-8.056982536318575,11.53179416568462), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,11.53179416568462)--(-1.2387614521621226,4.713573081528168), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,4.713573081528168)--(5.579459631994328,4.713573081528168), linewidth(0.8) + zzttqq); draw((5.579459631994328,4.713573081528168)--(5.579459631994329,11.53179416568462), linewidth(0.8) + zzttqq); draw((5.579459631994329,11.53179416568462)--(-1.2387614521621226,11.53179416568462), linewidth(0.8) + zzttqq); draw((-1.2387614521621226,4.713573081528168)--(-1.2387614521621244,-2.1046480026282866), linewidth(0.8) + fuqqzz); draw((-1.2387614521621244,-2.1046480026282866)--(5.579459631994328,-2.1046480026282888), linewidth(0.8) + fuqqzz); draw((5.579459631994328,-2.1046480026282888)--(5.579459631994331,4.713573081528165), linewidth(0.8) + fuqqzz); draw((5.579459631994331,4.713573081528165)--(-1.2387614521621226,4.713573081528168), linewidth(0.8) + fuqqzz); draw((5.579459631994329,11.53179416568462)--(5.579459631994328,4.713573081528168), linewidth(0.8) + fuqqzz); draw((5.579459631994328,4.713573081528168)--(12.39768071615078,4.713573081528168), linewidth(0.8) + fuqqzz); draw((12.39768071615078,4.713573081528168)--(12.39768071615078,11.53179416568462), linewidth(0.8) + fuqqzz); draw((12.39768071615078,11.53179416568462)--(5.579459631994329,11.53179416568462), linewidth(0.8) + fuqqzz); draw((13.771429180245608,-54.02641267311257)--(18.17735972395736,-54.04179113923373), linewidth(0.8)); draw((18.1921652191575,-49.800016764393966)--(23.63639338824057,-49.819019305996356), linewidth(0.8)); draw((34.21431439638561,-56.548835955258994)--(40.03232971060236,-56.56914316403462), linewidth(0.8)); draw((13.846731046333241,-32.45242803900474)--(13.771429180245608,-54.02641267311257), linewidth(0.8)); draw((40.116186688544346,-32.544118983654684)--(40.03232971060236,-56.56914316403462), linewidth(0.8)); draw((23.601900148770067,-59.70133241429752)--(34.20318176396959,-59.738335142448314), linewidth(0.8)); draw((13.846731046333241,-32.45242803900474)--(40.116186688544346,-32.544118983654684), linewidth(0.8)); draw((13.803192596235494,-44.92619399200999)--(40.072648238446604,-45.01788493665995), linewidth(0.8)); draw((18.209123139947245,-44.941572458131155)--(18.17735972395736,-54.04179113923373), linewidth(0.8)); draw((23.65335130903032,-44.960574999733545)--(23.601900148770067,-59.70133241429752), linewidth(0.8)); draw((34.25463292422984,-44.997577727884334)--(34.20318176396959,-59.738335142448314), linewidth(0.8)); /* dots and labels */dot((-14.875203620475027,11.53179416568462),dotstyle); dot((-14.875203620475027,4.713573081528168),dotstyle); dot((-8.056982536318575,4.713573081528168),dotstyle); dot((-8.056982536318575,11.53179416568462),dotstyle); dot((-14.875203620475027,-2.104648002628283),dotstyle); dot((-8.056982536318575,-2.1046480026282843),dotstyle); dot((-14.875203620475027,-8.922869086784733),dotstyle); dot((-8.056982536318577,-8.922869086784734),dotstyle); dot((-14.875203620475029,-15.74109017094118),dotstyle); dot((-8.05698253631858,-15.741090170941183),dotstyle); dot((-1.238761452162127,-8.922869086784736),dotstyle); dot((-1.2387614521621244,-2.1046480026282866),dotstyle); dot((-1.2387614521621235,-2.1046480026282848),dotstyle); dot((-1.2387614521621226,4.713573081528168),dotstyle); dot((-1.2387614521621235,4.713573081528168),dotstyle); dot((-1.2387614521621226,11.53179416568462),dotstyle); dot((5.579459631994328,4.713573081528168),dotstyle); dot((5.579459631994329,11.53179416568462),dotstyle); dot((5.579459631994328,-2.1046480026282888),dotstyle); dot((5.579459631994331,4.713573081528165),dotstyle); dot((12.39768071615078,4.713573081528168),dotstyle); dot((12.39768071615078,11.53179416568462),dotstyle); dot((13.8146653182241,-41.63925914227436),dotstyle); dot((40.08412096043521,-41.73095008692431),dotstyle); dot((13.803192596235494,-44.92619399200999),dotstyle); dot((13.826138040212705,-38.35232429253873),dotstyle); dot((40.072648238446604,-45.01788493665995),linewidth(4pt) + dotstyle); dot((40.09559368242382,-38.44401523718869),linewidth(4pt) + dotstyle); dot((13.846731046333241,-32.45242803900474),dotstyle); dot((40.116186688544346,-32.544118983654684),linewidth(4pt) + dotstyle); dot((13.771429180245608,-54.02641267311257),dotstyle); dot((18.1921652191575,-49.800016764393966),dotstyle); dot((34.21431439638561,-56.548835955258994),dotstyle); dot((23.601900148770067,-59.70133241429752),dotstyle); dot((23.63639338824057,-49.819019305996356),linewidth(4pt) + dotstyle); dot((18.17735972395736,-54.04179113923373),linewidth(4pt) + dotstyle); dot((40.03232971060236,-56.56914316403462),linewidth(4pt) + dotstyle); dot((34.20318176396959,-59.738335142448314),linewidth(4pt) + dotstyle); dot((18.209123139947245,-44.941572458131155),linewidth(4pt) + dotstyle); dot((23.65335130903032,-44.960574999733545),linewidth(4pt) + dotstyle); dot((34.25463292422984,-44.997577727884334),linewidth(4pt) + dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy][/asy] Verctially, the perimeter is unchanged if $k=1$, and decreased if $k>1$. Horizontally, the perimeter is unchanged if $h_1,...,h_k>1$, and decreased if $h_p=1$ for some $1\leq p\leq k$. Therefore, the total perimeter will not decrease, repeat this procedure for a finite number of time and we will arrive at the state where the corner cell is in the same state as one of the diagoanl cell. $\blacksquare$ Now the problem is easy. Suppose the minimum perimeter of an $n$ ladder is $f(n)$, we claim that $f(2^m-1)=m^{2m+1}$ which will solve the problem. Indeed, if the corner cell is in the same rectangle as $(i,n+1-i)$, then this rectangle will divide the ladder into a $(i-1)\times(i-1)$ and a $(n-i)\times (n-i)$ ladder. In addition, this rectangle has perimeter $2(n+1)$. Therefore, we have $$f(n+1)=2(n+1)+\underset{0\leq i\leq n}{\min}(f(n-i)+f(i-1))$$Using this with easy (though tedious) induction we can show that if $\lfloor \log_2n\rfloor=a$ then $$f(n+1)-f(n)=2(a+2)$$Hence $$f(2^{m+1}-1)-f(2^m-1)=(m+2)2^{m+1}$$Combining this with the fact that $f(1)=4$ it is easy to see that $f(2^m-1)=m2^{m+1}$ as desired.

The answer is $2^{m+2}(m+1)$ First, define $f(n)$ as the minimum sum of perimeters of a rectangle tiling of a $n-1$ by $n-1$ staircase. I claim that $f(n) \geq 2n\log_{2}(n)$ We will prove this by induction on $n$. The base case of $n = 2$ is trivial, so assume it's true for all $i < n$. Consider the rectangle with the corner on the ith step of the staircase and with a vertex at the bottom-right of the staircase, where the maximal height of all rectangles that are adjacent to the bottom row have height $i$; it will split the staircase into two pieces of size $i$ and size $n-i$. First, if the actual rectangle at the ith step did not have a vertex at the bottom right, then by partitioning each rectangle that is between the other two staircase and the $i$ by $n-i$ rectangle, (without counting the edge that's formed by the partition), it is clear that the perimeter of the other two staircases stays the same, while the perimeter of the rectangles within the $i$ by $n-i$ rectangle is at least $2n$. Therefore, we have the following inequality: \[f(n) \geq f(i) + f(n-i-1) + 2n\]\[f(n) \geq 2(i)\log_{2}(i) + 2(n-i)\log_{2}(n-i) + 2n\]Now, by Jensens on the function $2x\log_{2}x$, we get that this expression is at least $2n\log_{2}n$, which completes the induction. Now, we can construct this by placing a $2^{m-1}$ by $2^{m-1}$ square from the $2^{m-1}$th step on the staircase, and inducting down. Therefore, the minimum sum of rectangle perimeters is $2\cdot m\cdot 2^{m+1} + 2^{m+2} = (m+1)2^{m+2}$.

Define a $S_t$ to be the subset of the chessboard that contains all cells which are all entirely below the main diagonal. Let $M(t)$ to be the minimum sum of rectangle perimeters of any partition of $S_t$. Clearly, the answer to the question is $2M(2^m-1)+2^{m+2}$. We claim that one of the ways to achieve minimum perimeter sum of $S_{2t+1}$ involves a $t+1\times t+1$ square which has one vertex at a vertex of $S_{2t+1}$, as shown below in red. Suppose not, then consider a better tiling which does not involve this square. For every instance of some rectangle that intersects the red rectangle, we may pare down the blue one so that it does not have anything inside the red one, and then once all such rectangles are taken care of, we can merge every rectangle on the interior of the red rectangle. Clearly this does not increase the number of partitioning segments of length $1$, as desired. Thus, $M(2t+1)=2M(t)+4(t+1)$ and it is easy by induction to see that $M(2^m-1)=m\cdot 2^{m+1}$ and \[2m(2^{m+1})+2^{m+2}=(m+1)2^{m+2}\]which is our answer.

Solved with NTguy, AN1729, kotmhn. Claim: For an $n\times n$ grid, the half of the minimum perimeter of the non-diagonal elements is $a_n=2n\lfloor \log_{2}n \rfloor$. We prove this by induction. We check base cases $a_0=0, a_1=0, a_2=4, a_3=12$. Assume that our formula is true for $k\le n$. Observe that $a_{m+n}\le a_m+a_n + 2(m+n)$. The RHS is maximum when $|m-n|$ is minimum ($n\log_2 n$ is convex). Hence, $a_{n+1}=a_{\lfloor\frac {n+1}{2}\rfloor}+a_{\lceil\frac{n+1}{2}\rceil}+2n+2$. $\blacksquare$