\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Shortlist 2009 C4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 23}
\maketitle
\section*{Problem}
For an integer $m\geq 1$, we consider partitions of a $2^m\times 2^m$
chessboard into rectangles consisting of cells of chessboard,
in which each of the $2^m$ cells along one diagonal
forms a separate square of side length $1$.
Determine the smallest possible sum of rectangle perimeters in such a partition.
\section*{Video}
\href{https://www.youtube.com/watch?v=yvW6wnctR-c&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/yvW6wnctR-c}}
\newpage
\section*{Solution}
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:
\begin{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.
\end{claim*}
\begin{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.
\begin{center}
\begin{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);
\end{asy}
\end{center}
If $R$ does \emph{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.
\end{proof}
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.
\end{document}