IMO Problem Shortlist

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,\dots ,k\}$. Without loss of generality assume that the cells $C_{ii}$, $i=1,\dots ,k$, form a separate rectangle. Then we may consider the boards $B_k={\bigcup }_{1\le i<j\le k}{C}_{ij}$ below that diagonal and the congruent board $B_k^{\prime }={\bigcup }_{1\le j<i\le k}{C}_{ij}$ above that diagonal separately because no rectangle can simultaneously cover cells from $B_k$ and $B_k^{\prime }$. 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\ge 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\ge 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^{\prime }$ 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}\ge 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\le i\le 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\le i\le 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\ne 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\ge \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)}\ge 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\ge M{2}^{-\frac{p}{2M}}$$ and equivalently $$p\ge m{2}^{m+1}$$