\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}}

\section*{External Link}
\url{https://aops.com/community/p1932929}

\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}
