C4 NLD (Netherlands)
For an integer $m \geq 1$, we consider partitions of a $2^{m} \times 2^{m}$ chessboard into rectangles consisting of cells of the chessboard, in which each of the $2^{m}$ cells along one diagonal forms a separate rectangle of side length 1. Determine the smallest possible sum of rectangle perimeters in such a partition.
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_{i j}$ 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_{i 1}$, $i=1, \ldots, k$, form a separate rectangle. Then we may consider the boards $B_{k}=\bigcup_{1 \leq 10$, JENSEN's inequality immediately shows that the minimum of the right hand sight of (1) is attained for $i=k / 2$. Hence the total perimeter of the optimal partition of $B_{k}$ is at least $2 k+2 k / 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_{i i}$. 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_{i j}$ 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_{1}-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}{2 M}} .
$$

From (2) and (3) we obtain
$$
1 \geq M 2^{-\frac{F}{2 M}}
$$
and equivalently
$$
p \geq m 2^{m+1}
$$