Problem 1990

Solution 1. For a $k \times k$ chessboard, we introduce in a standard way coordinates of the vertices of the cells and assume that the cell $C_{ij}$ in row $i$ and column $j$ has vertices $(i-1, j-1), (i-1, j), (i, j-1), (i, j)$, where $i, j \in \{1, \ldots, k\}$. Without loss of generality assume that the cells $C_{ii}$, $i=1, \ldots, k$, form a separate rectangle. Then we may consider the boards $B_{k} = \bigcup_{1 \leq i < j \leq k} C_{ij}$ below that diagonal and the congruent board $B_{k}' = \bigcup_{1 \leq j < i \leq k} C_{ij}$ above that diagonal separately because no rectangle can simultaneously cover cells from $B_{k}$ and $B_{k}'$. We will show that for $k = 2^{m}$ the smallest total perimeter of a rectangular partition of $B_{k}$ is $m 2^{m+1}$. Then the overall answer to the problem is $2 \cdot m 2^{m+1} + 4 \cdot 2^{m} = (m+1) 2^{m+2}$.

First we inductively construct for $m \geq 1$ a partition of $B_{2^{m}}$ with total perimeter $m 2^{m+1}$. If $m=0$, the board $B_{2^{m}}$ is empty and the total perimeter is 0. For $m \geq 0$, the board $B_{2^{m+1}}$ consists of a $2^{m} \times 2^{m}$ square in the lower right corner with vertices $(2^{m}, 2^{m}), (2^{m}, 2^{m+1}), (2^{m+1}, 2^{m}), (2^{m+1}, 2^{m+1})$ to which two boards congruent to $B_{2^{m}}$ are glued along the left and the upper margin. The square together with the inductive partitions of these two boards yield a partition with total perimeter $4 \cdot 2^{m} + 2 \cdot m 2^{m+1} = (m+1) 2^{m+2}$ and the induction step is complete.

Let
$$D_{k} = 2k \log_{2} k.$$
Note that $D_{k} = m 2^{m+1}$ if $k = 2^{m}$. Now we show by induction on $k$ that the total perimeter of a rectangular partition of $B_{k}$ is at least $D_{k}$. The case $k=1$ is trivial (see $m=0$ from above). Let the assertion be true for all positive integers less than $k$. We investigate a fixed rectangular partition of $B_{k}$ that attains the minimal total perimeter. Let $R$ be the rectangle that covers the cell $C_{1k}$ in the lower right corner. Let $(i, j)$ be the upper left corner of $R$. First we show that $i = j$. Assume that $i < j$. Then the line from $(i, j)$ to $(i+1, j)$ or from $(i, j)$ to $(i, j-1)$ must belong to the boundary of some rectangle in the partition. Without loss of generality assume that this is the case for the line from $(i, j)$ to $(i+1, j)$.

Case 1. No line from $(i, l)$ to $(i+1, l)$ where $j < l < k$ belongs to the boundary of some rectangle of the partition.
Then there is some rectangle $R'$ of the partition that has with $R$ the common side from $(i, j)$ to $(i, k)$. If we join these two rectangles to one rectangle we get a partition with smaller total perimeter, a contradiction.

Case 2. There is some $l$ such that $j < l < k$ and the line from $(i, l)$ to $(i+1, l)$ belongs to the boundary of some rectangle of the partition.
Then we replace the upper side of $R$ by the line $(i+1, j)$ to $(i+1, k)$ and for the rectangles whose lower side belongs to the line from $(i, j)$ to $(i, k)$ we shift the lower side upwards so that the new lower side belongs to the line from $(i+1, j)$ to $(i+1, k)$. In such a way we obtain a rectangular partition of $B_{k}$ with smaller total perimeter, a contradiction.

Now the fact that the upper left corner of $R$ has the coordinates $(i, i)$ is established. Consequently, the partition consists of $R$, of rectangles of a partition of a board congruent to $B_{i}$ and of rectangles of a partition of a board congruent to $B_{k-i}$. By the induction hypothesis, its total perimeter is at least
$$2(k-i) + 2i + D_{i} + D_{k-i} \geq 2k + 2i \log_{2} i + 2(k-i) \log_{2}(k-i).$$
Since the function $f(x) = 2x \log_{2} x$ is convex for $x > 0$, Jensen's inequality immediately shows that the minimum of the right hand side is attained for $i = k/2$. Hence the total perimeter of the optimal partition of $B_{k}$ is at least $2k + 2k/2 \log_{2} k/2 + 2(k/2) \log_{2}(k/2) = D_{k}$.

Solution 2. We start as in Solution 1 and present another proof that $m 2^{m+1}$ is a lower bound for the total perimeter of a partition of $B_{2^{m}}$ into $n$ rectangles. Let briefly $M = 2^{m}$. For $1 \leq i \leq M$, let $r_{i}$ denote the number of rectangles in the partition that cover some cell from row $i$ and let $c_{j}$ be the number of rectangles that cover some cell from column $j$. Note that the total perimeter $p$ of all rectangles in the partition is
$$p = 2\left(\sum_{i=1}^{M} r_{i} + \sum_{i=1}^{M} c_{i}\right).$$
No rectangle can simultaneously cover cells from row $i$ and from column $i$ since otherwise it would also cover the cell $C_{ii}$. We classify subsets $S$ of rectangles of the partition as follows. We say that $S$ is of type $i$, $1 \leq i \leq M$, if $S$ contains all $r_{i}$ rectangles that cover some cell from row $i$, but none of the $c_{i}$ rectangles that cover some cell from column $i$. Altogether there are $2^{n - r_{i} - c_{i}}$ subsets of type $i$. Now we show that no subset $S$ can be simultaneously of type $i$ and of type $j$ if $i \neq j$. Assume the contrary and let without loss of generality $i < j$. The cell $C_{ij}$ must be covered by some rectangle $R$. The subset $S$ is of type $i$, hence $R$ is contained in $S$. $S$ is of type $j$, thus $R$ does not belong to $S$, a contradiction. Since there are $2^{n}$ subsets of rectangles of the partition, we infer
$$2^{n} \geq \sum_{i=1}^{M} 2^{n - r_{i} - c_{i}} = 2^{n} \sum_{i=1}^{M} 2^{-\left(r_{i} + c_{i}\right)}$$
By applying Jensen's inequality to the convex function $f(x) = 2^{-x}$ we derive
$$\frac{1}{M} \sum_{i=1}^{M} 2^{-\left(r_{i} + c_{i}\right)} \geq 2^{-\frac{1}{M} \sum_{i=1}^{M} \left(r_{i} + c_{i}\right)} = 2^{-\frac{p}{2M}}$$
From the previous inequalities we obtain
$$1 \geq M 2^{-\frac{p}{2M}}$$
and equivalently
$$p \geq m 2^{m+1}$$