\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P46}{20(2)}{2013}

\usepackage{enumerate}

\usepackage{tikz}
   \def\tikzscale{0.8}
\usepackage{amsmath, amsfonts, amssymb, amsthm}
\usepackage{bbm}

%\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}\usepackage{textcomp}
\usepackage{boxedminipage}
\usepackage{url}

\def\Rec{\mathop{{\rm Rec}}\nolimits}
\def\dist{\mathop{{\rm dist}}\nolimits}
\def\NN{{\mathbb N}}
\def\ZZ{{\mathbb Z}}
\def\RR{{\mathbb R}}

\def\cA{{\mathcal A}}
\def\cRm{{\mathcal R}_{max}}
\def\cAm{{\mathcal A}_{max}}

\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\closure}[1]{\left\langle #1 \right\rangle}
\newcommand{\indicator}[1]{\mathbbm{1}_{\{ #1 \}}}

\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{problem}[thm]{Problem}
\newtheorem{fact}[thm]{Fact}
\newtheorem{observation}[thm]{Observation}
\newtheorem{lemma}[thm]{Lemma}

\newtheorem{claim}[thm]{Claim}
\newtheorem*{remark}{Remark}
\newtheorem{defn}{Definition}

%%If uncommented, makes text inside definition with normal font-type. If commented or removed, leaves definitions in italycs, like theorems, lemmas, etc
%\theoremstyle{definition}
\newenvironment{proofOfThm}[1]{\begin{proof}[\textit{Proof of Theorem \ref{#1}}]}{\end{proof}}

\begin{document}

\title{\bf On slowly percolating sets of minimal size\\ in bootstrap percolation}

\author{Fabricio Benevides\thanks{Supported by CNPq and FUNCAP.}\\
\small Departamento de Matem\'atica\\[-0.8ex]
\small Universidade Federal do Cear\'a\\[-0.8ex] 
\small Fortaleza, CE 60455-760, Brazil.\\
\small\tt fabricio@mat.ufc.br\\
\and
Micha{\l} Przykucki\\
\small Department of Pure Mathematics and Mathematical Statistics\\[-0.8ex]
\small University of Cambridge\\[-0.8ex] 
\small Cambridge, CB3 0WB, England, UK\\
\small\tt m.j.przykucki@dpmms.cam.ac.uk\\
}

\date{\dateline{Jul 12, 2012}{May 26, 2013}{Jun 7, 2013}\\
\small Mathematics Subject Classifications: 05D99, 60K35}

\maketitle

\begin{abstract}
Bootstrap percolation, one of the simplest cellular automata, can be seen as a model of the spread of infection. In $r$-neighbour bootstrap percolation on a graph $G$ we assign a state, infected or healthy, to every vertex of $G$ and then update these states in successive rounds, according to the following simple local update rule: infected vertices of $G$ remain infected forever and a healthy vertex becomes infected if it has at least $r$ already infected neighbours. We say that percolation occurs if eventually every vertex of $G$ becomes infected.

A well known and celebrated fact about the classical model of $2$-neighbour bootstrap percolation on the $n \times n$ square grid is that the smallest size of an initially infected set which percolates in this process is $n$. In this paper we consider the problem of finding the maximum time a $2$-neighbour bootstrap process on $[n]^2$ with $n$ initially infected vertices can take to eventually infect the entire vertex set. Answering a question posed by Bollob{\'a}s we compute the exact value for this maximum showing that, for $n \ge 4$, it is equal to the integer nearest to $(5n^2-2n)/8$.

\phantom{spacer}
\end{abstract}

\section{Introduction}
\label{sec:intro}

Bootstrap percolation is a particular type of cellular automaton, a concept studied, for example, by von Neumann~\cite{theoryautomata}. Given a graph $G$, bootstrap percolation on $G$ is a class of models that describe the spread of `infection' over the set of vertices. Before describing the model let us fix some notation. In the context of percolation, the vertices of $G$ are usually called \emph{sites} and the edges of $G$ \emph{bonds}. For each $v \in V(G)$, we denote by $N(v)$ the set of neighbours of $v$. Each site $v \in V(G)$ is in one of the two \emph{states}, say \emph{healthy} or \emph{infected}; we write $A$ for the set of sites whose initial state is `infected' and call $A$ the set of \emph{initially infected sites}.

In this paper we consider a particular family of bootstrap percolation models called \textit{$r$-neighbour bootstrap percolation}. It consists of the process defined as follows: set $A_0 = A$ and, thinking of $A_t$ as the set of sites infected at time~$t$, for $t \in \NN$ set 
\begin{equation}
\label{eq:A_t}
A_{t} = A_{t-1} \cup \{ v \in V(G) : |N(v)\cap A_{t-1}| \geq r \}.
\end{equation}
This means that sites of $G$ become infected if they have at least $r$ infected neighbours. Note that in bootstrap percolation once a site is infected it never becomes healthy.

The closure of $A\subset V(G)$ is the set $\closure{A} = \bigcup_{t=0}^{\infty} A_t$ of all sites that are eventually infected. We say that a set $A$ \textit{percolates} if all sites are eventually infected, that is, if $\closure{A} = V(G)$. Furthermore, we say that $A$ takes time $T$ to percolate if $\closure{A} = V(G)$ and $T$ is the smallest natural number such that $A_T = V(G)$.

Most work in bootstrap percolation has been focused on a particular case where, for some natural numbers~$n$ and $d$, the graph $G$ above is the $d$-dimensional grid $[n]^d$ defined as follows: the set of sites of $G$ is
\[
 V(G) = \{(i_1,i_2, \ldots, i_d): 1 \le i_j \le n \text{ for all } 1 \leq j \leq d \}
\]
and two sites $v,w \in V(G)$ are neighbours if $\|v-w\|_1 = 1$, that is, $v$ and $w$ differ in exactly one coordinate and by one unit. For $d=2$ we can represent $G=[n]^2$ by an $n$ by $n$ square-grid where each site $(i,j)$ is a unit square whose center has coordinates $(i-1/2,j-1/2)$ in the Cartesian plane. Note that two sites are adjacent if the corresponding squares share an edge. This particular model was introduced in 1979 by Chalupa, Leath and Reich~\cite{bootstrapbethe}, together with bootstrap percolation on regular trees. In this paper we consider some extremal properties of bootstrap percolation on $[n]^2$ but the first questions asked about this model were mostly of probabilistic nature. Aizenman and Lebowitz~\cite{metastabilityeffects} considered the problem where the set of initially infected sites is chosen by selecting sites independently at random with uniform probability~$p$. They tried to determine for what values of $p$ an initial set $A$ chosen this way percolates with high probability. The first sharp result was given by Holroyd~\cite{sharpmetastability} in 2003: he determined the asymptotic value of the critical probability in 2-neighbour bootstrap percolation on the square grid. Balogh, Bollob{\'a}s, Duminil-Copin and Morris \cite{sharpbootstrapall} proved the corresponding result in all dimensions $d$ and for all values of the infection threshold $r$.

Turning to extremal problems, the size of the smallest percolating sets in $[n]^d$ was studied by Pete and a summary of his results can be found in \cite{randomdisease}. However, the case $d=r=2$, which is now a famous coffee-time problem and a puzzle for high-school students, was answered very early. In this case the answer is $n$ with a diagonal of the $n \times n$ square being an obvious example of such a percolating set. This little result turned out to be very useful in proving some early probabilistic results in bootstrap percolation which motivated further research on extremal bootstrap percolation problems. Smallest percolating sets for $G=[n]^2$ and $r=2$ have also been considered by Shapiro and Stephens \cite{schrodernumbers}. A famous and still wide open problem in this area is determining the size of the smallest percolating sets for $G$ being the $d$-dimensional hypercube ($n=2$) and $r=3$.

Another family of extremal questions that have been considered, posed by Bollob{\'a}s, are those about the maximum size of minimal percolating sets, i.e., sets that percolate but no proper subsets of which do. This problem was studied by Morris~\cite{largestgridbootstrap} for $G = [n]^2$ and $r=2$ and by Riedl~\cite{largesthypercubebootstrap} for 2-neighbour bootstrap percolation on a hypercube.

In this paper we answer another question posed by Bollob{\'a}s, that of bounding the time that a percolating subset $A$ of the set of vertices of $G = [n]^2$, such that $|A|=n$, can take to percolate under $2$-neighbour bootstrap percolation. Time-related questions have recently attracted a lot of attention also in the probabilistic setup, with some sharp results obtained by Bollob{\'a}s, Holmgren, Smith and Uzzell \cite{densebootstraptime} and by Bollob{\'a}s, Smith and Uzzell \cite{densebootstraptimeall}.

For small values of $n$ it is easy to answer our question computationally by an exhaustive search. But as a main result of this paper we prove the following theorem. Let $T(A)$ denote the time that $A$ takes to percolate. Moreover, let
\[
M(n) = \max \{ T(A): \closure{A}=[n]^2 \mbox{ and } |A|=n \}.
\]
\begin{thm}
 \label{thm:minimalExact}
For every $n \geq 4$,
\begin{equation}
  \label{equation:M0exact}
  M(n) = {\bigg \lfloor} \frac{5n^2-2n}{8} {\bigg \rceil},
\end{equation}
where $\lfloor x \rceil$ denotes the integer nearest to $x$.
\end{thm}

In a forthcoming paper \cite{benevidesprzykucki01} we consider a similar problem: finding the maximum percolation time in $2$-neighbour bootstrap percolation on $[n]^2$ among all percolating sets of initially infected sites, i.e., not only those of size $n$. For that problem we determine an asymptotic answer showing that the maximum time is $\frac{13}{18}n^2+O(n)$, which is interesting as it shows that taking larger initially infected sets might extend the percolation time significantly. For $G$ being an $n$-dimensional hypercube and $r=2$ an analogous question was recently answered by Przykucki \cite{przykucki01}.

\section{Preliminaries}
\label{sec:preliminaries}
Given natural numbers $k$ and $\ell$, a $k$ by $\ell$ rectangle is a subset of $\ZZ^2$ of the form $\{a, a+1, \ldots, a+k-1\} \times \{b, b+1, \ldots, b+\ell-1\}$ for some choice of $a$ and~$b$. Let $\Rec(k, \ell)$ denote the set of all $k$ by $\ell$ rectangles in $[n]^2$. We say that a rectangle $R$ is \emph{internally spanned} by a given set of infected sites $A$ if $\closure{A\cap R} = R$.

Given a finite set $A\subset \ZZ^2$, we represent a site $(i,j) \in A$ as a shaded unit square on the grid so that its center has coordinates $(i-1/2,j-1/2)$ in $\RR^2$. We define the \emph{boundary} of $A$ as the set of bonds of $\ZZ^2$ having exactly one endpoint in $A$; in our pictures this corresponds to a side shared by a shaded and a non-shaded unit square. The \emph{perimeter} of $A$ is the number of bonds in its boundary. Its \emph{semi-perimeter} is half of the perimeter; we denote it by $\Phi(A)$. In particular, if $R \in \Rec(k, \ell)$ is a $k$ by $\ell$ rectangle then its semi-perimeter is $\Phi(R) = k+\ell$.

In our proofs we shall talk about distances between sites and rectangles. The distance we use is given by the usual $L_1$ norm, i.e., the distance between a pair of sites, say $(i_1,j_1)$ and $(i_2,j_2)$, is $|i_1 - i_2| + |j_1 - j_2|$. The distance between two rectangles $R'$ and $R''$ is the minimum distance between a site in $R'$ and a site in $R''$; it is denoted by $\dist(R', R'')$.

\begin{remark} This definition of distance coincides with the length of the shortest path from $R'$ to $R''$ when viewing $\ZZ^2$ as a graph. Note that two rectangles are at distance zero from each other if and only if they intersect; and at distance one if and only if they are disjoint but their boundaries share at least one edge.
\end{remark}

\begin{fact}\label{fact:perimeterunion}
For any two finite sets $A, B \subset \ZZ^2$ we have $\Phi(A) + \Phi(B) \ge \Phi(A\cup B)$. Equality occurs if and only if $\dist(A, B) \ge 2$, that is, if $A$ and $B$ do not intersect and have disjoint boundaries.
\end{fact}

From now on let us consider $2$-neighbour bootstrap percolation on $[n]^2$ only. Let us start with the following standard and simple observation which follows immediately from the fact that the perimeter of the infected set cannot grow when a new site becomes infected.

\begin{observation}
\label{obs:perimeters}
Let $A$ be a set of infected sites. Then $\Phi(\closure{A}) \le \Phi(A)$.
\end{observation}

\begin{cor} 
\label{cor:n_necessary}
Given $k, \ell \in \NN$ and a rectangle $R \in \Rec(k,\ell)$, if $A \subset R$ is a set that internally spans $R$ then $|A| \geq \ceil{\Phi(R)/2} = \ceil{\frac{k+\ell}{2}}$. In particular, if $n \in \NN$ and $A \subset [n]^2$  percolates, then $|A| \ge n$.
\end{cor}
It is easy to show that the lower bounds in Corollary \ref{cor:n_necessary} are sharp. For example, a diagonal is a percolating set of size $n$ in $[n]^2$.

As we mentioned before, we are interested in finding sets of size $n$ in $[n]^2$ that do percolate but do so in the maximum possible time $M(n)$. To do this we build a family of sets that percolate in a particular way. In order to do so we shall need to use induction on the size of the underlying graph. Hence it is natural to extend the definition of $M(n)$ to percolation on rectangles.

Given natural numbers $k$ and $\ell$ such that $k+\ell$ is even (the reason why we only look at even values of $k+\ell$ will become clear in our proof) let $T(A)$ again denote the time that $A$ takes to percolate. We define $M(k,\ell)$ by
\[
M(k,\ell) = \max \{ T(A): \closure{A}=[k] \times [\ell] \mbox{ and } |A|=(k+\ell)/2 \}.
\]
For a rectangle $R \in \Rec(k,\ell)$ define $M(R)$ to be the maximum time in which some set of order $\Phi(R)/2$ internally spans $R$. Of course, $M(R)$ is just another notation for $M(k,\ell)$.

Before trying to compute bounds on $M(n)$ we should also understand how the infection spreads on a broader scale. The first simple but important observation is the following.

\begin{fact}
Given any set $A$ of infected sites, $\closure{A}$ is a union of rectangles such that any distinct two of them are at distance at least $3$.
\end{fact}

This fact clearly follows from the following argument. The set $A$ can be viewed as a union of $1$~by~$1$ rectangles and any two fully infected rectangles within distance at most $2$ do span a larger rectangle containing both. The next proposition from Holroyd~\cite{sharpmetastability} is a much more precise result in this direction.

\begin{prop}\label{prop:rectangles}
Let $R$ be a rectangle with area at least $2$. Suppose that $R$ is internally spanned by a set of sites $A$. Then there exist disjoint subsets of $A$, say $A'$ and $A''$, and rectangles $R'$ and $R''$ such that:
\begin{enumerate}
\item \label{prop:rectangles:c1} $R'\subsetneq R$ and $R'' \subsetneq R$,
\item \label{prop:rectangles:c2} $R'$ is internally spanned by sites in $A'$ and $R''$ is internally spanned by sites in~$A''$,
\item \label{prop:rectangles:c3} $\closure{R'\cup R''} = R$; in particular, $\dist(R', R'') \le 2$.
\end{enumerate}
\end{prop}

\begin{remark} Note that in Proposition~\ref{prop:rectangles} we cannot require the rectangles $R'$ and $R''$ to be disjoint (see Figure~\ref{figure:overlap}).
\end{remark}

\begin{figure}[ht]
  \centering
  \begin{tikzpicture}[scale=\tikzscale]
    \fill[color=lightgray] (0,3.5) rectangle +(0.5,0.5);
    \fill[color=lightgray] (0.5,3) rectangle +(0.5,0.5);
    \fill[color=lightgray] (1,2.5) rectangle +(0.5,0.5);
    \fill[color=lightgray] (1.5,5) rectangle +(0.5,0.5);
    \fill[color=lightgray] (2,4.5) rectangle +(0.5,0.5);
    \fill[color=lightgray] (2.5,4) rectangle +(0.5,0.5);
    \fill[color=lightgray] (2.5,1) rectangle +(0.5,0.5);
    \fill[color=lightgray] (3,0.5) rectangle +(0.5,0.5);
    \fill[color=lightgray] (3.5,0) rectangle +(0.5,0.5);
    \fill[color=lightgray] (4,2.5) rectangle +(0.5,0.5);
    \fill[color=lightgray] (4.5,2) rectangle +(0.5,0.5);
    \fill[color=lightgray] (5,1.5) rectangle +(0.5,0.5);

    \draw[step=.5cm,gray,thick]
    (0,0) grid (5.5,5.5);
    \draw[line width=1mm,black,dashed]
    (0,5.5) -- (3,5.5) -- (3,2.5) -- (0,2.5) -- (0,5.5);
    \draw[line width=1mm,black,dashed]
    (2.5,3) -- (5.5,3) -- (5.5,0) -- (2.5,0) -- (2.5,3);
    \draw[black] (-0.25,4) node [left] {$R'$};
    \draw[black] (5.75,1.5) node [right] {$R''$};
  \end{tikzpicture}
  \caption{An example where rectangles $R'$ and $R''$ are uniquely determined by the initially infected sites and do overlap.}
  \label{figure:overlap}
\end{figure}

\begin{remark}
Although Proposition~\ref{prop:rectangles} is sharp, it does not describe the percolation process in a step by step fashion (i.e., as the time $t$ increases by one). In fact, it may happen that some sites in $R \setminus (R'\cup R'')$ become infected while some of $R'\cup R''$ are still healthy. Even though the problem we study is intrinsically time related, we shall be able to make heavy use of Proposition~\ref{prop:rectangles}.
\end{remark}

\section[Slowly percolating sets]{Slowly percolating sets with the minimal number of sites}
\label{section:minimal}
In this section our aim is to compute the exact value of $M(n)$ for every $n \in \NN$. Let us start by giving some intuitions about the solution to this problem. First, we clearly have $M(n) \leq n^2-n$, since at each time step we need to infect at least one of the initially healthy sites to continue the process. Also, without too much effort one can show that $M(n) \geq \frac{n^2}{2}+O(n)$. For example, consider the set of initially infected sites of the $[7]^2$ grid in Figure~\ref{figure:n^2/2}, which generalizes in a self-explanatory way to the $[n]^2$ grid. It is clear that with this particular starting set at each time step, except the first one, at most two new sites become infected.

\begin{figure}[ht]
  \centering
    \begin{tikzpicture}[scale=\tikzscale]
      \foreach \x/\y in {0/0, 1/0, 2/0, 3/0, 0/1, 3/2, 0/3}
      \fill[color=lightgray]  (\x,\y) rectangle +(0.5,0.5);
      \draw[black] (0.75,0.25) node {1};
      \draw[black] (1.75,0.25) node {1};
      \draw[black] (2.75,0.25) node {1};

      \draw[step=.5cm,gray,thick]
      (0,0) grid (3.5,3.5);
      \draw[->] (0.25,0.75) -- (3.25,0.75);
      \draw[->] (0.75,0.75) -- (0.75,1.25) -- (3.25,1.25) -- (3.25,1.75) -- (0.25,1.75);
      \draw[->] (2.75,1.75) -- (2.75,2.25) -- (0.25,2.25) -- (0.25,2.75) -- (3.25,2.75);
      \draw[->] (0.75,2.75) -- (0.75,3.25) -- (3.25,3.25);
    \end{tikzpicture}
  \caption{An initial set showing that $M(n) \geq \frac{n^2}{2}+O(n)$.}
  \label{figure:n^2/2}
\end{figure}

This shows that $M(n) = \Theta(n^2)$. As a main result of this paper we prove that the structure of sets maximizing percolation time is actually more sophisticated. To be more precise, we show that to infect a $k \times \ell$ rectangle $R$ in the maximum time we should use an initially infected set $A = A' \cup \{v\}$ such that the set $A'$ first internally spans either a $(k-1) \times (\ell-1)$, $(k-2) \times \ell$ or $k \times (\ell-2)$ rectangle in the maximum possible time, and then using 'help' from the site $v$ finishes the infection of $R$. As a consequence, when $k = \ell = n$, the structure of a set $A(n)$ with $|A(n)| = n$ maximizing percolation time can be described as follows. We have $A(n) = B(n) \cup C(n) \cup D(n)$, where $|B(n)| \approx n/4$, $|C(n)| \approx n/2$ and $|D(n)| \approx n/4$, and such that
\begin{enumerate}
 \item Set $B(n)$ internally spans a rectangle of size roughly $\frac{n}{2} \times 2$ in time $\frac{3n}{4} + O(1)$,
 \item Set $C(n)$ extends the infected area to a rectangle of size roughly $n \times \frac{n}{2}$ in time $\frac{3n^2}{8} + O(n)$,
 \item Set $D(n)$ finishes the infection of the $n \times n$ grid in time $\frac{n^2}{4} + O(n)$.
\end{enumerate}
Thus the set $A(n)$ percolates in time $5n^2/8 + O(n)$, significantly beating the simple construction presented in Figure~\ref{figure:n^2/2}.

Now, let us return to Proposition~\ref{prop:rectangles}. Given $A \subset [n]^2$, consider the sets $A'$, $A''$, $R'$ and $R''$, given by Proposition~\ref{prop:rectangles}, and assume that $A'$ takes at least as many time steps to internally span $R'$ as $A''$ takes to internally span $R''$. Then clearly we can bound from above the time that $A$ takes to percolate $R$ by the time $A'$ takes to infect $R'$ plus the time to grow from $R' \cup R''$ to $R$, that is, to infect all sites in $R \setminus (R' \cup R'')$ given that all sites in $R'$ and $R''$ are infected. Intuitively, the time to grow from $R' \cup R''$ to $R$ does not change much if we only slightly change the sizes of $R'$ and $R''$ while the infection time of $R'$ might grow a lot if we increase the side lengths of $R'$ even by some small quantities (this follows from our intuitions about the quadratic growth of $M$). It is then intuitive that, to maximize the time that $A$ takes to percolate, $R''$ should probably be as small as possible, maybe even a single site. Let us now make our arguments formal.

First, we consider a family of sets of initially infected sites that internally span a rectangle in a particular way. The following definition is the most important concept of this paper.
\begin{defn}\label{defn:goodset}
Let $k$ and $\ell$, with $k+\ell$ even, be given natural numbers. We say that a set $A$ of initially infected sites is \emph{$(k,\ell)$-good} if it has cardinality $(k+\ell)/2$ and the $2$-neighbour bootstrap percolation process starting from $A$ can be described as follows. There exists a nested sequence of rectangles $P_0 \subset P_1 \subset \ldots \subset P_r \in \Rec(k,\ell)$, such that $P_i \in \Rec(s_i, t_i)$ where $s_i, t_i$ satisfy the following properties:
\begin{enumerate}
  \item \label{Ra} either $s_0 \le 2$ or $t_0 \le 2$ or $s_0 = t_0 = 3$; and $s_1, t_1 \geq 3$ and $(s_1, t_1) \neq (3,3)$,
  \item \label{Rb} for every $1 \le i\le r$, the rectangle $P_i$ is in 
\[
 \Rec(s_{i-1}+1,t_{i-1}+1) \cup \Rec(s_{i-1}+2,t_i) \cup \Rec(s_i,t_{i-1}+2),
\]
  \item \label{Rc} for all $0 \le i \le r$, the rectangles $P_i$ are internally spanned by $A \cap P_i$ in the maximal possible time, that is, in time $M(P_i)$,
  \item \label{Rd} for every $0 \le i \le r$, if the rectangle $P_i$ has no side of length $1$ then among the sites which become infected last in $P_i$ there is at least one of its corner sites,
  \item \label{Re} for every $0 \le i < r$, there exists a site $v_i \in A$ such that $P_{i} \cup \{v_i\}$ internally spans $P_{i+1}$ and $v_i$ is at distance exactly 2 from one of the last sites to become infected in $P_{i}$ and at distance at least 3 from any other site in $P_{i}$ (see Figure~\ref{figure:Moves123}).
\end{enumerate}
\end{defn}
\begin{defn}
 If $A$ is $(k,\ell)$-good we say that $P_0 \subset P_1 \subset \ldots \subset P_r \in \Rec(k,\ell)$ is a \emph{good sequence} of rectangles associated with $A$ if it satisfies conditions (\ref{Ra})-(\ref{Re}) above.
\end{defn}
From condition (\ref{Rb}) it follows that for every $0 \le i \le r-1$ we have $\Phi(R_{i+1}) = \Phi(R_{i}) + 2$. From condition \eqref{Rc}, taking $i=r$, it follows that any $(k,\ell)$-good set infects a $k \times \ell$ rectangle in the maximum possible time. We shall show that for every $n \geq 4$ there exists an $(n,n)$-good set $A$.

For a $(k,\ell)$-good set $A \subset [k] \times [\ell]$ and a good sequence $P_0 \subset P_1 \subset \ldots \subset P_r = [k] \times [\ell]$ associated with it, we say that we use \emph{Move $1$} at moment $i$ (to construct $P_{i}$ from $P_{i-1}$) if $P_{i} \in \Rec(s_{i-1}+1, t_{i-1}+1)$, that we use \emph{Move $2$} at moment $i$ if $P_{i} \in \Rec(s_{i-1}+2, t_{i-1})$ and that we use \emph{Move $3$} at moment $i$ if $P_{i} \in \Rec(s_{i-1}, t_{i-1}+2)$.

\begin{figure}[ht]
  \centering
  \begin{minipage}[b]{0.4\linewidth}
    \centering
    \begin{tikzpicture}[scale=\tikzscale]
      \fill[color=lightgray]  (3.5,2.5) rectangle +(0.5,0.5);
      \fill[color=lightgray]  (0,0) rectangle (3.5,2);
      \fill[color=lightgray]  (0,2) rectangle (3,2.5);

      \draw[step=.5cm,gray,thick]
      (0,0) grid (4,3);
      \draw[line width=1mm,black,dashed]
      (0,0) -- (0,2.5) -- (3.5,2.5) -- (3.5,0) -- (0,0);
      \draw[->] (3.75,2.25) -- (3.75,0.25);
      \draw[->] (3.25,2.75) -- (0.25,2.75);
      \draw[black] (-0.25,1.25) node [left] {$t_{i-1}$};
      \draw[black] (1.75, -0.85) node [above] {$s_{i-1}$};
      \draw[black] (2,-0.75) node [below] {Move $1$ at moment $i$};
    \end{tikzpicture}
  \end{minipage}
  \hspace{0.5cm}
  \begin{minipage}[b]{0.4\linewidth}
    \centering
    \begin{tikzpicture}[scale=\tikzscale]
      \fill[color=lightgray]  (3.5,2.5) rectangle +(0.5,0.5);
      \fill[color=lightgray]  (0,0) rectangle (3,2.5);
      \fill[color=lightgray]  (0,2.5) rectangle (2.5,3);

      \draw[step=.5cm,gray,thick]
      (0,0) grid (4,3);
      \draw[line width=1mm,black,dashed]
      (0,0) -- (0,3) -- (3,3) -- (3,0) -- (0,0);
      \draw[->] (3.75,2.25) -- (3.75,0.25);
      \draw[->] (3.25,1.75) -- (3.25,0.25);
      \draw[black] (-0.25,1.5) node [left] {$t_{i-1}$};
      \draw[black] (4.25,1.5) node [right] {};
      \draw[black] (1.5,-0.85) node [above] {$s_{i-1}$};
      \draw[black] (3.25,2.75) node {1};
      \draw[black] (3.25,2.25) node {2};
      \draw[black] (2,-0.75) node [below] {Move $2$ at moment $i$};
    \end{tikzpicture}
  \end{minipage}
  \centering
    \begin{tikzpicture}[scale=\tikzscale]
      \fill[color=lightgray]  (3.5,2.5) rectangle +(0.5,0.5);
      \fill[color=lightgray]  (0,0) rectangle (3.5,2);
      \fill[color=lightgray]  (3.5,0) rectangle (4,1.5);

      \draw[step=.5cm,gray,thick]
      (0,0) grid (4,3);
      \draw[line width=1mm,black,dashed]
      (0,0) -- (0,2) -- (4,2) -- (4,0) -- (0,0);
      \draw[->] (3.25,2.75) -- (0.25,2.75);
      \draw[->] (2.75,2.25) -- (0.25,2.25);
      \draw[black] (-0.25,1) node [left] {$t_{i-1}$};
      \draw[black] (4.25,1.5) node [right] {};
      \draw[black] (2,-0.85) node [above] {$s_{i-1}$};
      \draw[black] (3.75,2.25) node {1};
      \draw[black] (3.25,2.25) node {2};
      \draw[black] (2,-0.75) node [below] {Move $3$ at moment $i$};
    \end{tikzpicture}
  \caption{Moves $1$, $2$ and $3$.}
  \label{figure:Moves123}
\end{figure}

We shall prove a recursive formula for $M(k,\ell)$ that works for all values of $k$ and $\ell$ such that $k+\ell$ is even. The reader should keep in mind the description of $(k,\ell)$-good initial sets as we are going to build such a set in our proof. In the next two lemmas we deal with some small cases which we will later use as base cases for the recursion. Since $M(k, \ell) = M(\ell, k)$, we shall omit some cases where $k < \ell$. 

\begin{lemma}\label{lemma:smallCases}
 We have $M(1,1) = 0$; $M(k, 1) = 1$ for all odd $k \ge 3$; and $M(3, 3) = 4$. Furthermore, in all these cases there exist $(k,\ell)$-good sets.
\end{lemma}
\begin{proof}
 The proof of this lemma is easy and we leave it as an exercise to the reader.
\end{proof}

\begin{lemma}\label{lemma:kequals2}
For any even $k$ we have $M(k,2) = (3k-4)/2$. Furthermore, there is a $(k,2)$-good set, $A^0(k,2)$, which percolates $[k] \times [2]$ in time $M(k,2)$.
\end{lemma}
\begin{proof}
We define $A^0(k,2)$ to be the set of shaded sites in Figure~\ref{figure:2k}. Clearly $|A^0(k,2)|= (k+2)/2$ and $A^0(k,2)$ percolates $[k] \times [2]$ in time $(3k-4)/2$. Thus we have $M(k, 2) \ge (3k-4)/2$ for any $k$ even. Note that, setting $P_0 = [k] \times [2]$, to prove that $A^0(k,2)$ is a $(k,2)$-good set we only need to show that in fact $M(k, 2) = (3k-4)/2$.
\begin{figure}[ht]
  \centering
  \begin{tikzpicture}[scale=\tikzscale]

    \fill[color=lightgray]  (0,0) rectangle + (0.5,0.5);
    \fill[color=lightgray]  (0.5,0.5) rectangle (1,1);
    \fill[color=lightgray]  (1.5,0) rectangle (2,0.5);
    \fill[color=lightgray]  (2.5,0.5) rectangle (3,1);
    \fill[color=lightgray]  (4.5,0) rectangle (5,0.5);
    \fill[color=lightgray]  (5.5,0.5) rectangle (6,1);

    \draw[step=.5cm,gray,thick]
    (0,0) grid (6,1);

    \draw[->] (1.25,0.25) -- (1.25,0.75) -- (1.75,0.75) -- (2.25,0.75) -- (2.25,0.25) -- (2.75,0.25);
    \draw[->] (4.25,0.25) -- (4.25,0.75) -- (4.75,0.75) -- (5.25,0.75) -- (5.25,0.25) -- (5.75,0.25);
    \draw[black] (0.25,0.75) node {1};
    \draw[black] (0.75,0.25) node {1};
    \draw[black] (3.5,0.75) node {\ldots};
    \draw[black] (3.5,0.25) node {\ldots\ldots};
    \draw[black] (4.25,1.5) node [right] {};
    \draw[black] (3,-0.25) node [below] {$k$};
  \end{tikzpicture}
  \caption{A set of initially infected sites which gives the maximum percolation time on $[k] \times [2]$ when $k$ is even.}
  \label{figure:2k}
\end{figure}

Now we prove by induction on $k$ that for any $k$ even we have $M(k,2) \le (3k-4)/2$. Clearly, ${M(2, 2) = 1}$. Assume that we are given some even $k \ge 4$ and that $M(k-2,2) = (3k-10)/2$. Let $A$, with $|A|= (k+2)/2$, be any set that percolates $[k] \times [2]$.

Since $A$ percolates, any two consecutive columns of $[k]\times [2]$ contain at least one site of $A$. In particular, each of the $2$ by $2$ squares of the form $\{2i-1, 2i\}\times\{1,2\}$, $1\le i \le k/2$, must contain at least one site of $A$. So only one of such squares can contain two sites of $A$. Therefore, either $\{1,2\}\times\{1, 2\}$ or $\{k-1, k\} \times \{1,2\}$ contains exactly one site of $A$. Assume without loss of generality that the latter holds. Since $A$ percolates, either $(k,1)$ or $(k,2)$ must be an initially infected site. Again without loss of generality we may assume that the latter holds. In this setting it is trivial to check that $A$ must internally span $[k-2]\times [2]$. Therefore $A$ takes time at most $M(k-2,2) + 3 = (3k-4)/2$ to percolate. This completes the proof.
\end{proof}

Now, we state a lemma giving a recursive formula for $M(k, \ell)$. Let us note that in the formula we are about to prove the sum of the parameters that the function $M(\cdot,\cdot)$ depends on at each recursive step decreases by two. This is why, being interested in the value of $M(n,n)$, we only need to look at values of $k$ and $\ell$ with even $k+\ell$. 

\begin{lemma}
\label{lemma:M0recurrence}
For $k, \ell \ge 3$ such that $(k, \ell) \neq (3,3)$ and $k+\ell$ is even, we have
\begin{equation}
\label{equation:M0recurrence}
M(k,\ell) = \max
  \begin{cases}
    M(k-1,\ell-1) + \max\{k, \ell\}-1,\\
    M(k-2, \ell) + \ell+1,\\
    M(k,\ell-2) + k+1.
  \end{cases}
\end{equation}
Furthermore, for all such $k$ and $\ell$ there exists a $(k,\ell)$-good set.
\end{lemma}
\begin{proof} We prove Lemma~\ref{lemma:M0recurrence} by induction on $k + \ell$. Assume that we are given $k, \ell \ge 3$ such that $(k, \ell) \neq (3,3)$ and $k + \ell$ is even. Our induction hypothesis is that for any $k', \ell'$ such that $k'+\ell'$ is even and $k'+\ell' < k+\ell$ there exists a $(k',\ell')$-good set $A^0(k', \ell')$ which percolates in time $M(k', \ell')$, as in the statement of Lemma~\ref{lemma:M0recurrence}.

The fact that $k, \ell \ge 3$ guarantees that we have $k-1, \ell -1 \geq 2$. This will be important for us as in the constructions below we shall use property \eqref{Rd} of Definition \ref{defn:goodset} of $(k,\ell)$-good sets a lot. We shall first prove that the following inequality holds for $k$ and $\ell$ as above.
\begin{equation}
\label{equation:M0geq}
M(k,\ell) \geq \max
  \begin{cases}
    M(k-1,\ell-1) + \max\{k, \ell\}-1,\\
    M(k-2, \ell) + \ell+1,\\
    M(k,\ell-2) + k+1.
  \end{cases}
\end{equation}

Consider the following three particular ways of infecting $[k] \times [\ell]$ (see Figure~\ref{figure:Moves123}).

\begin{enumerate}\renewcommand*\theenumi{\alph{enumi}}
  \item \label{option:1} By the induction hypothesis there exists a $(k-1,\ell-1)$-good set $A^0(k-1, \ell -1)$ which internally spans the rectangle $[k-1]\times [\ell-1]$ in time $M(k-1, \ell -1)$. Without loss of generality, since $k-1, \ell -1 \geq 2$, we may assume that the site $(k-1,\ell-1)$ becomes infected at time $M(k-1,\ell-1)$. Let $A_1(k,\ell) = A^0(k-1, \ell -1) \cup \{(k, \ell)\}$. Then the infection of sites in $([k]\times [\ell]) \setminus ([k-1]\times [\ell-1])$ starts only after $(k-1,\ell-1)$ is infected and so $A_1(k,\ell)$ takes time $M(k-1,\ell-1) + \max\{k,\ell\} - 1$ to internally span $[k]\times [\ell]$. In addition, note that at least one of the corner sites $(k,1),(1,\ell)$ becomes infected at time $M(k-1,\ell-1) + \max\{k,\ell\} - 1$.

  \item \label{option:2} When $k \ge 4$, by the induction hypothesis there exists a $(k-2,\ell)$-good set $A^0(k-2, \ell)$, internally spanning the rectangle $[k-2] \times [\ell]$ in time $M(k-2, \ell)$, which infects the site $(k-2,\ell)$ at time $M(k-2,\ell)$ (this follows from the fact that $k-2, \ell \geq 2$). Let $A_2(k,\ell) = A^0(k-2, \ell) \cup \{(k, \ell)\}$. Then the infection of sites in $([k]\times [\ell]) \setminus ([k-2]\times [\ell])$ starts only after $(k-2,\ell)$ is infected and so $A_2(k,\ell)$ takes time $M(k-2,\ell) + \ell + 1$ to internally span $[k]\times [\ell]$. In addition, note that the corner site $(k,1)$ becomes infected at time $M(k-2,\ell) + \ell + 1$.

  \item \label{option:3} When $\ell \ge 4$, analogously to case \ref{option:2}), by the induction hypothesis there exists a $(k,\ell-2)$-good set $A^0(k, \ell-2)$, internally spanning the rectangle $[k] \times [\ell-2]$ in time $M(k, \ell-2)$, which infects the site $(k,\ell-2)$ at time $M(k,\ell-2)$. Then the set $A_3(k,\ell) = A^0(k, \ell-2) \cup \{(k, \ell)\}$ internally spans $[k]\times [\ell]$ in time $M(k, \ell-2) + k+1$, with the corner site $(1,\ell)$ becoming infected at the last time step.
\end{enumerate}

The above constructions show that inequality~\eqref{equation:M0geq} holds when $k, \ell \ge 4$. It remains to check that it also holds for $k =3$ and $\ell \ge 5$, and for $\ell =3$ and $k \ge 5$ (recall that $k+\ell$ is even so, e.g., when $k = 3$ we have $\ell \neq 4$). These cases are clearly symmetric so let us just show that $M(k,3) \geq M(k,1) + k + 1$ for $k \geq 5$. This is immediate as $M(k,1)+k+1 = k+2$ and we already know that
\[
 M(k,3) \geq M(k-1,2)+k-1 \geq M(4,2) + k-1 \geq k+3.
\]
Thus the lower bound on $M(k,\ell)$ is proved.

Let us now show that the set $A_1(k,\ell)$ defined above satisfies all but possibly condition \eqref{Rc} of a $(k,\ell)$-good set. Showing that the same holds for the sets $A_2(k,\ell)$ and $A_3(k,\ell)$ is analogous.

Thus, assume that $A^0(k-1, \ell -1)$ is a $(k-1,\ell-1)$-good set with a good sequence of rectangles $P_0 \subset P_1 \subset \ldots \subset P_r = [k-1] \times [\ell-1]$ associated with it. First, clearly $|A_1(k,\ell)| = |A^0(k-1, \ell -1)| + 1 = (k+\ell-2)/2+1 = (k+\ell)/2$. Now consider the sequence $P_0 \subset P_1 \subset \ldots \subset P_r = [k-1] \times [\ell-1] \subset P_{r+1} = [k] \times [\ell]$ which describes the infection of $[k] \times [\ell]$ with $A_1(k,\ell)$ as the set of initially infected sites. This sequence clearly satisfies properties \eqref{Ra} and \eqref{Rb} of $(k,\ell)$-good sets since it is obtained from a $(k-1,\ell-1)$-good set. It satisfies property \eqref{Rd} for $i=r+1$ since, as we noticed, in the infection started from $A_1(k,\ell)$ at least one of the corner sites $(k,1),(1,\ell)$ becomes infected at the last time step. It satisfies property \eqref{Re} for $i=r+1$ since $(k,\ell)$ is at distance $2$ from $(k-1, \ell-1)$ (which is infected last) and at distance at least $3$ from any other site in $P_r = [k-1] \times [\ell-1]$. Properties \eqref{Rd} and \eqref{Re} for $i \leq r$ are satisfied for this sequence since it is obtained from one associated with a $(k-1,\ell-1)$-good set.

We shall show that at least one of the sets $A_1(k,\ell)$, $A_2(k,\ell)$ and $A_3(k,\ell)$ is $(k,\ell)$-good by proving an upper bound on $M(k,\ell)$ analogous to inequality~\eqref{equation:M0geq}, that is, 
\begin{equation}
\label{equation:M0gequpper}
M(k,\ell) \leq \max
  \begin{cases}
    M(k-1,\ell-1) + \max\{k, \ell\}-1,\\
    M(k-2, \ell) + \ell+1,\\
    M(k,\ell-2) + k+1.
  \end{cases}
\end{equation}
This will mean that at least one of these sets satisfies the missing property \eqref{Rc} of a $(k,\ell)$-good set.

Consider any set $A$ which internally spans the rectangle $R = [k] \times [\ell]$ in time $M(k, \ell)$ and is such that $|A| = (k+\ell)/2$. By Proposition~\ref{prop:rectangles}, there exist disjoint subsets of $A$, say $A'$ and $A''$, and two rectangles $R'$ and $R''$ satisfying conditions (\ref{prop:rectangles:c1})--(\ref{prop:rectangles:c3}) of Proposition~\ref{prop:rectangles}. By Proposition~\ref{obs:perimeters} and condition~(\ref{prop:rectangles:c3}) of Proposition~\ref{prop:rectangles}, we have that
$$
 \Phi(R'\cup R'') \ge \Phi(\closure{R'\cup R''}) = \Phi(R) = k+\ell.
 $$
By Fact~\ref{fact:perimeterunion}, condition~(\ref{prop:rectangles:c2}) of Proposition~\ref{prop:rectangles} and Corollary~\ref{cor:n_necessary}, 
$$
  \Phi(R'\cup R'') \le \Phi(R') + \Phi(R'') \le 2|A'| + 2|A''| \le 2|A| = k+\ell.
$$

Therefore, each of the above inequalities must be an equality. In particular, we have \mbox{$\Phi(R'\cup R'') = \Phi(R') + \Phi(R'')$}. Fact~\ref{fact:perimeterunion} implies that $\dist(R', R'') \ge 2$, which together with condition~(\ref{prop:rectangles:c3}) of Proposition~\ref{prop:rectangles} gives that $R'$ and $R''$ must be at distance exactly 2. Also, we must have $\Phi(R') = 2|A'|$ and $\Phi(R'') = 2|A''|$, therefore, both $\Phi(R')$ and $\Phi(R'')$ are even.

Let $s_1, t_1, s_2, t_2 \geq 1$ be such that $R' \in \Rec(s_1, t_1)$ and $R'' \in \Rec(s_2, t_2)$.  We have $\Phi(R') + \Phi(R'') = \Phi(R)$, so $s_1 + s_2 + t_1 + t_2 = k+ \ell$. Since $R'$ and $R''$ must be at distance exactly 2, the values of $s_1, t_1, s_2, t_2$ and the positions of $R'$ and $R''$ inside $R$, must satisfy exactly one of the following conditions (to avoid redundancy we do not list cases analogous to Conditions (\ref{item:CondA}), (\ref{item:CondB}) and (\ref{item:CondC}) when the alignment of $R'$ and $R''$ in $R$ is a rotation by 90 degrees of the one we consider here).

\begin{enumerate}[{Condition} (a):]
  \item \label{item:CondA} rectangles $R'$ and $R''$ align like in Figure~\ref{figure:Cond}~(a) with $s_1 + s_2 = k-1$ and $t_1 + t_2 = \ell+1$.
  \item \label{item:CondB} rectangles $R'$ and $R''$ align like in Figure~\ref{figure:Cond}~(b) with $s_1 + s_2 = k$, $t_1 + t_2 = \ell$.
  \item \label{item:CondC} there is an $0 \leq m \leq t_1-t_2$ so that the rectangles $R'$ and $R''$ align as in Figure \ref{figure:Cond}~(c) with $s_1 + s_2 = k-1$, $t_1 = \ell$ and $t_2 = 1$.
\end{enumerate}
\begin{figure}[ht]
  \centering
  \begin{minipage}[b]{0.4\linewidth}
    \centering
    \begin{tikzpicture}[scale=\tikzscale]
      \draw[step=.5cm,gray,thick]
      (0,0) grid (4,3);
      \draw[line width=1mm,black,dashed]
      (0,1.5) -- (0,3) -- (2.5,3) -- (2.5,1.5) -- (0,1.5);
      \draw[line width=1mm,black,dashed]
      (3,0) -- (3,2) -- (4,2) -- (4,0) -- (3,0);
      \draw[black] (-0.25,2.25) node [left] {$t_1$};
      \draw[black] (4.25,1) node [right] {$t_2$};
      \draw[black] (1.25,3.25) node [above] {$s_1$};
      \draw[black] (3.5,-0.25) node [below] {$s_2$};
      \draw[black] (2,-0.75) node [below] {(\ref{item:CondA})};
    \end{tikzpicture}
    \end{minipage}
  \hspace{0.5cm}
  \begin{minipage}[b]{0.4\linewidth}
    \centering
    \begin{tikzpicture}[scale=\tikzscale]
      \draw[step=.5cm,gray,thick]
      (0,0) grid (4,3);
      \draw[line width=1mm,black,dashed]
      (0,1.5) -- (0,3) -- (2.5,3) -- (2.5,1.5) -- (0,1.5);
      \draw[line width=1mm,black,dashed]
      (2.5,0) -- (2.5,1.5) -- (4,1.5) -- (4,0) -- (2.5,0);
      \draw[black] (-0.25,2.25) node [left] {$t_1$};
      \draw[black] (4.25,0.75) node [right] {$t_2$};
      \draw[black] (1.25,3.25) node [above] {$s_1$};
      \draw[black] (3.25,-0.25) node [below] {$s_2$};
      \draw[black] (2,-0.75) node [below] {(\ref{item:CondB})};
    \end{tikzpicture}
  \end{minipage}
  \centering
  \begin{tikzpicture}[scale=\tikzscale]
    \draw[step=.5cm,gray,thick]
    (0,0) grid (4,3);
    \draw[line width=1mm,black,dashed]
    (0,0) -- (0,3) -- (2,3) -- (2,0) -- (0,0);
    \draw[line width=1mm,black,dashed]
    (2.5,0.5) -- (2.5,1) -- (4,1) -- (4,0.5) -- (2.5,0.5);
    \draw[black] (-0.25,1.5) node [left] {$t_1$};
    \draw[black] (4.25,0.75) node [right] {$t_2=1$};
    \draw [|-|, black] (4.25,1)  -- (4.25,3)
         node [black,midway,right=4pt] {$m$};
    \draw[black] (1,3.25) node [above] {$s_1$};
    \draw[black] (3.25,-0.25) node [below] {$s_2$};
    \draw[black] (2,-0.75) node [below] {(\ref{item:CondC})};
  \end{tikzpicture}
  \caption{Three possible alignments of rectangles $R'$ and $R''$.}
  \label{figure:Cond}
\end{figure}

Additionally, the rectangles $R'$ and $R''$ are nonempty and internally spanned by $\frac{s_1+t_1}{2}$ and $\frac{s_2+t_2}{2}$ sites respectively.

Note now that no matter which of the Conditions (\ref{item:CondA}), (\ref{item:CondB}) or (\ref{item:CondC}) holds, if at least one of $s_1, t_1, s_2, t_2$ equals $1$ (which for Condition (\ref{item:CondC}) is true by definition with $t_2 = 1$) then, just by possibly moving sites from $A'$ to $A''$ or the other way, we can find a partition of $A$, say into sets $\tilde{A}'$ and $\tilde{A}''$, such that $\closure{\tilde{A}'} = \tilde{R}'$ is a rectangle, $\closure{\tilde{A}''} = \tilde{R}''$ is a single site and $\closure{\tilde{R}' \cup \tilde{R}''} = R$. Now, returning to the intuitions we gave at the beginning of this section, we can bound from above the time that $A$ takes to percolate $[k]\times [\ell]$ by the larger of the maximal times needed to internally span $R'$ or $R''$, plus the time to grow from $R' \cup R''$ to $R$, that is, to infect all sites in $R \setminus (R' \cup R'')$ given that all sites in $R'$ and $R''$ are infected. So if such $\tilde{R}''$ consisting of a single site can be found then the percolation time clearly cannot be greater than the lower bound given by inequality~\eqref{equation:M0geq}, in which case we are done. Assume therefore this is not the case which allows us to ignore Condition (\ref{item:CondC}). Thus we only need to consider Conditions (\ref{item:CondA}) and (\ref{item:CondB}) with $s_1, t_1, s_2, t_2 \geq 2$. For these Conditions we are also free to assume that $M(R') \geq M(R'')$.

Therefore, the time $A$ takes to percolate is at most
\begin{equation}\label{eq:TplusMax}
  \begin{cases}
    M(s_1, t_1) + \max\{s_1+t_2, s_2+t_1\},     & \text{if Condition (\ref{item:CondA}) holds,} \\
    M(s_1, t_1) + \max\{s_1+t_2-1, s_2+t_1-1\}, & \text{if Condition (\ref{item:CondB}) holds.}
  \end{cases}
\end{equation}

From \eqref{equation:M0geq} and small case analysis when $s$ or $t$ equals 2, we have that the bound $M(s,t) \geq M(s-1,t-1) + \max\{s, t\}-1$ holds for all $2 \leq s \leq k$, $2 \leq t \leq \ell$, $s+t$ even. Also, $M(\cdot,\cdot)$ is clearly non-decreasing in both parameters.

If Condition (\ref{item:CondA}) holds then since $s_1, t_1, s_2, t_2 \geq 2$ we also have $s_1, s_2 \leq k-3$ and $t_1, t_2 \leq \ell-1$. Then
\[
\begin{split}
 M(s_1, t_1) + \max\{s_1+t_2, s_2+t_1\} & \leq M(k-3, \ell-1) + k+\ell-4 \\ 
& \leq M(k-2, \ell) + k+\ell-4 - (\max\{k-2,\ell\}-1) \\
& \leq M(k-2, \ell) + \min\{\ell-1,k-3\} \\
& < M(k-2, \ell) + \ell + 1.
\end{split}
\]
In case the rectangles $R'$ and $R''$ satisfy an analogous condition obtained by rotating Condition (\ref{item:CondA}) by 90 degrees, we get an analogous bound $M(k, \ell-2) + k + 1$ for the percolation time of $A$.

If Condition (\ref{item:CondB}) holds then since $s_1, t_1, s_2, t_2 \geq 2$ we also have $s_1, s_2 \leq k-2$ and $t_1, t_2 \leq \ell-2$. Then
\[
\begin{split}
M(s_1, t_1) + \max\{s_1+t_2, s_2+t_1\} -1 & \leq M(k-2, \ell-2) + k+\ell-5 \\ 
& \leq M(k-1, \ell-1) + k+\ell-5 - (\max\{k,\ell\}-2) \\
& \leq M(k-1, \ell-1) + \min\{\ell,k\}-3 \\
& < M(k-1, \ell-1) + \max\{k,\ell\} -1.
\end{split}
\]

Thus we conclude that the weakest upper bound on percolation time of $A$, equal to
\begin{equation*}
\max\{M(k-1,\ell-1) + \max\{k, \ell\}-1,\ M(k-2, \ell) + \ell+1,\ M(k,\ell-2) + k+1\},
\end{equation*}
is obtained when one of $R'$ or $R''$ is a single site. Since $A$ was arbitrary with $|A| = (k+\ell)/2$ and $T(A) = M(k,\ell)$, this is an upper bound on $M(k,\ell)$ and so \eqref{equation:M0gequpper} is proved. Since this upper bound matches the percolation time of at least one of the sets $A_1(k,\ell)$, $A_2(k,\ell)$, $A_3(k,\ell)$ constructed in the proof of the lower bound on $M(k,\ell)$, we see that at least one of them percolates in time $M(k,\ell)$. This was the last step needed to show that one of them is a $(k,\ell)$-good set. This completes the proof of Lemma \ref{lemma:M0recurrence}. 
\end{proof}

By Lemma~\ref{lemma:M0recurrence} for every $n \ge 4$ there exists an $(n,n)$-good set which percolates $[n]^2$ in the maximal time $M(n)$. So, it is enough to determine $s_0$, $t_0$ and the sequence of moves $1$, $2$ and $3$ which takes the longest time to percolate. In the next lemma we treat a number of small cases to exclude some, a priori possible, values for the numbers $s_0$ and $t_0$.

\begin{lemma}
 \label{lemma:s0equals2}
 Let $k$ and $\ell$ be such that $k \geq 4, \ell \geq 2$ and $k + \ell$ is even. Then there exists a $(k,\ell)$-good set $A^0(k,\ell)$ with the sequence $P_0 \subset P_1 \subset \ldots \subset P_r = [k] \times [\ell]$ of rectangles associated with it, with $P_0 \in \Rec(s, 2) \cup \Rec(2, s)$ for some even $s \geq 4$.
\end{lemma}
\begin{proof} 
Given  $k, \ell$, with $k \geq 4, \ell \geq 2$ and $k + \ell$ is even, consider any $(k,\ell)$-good set, $A^0(k,\ell)$, and its associated good sequence of rectangles $P_0 \subset P_1 \subset \ldots \subset P_r = [k] \times [\ell]$. If $\ell = 2$ then we have $r=0$ and the lemma is trivial. Thus assume that $\ell \geq 3$. Then since $k \geq 4$ we also have $r \geq 1$.

Suppose for a contradiction that $P_0 \in \Rec(s, 1)$, for some odd $s$. By the definition of a $(k,\ell)$-good set we have $P_1 \in \Rec(s_1,t_1)$ with $s_1, t_1 \geq 3$ and $\max\{s_1, t_1\} \geq 4$. The only move we can apply to $P_0$ to satisfy this is Move $3$, so we must have $P_1 \in \Rec(s, 3)$ with $s \geq 5$ (recall that $s_1 + t_1$ is even). This implies $s-1\ge 4$ and so $M(s-1,2) \geq 4$. By inequality \eqref{equation:M0geq} we obtain $M(P_1) = M(s,3) \geq M(s-1,2)+s-1 \geq s+3$. However, if we apply Move $3$ to $P_0 \in \Rec(s, 1)$ we will percolate $P_1 \in \Rec(s, 3)$ in time at most $M(P_0)+s+1 = s+2$. This contradicts the fact that $A^0(k,\ell)$ is $(k,\ell)$-good (more precisely, property \eqref{Rc} of Definition \ref{defn:goodset} will not hold for $P_1$). We deal with the case $P_0 \in \Rec(1,s)$ analogously.

Suppose now that $P_0 \in \Rec(3, 3)$. We can assume that either $P_1 \in \Rec(4, 4)$ (if we use Move $1$ at moment $1$) or $P_1 \in \Rec(5, 3)$ (if we use Move $2$), as the case $P_1 \in \Rec(3, 5)$ (where we use Move $3$) is analogous. In the first case, $M(P_0) = M(3) = 4$ and it takes $3$ time steps to finish the infection of $P_1$ after $P_0$ has been fully infected. Thus $P_1$ becomes fully infected after at most $4+3 = 7$ time steps. However, by inequality \eqref{equation:M0geq} we know that $M(P_1) = M(4) \geq M(4,2)+4+1 = 9$. So, like in the previous paragraph, we have a contradiction to $A^0(k,\ell)$ being $(k,\ell)$-good. In the second case, where $P_1 \in \Rec(5, 3)$, it takes $4$ time steps to apply Move $2$ to $P_0$ and finish the infection of $P_1$ after $P_0$ is fully infected. Thus $P_1$ is fully infected at time $M(P_0)+4 = 8$. However, starting from $P'_0 \in \Rec(4, 2)$ and using Move $1$ at moment $1$ we obtain infection time of $P_1$ equal to $M(4,2)+4 = 8$. This does not contradict the $(k,\ell)$-goodness of $A^0(k,\ell)$ but shows that there exists a $(k,\ell)$-good set $A'(k,\ell)$ with the sequence $P'_0 \subset P_1 \subset \ldots \subset P_r = [k] \times [\ell]$ of rectangles associated with it. This completes the proof of Lemma~\ref{lemma:s0equals2}.
\end{proof}

Let $k$ and $\ell$ be such that $k \geq 4, \ell \ge 2$ and $k + \ell$ is even. By Lemma \ref{lemma:s0equals2} we know that there exists an $(k,\ell)$-good set $A^0(k, \ell)$ with the sequence $P_0 \subset P_1 \subset \ldots \subset P_r = [k] \times [\ell]$ of rectangles associated with it, with $P_0 \in \Rec(s, 2) \cup \Rec(2, s)$ for some even $s \geq 4$. Note that for each $i \geq 1$ the infection of the sites in $P_{i} \setminus P_{i-1}$ starts only after all sites in $P_{i-1}$ are infected, which by the definition of $(k,\ell)$-good sets happens at time $M(P_{i-1})$. The following two observations are crucial to determine the precise value of $M(n)$. In fact, with those observations and equation~\eqref{equation:M0recurrence} we shall be able to find an $(n,n)$-good percolating set, i.e., a set which takes time exactly $M(n)$ to percolate.

\begin{observation}
\label{observation:maximumtwo}
For any $i \ge 1$, no matter which of moves $1$, $2$ or $3$ is used at moment~$i$ to extend the rectangle $P_{i-1}$ to $P_{i}$, at most two new sites become infected at each time step between $M(P_{i-1})+1$ and $M(P_i)$.
\end{observation}

By Observation~\ref{observation:maximumtwo}, having fixed $P_0$ and remembering that in our problem the number of initially infected sites is fixed, a sequence of moves 1, 2 and 3 that maximizes the time to infect a rectangle $R$ must also maximize the number of time steps after $M(P_0)$ at which only one new site of $R \setminus A$ becomes infected. This observation also allows us to change the way we think about maximizing percolation time. Instead of thinking of the exact time it takes to apply a particular Move $j$ at step $i$ we shall think of a \textit{score} of such move which is equal to the number of time steps at which exactly one new site becomes infected when we use Move $j$. Then our task becomes to maximize the cumulative score of our sequence of moves.

\begin{observation} \label{observation:howmanyones}
For any $i \ge 1$ the following statements hold.
\begin{enumerate}
\item If Move $1$ is used at moment $i$ to extend the rectangle $P_{i-1} \in \Rec(s_{i-1}, t_{i-1})$ to $P_{i} \in \Rec(s_{i-1}+1, t_{i-1}+1)$ then only one new site becomes infected at exactly $|s_{i-1} - t_{i-1}|$ time steps between $M(P_{i-1})+1$ and $M(P_i)$, i.e., at $M(P_{i})-|s_{i-1} - t_{i-1}|+1$, $M(P_{i})-|s_{i-1} - t_{i-1}|+2,\dots,M(P_i)-1$ and $M(P_i)$.
\item If Move $2$ or Move $3$ is used at moment $i$ to extend the rectangle $P_{i-1}$ to $P_{i}$ then only one new site becomes infected at exactly $3$ time steps between $M(P_{i-1})+1$ and $M(P_i)$, i.e., at $M(P_{i-1})+1$, $M(P_{i-1})+2$ and $M(P_i)$.
\end{enumerate}
\end{observation}

Using these observations we get the next important claim. To talk about sequences of moves we shall use the following notation similar to that of regular expressions. We say that a finite (possibly empty) sequence is of the form $[a_1|a_2|\ldots|a_r]^*$ if all its terms belong to $\{a_1, \ldots, a_r\} \subset \{1,2,3\}$. We concatenate these expressions to create more general ones which describe the corresponding sets of concatenated sequences. For example, each of the sequences $22133232$, $112333$, $121233$ is of the form $[1]^*[2]^*[1]^*[2|3]^*$, but $122331$ is not.

\begin{claim}\label{claim:moves123}
For $k \ge 4, \ell \ge 2$, there exists a $(k,\ell)$-good set $A$ internally spanning the rectangle $R \in \Rec(k,\ell)$, with a good sequence $P_0 \subset P_1 \subset \ldots \subset P_r = R$ associated with it, with $P_0 \in \Rec(s,2) \cup \Rec(2, s)$ for some $s \geq 4$, such that the sequence of moves $(m_1, m_2, \ldots, m_r)$ used to fully infect $P_r$ from $P_0$ is of the form $[2]^*[1]^*[3]^*$ or of the form $[3]^*[1]^*[2]^*$.
\end{claim}
\begin{proof}
Let us fix an even $s \geq 4$ and assume that $P_0 \in \Rec(s,2) \cup \Rec(2, s)$. Note that this uniquely defines $r = n - s/2 - 1$, which is also the number of initially infected sites outside $P_0$. By Observation~\ref{observation:howmanyones} we immediately see that in such a sequence we should apply moves~$1$ to rectangles $P_i \in \Rec(s_i,t_i)$ with as large as possible difference $|s_i - t_i|$ between the length of the longer side and the length of the shorter side of $P_i$. We also note that whenever Move~$1$ is applied, say to obtain $P_{i+1} \in \Rec(s_{i+1},t_{i+1})$ from $P_{i} \in \Rec(s_{i},t_{i})$, then this difference does not change, i.e., $|s_{i+1} - t_{i+1}| = |s_{i}+1 - (t_{i}+1)| = |s_{i} - t_{i}|$.

If Move~$1$ does not occur in $(m_1, m_2, \ldots, m_r)$ then every move in the sequence has a constant score $3$ depending neither on the step at which it is applied nor on the dimensions of the rectangle it is applied to. Thus every permutation of $(m_1, m_2, \ldots, m_r)$ has the same score and we can clearly rearrange the sequence of moves to make it be of the form $[2]^*[1]^*[3]^*$ (or in fact $[2]^*[3]^*$) without changing percolation time.

Assume that Move~$1$ occurs only once in $(m_1, m_2, \ldots, m_r)$, say that $m_k = 1$ and $m_j \in \{2,3\}$ for $j \in [r] \setminus \{k\}$. Assume first that $P_{k-1} \in \Rec(s_{k-1},t_{k-1})$ with $s_{k-1} > t_{k-1}$, so that the score of Move $1$ at step $k$ equals $s_{k-1} - t_{k-1}$. For a contradiction, let $m_j = 3$ for some $1 \leq j < k \leq r$. Consider a new sequence of moves $(m'_1, m'_2, \ldots, m'_r)$, obtained from $(m_i)_{i=1}^r$ by moving $m_j$ to position $k$ and shifting $m_{j+1}, \ldots, m_k$ to positions $j, \ldots, k-1$ respectively: more formally let $m'_i = m_i$ if $i < j$ or $i > k$,  $m'_i = m_{i+1}$ for $j \leq i \leq k-1$ and $m'_k = m_j = 3$.

Let $P'_0 \subset P'_1 \subset \ldots \subset P'_r = R$ be a sequence of rectangles obtained using the sequence of moves $(m'_i)_{i=1}^r$ (since for all $i \geq k$ the dimensions of rectangles $P'_i$ equal the dimensions of rectangles $P_i$ we indeed have $P'_r = R$). Then the only Move 1 in this new sequence is applied to the rectangle $P'_{k-2} \in \Rec(s_{k-1},t_{k-1}-2)$ (this is because there is one less Move $3$ among $(m'_1, m'_2, \ldots, m'_{k-2})$ as compared to $(m_1, m_2, \ldots, m_{k-1})$) and so this Move 1 has score $s_{k-1}-t_{k-1}+2$. Note that the scores of other moves do not change, as they are still equal $3$. Thus the cumulative score of the sequence $(m'_i)_{i=1}^r$ is greater than the one of the sequence $(m_i)_{i=1}^r$ and consequently percolation time of $A$ is not maximum, contradicting the fact that $A$ is $(k,\ell)$-good. Thus for all $1 \leq i \leq k-1$ we must have $m_i=2$. In an analogous way we prove that $m_i = 3$ for all $k+1 \leq i \leq r$. So in this case $(m_i)_{i=1}^r$ must be of the form $[2]^*[1]^*[3]^*$.

If Move~$1$ occurs only once in $(m_1, m_2, \ldots, m_r)$, say that again $m_k = 1$ and $m_j \in \{2,3\}$ for $j \in [r] \setminus \{k\}$, and additionally we have $P_{k-1} \in \Rec(s_{k-1},t_{k-1})$ with $s_{k-1} < t_{k-1}$, then in an analogous way we show that, this time, $(m_i)_{i=1}^r$ must be of the form $[3]^*[1]^*[2]^*$.

In the remaining case where $P_{k-1}$ is a square, i.e., $s_{k-1} = t_{k-1}$, also in a completely analogous way, we can show that we must have $r=1$ and $m_1 = 1$. If that was not the case, i.e., if we had $r \geq 2$ and there was some $m_j \in \{2,3\}$ then moving $m_j$ to the opposite side of the only occurrence of Move $1$ in $(m_i)_{i=1}^r$ would increase cumulative score (as Move $1$ would no longer have score 0) contradicting the $(k,\ell)$-goodness of $A$. Thus in this case $(m_i)_{i=1}^r = (1)$, which is at the same time of the form $[2]^*[1]^*[3]^*$ and of the form $[3]^*[1]^*[2]^*$.

Thus assume that Move~$1$ occurs more than once in $(m_1, m_2, \ldots, m_r)$. If all occurrences of it constitute a subsequence of consecutive $m_i$'s then we deal with this case exactly like we did with the one where Move~$1$ occurred only once. This is straightforward because, as we already noticed, using Move $1$ does not change the difference between the length of the longer side and the length of the shorter side of the rectangle it is applied to.

Thus assume that there is some $1 \leq j < t < k \leq r$ such that $m_j = m_k = 1$ and $m_t \in \{2,3\}$. For $P_{j} \in \Rec(s_{j},t_{j})$ and $P_{k} \in \Rec(s_{k},t_{k})$ assume that $|s_{j}-t_{j}| \geq |s_{k}-t_{k}|$. Consider a new sequence of moves $(m'_1, m'_2, \ldots, m'_r)$ obtained from $(m_i)_{i=1}^r$ by moving $m_k$ to position $j+1$, and shifting $m_{j+1}, \ldots, m_{k-1}$ to positions $j+2, \ldots, k$ respectively, that is, let $m'_i = m_i$ if $i \leq j$ or $i > k$, $m'_{j+1} = m_k = 1$ and for $j+2 \leq i \leq k$ let $m'_{i} = m_{i-1}$. 

Let $P'_0 \subset P'_1 \subset \ldots \subset P'_r = R$ be a sequence of rectangles obtained using the sequence $(m'_i)_{i=1}^r$ (note that as previously $P'_r = P_r = R$). Then using Move $m'_{j+1} = 1$ at step $j+1$ we finish the infection of $P'_{j+1} \in \Rec(s_{j}+1,t_{j}+1)$ and so this move has score $|s_{j}-t_{j}|$ which is at least as big as the score of the move $m_k$ at time $k$. Note that if $i \leq j$ or $i > k$ then the score of the move $m'_i$ at time $i$ equals the score of the move $m_i$ at time $i$. Finally if $j+2 \leq i \leq k$ then the score of the move $m'_i$ at time $i$ equals the score of the move $m_{i-1}$ at time $i-1$. Thus the cumulative score of the sequence $(m'_i)_{i=1}^r$ is at least as big as the one of the sequence $(m_i)_{i=1}^r$. Thus applying this modification (which does not decrease the score) of the sequence $(m_i)_{i=1}^r$ we could obtain a sequence describing another $(k,\ell)$-good set in which all moves $1$ occur in consecutive positions of the sequence. However, we already know that such sequence must be of the form $[2]^*[1]^*[3]^*$ or of the form $[3]^*[1]^*[2]^*$. When $|s_{j}-t_{j}| < |s_{k}-t_{k}|$ we proceed analogously, moving $m_j=1$ to position $k-1$. This completes the proof of the claim.
\end{proof}

By Lemma~\ref{lemma:s0equals2} there exists an $(k,\ell)$-good set $A$ for which $P_0 \in \Rec(s,2) \cup \Rec(2,s)$, with $s \geq 4$. The construction we give in Lemma~\ref{lemma:kequals2} shows that in this case $P_0$ can be obtained from some $P' \in \Rec(2,2)$ either by, if $P_0 \in \Rec(s,2)$, applying $(s-2)/2$ times Move~$2$, or by applying Move~$3$ if $P_0 \in \Rec(2,s)$. Note that indeed for all these occurrences of move $2$ or $3$ we infect one new site at exactly three time steps.

\begin{observation}
\label{observation:niceSet}
The proof of Claim~\ref{claim:moves123} actually tells us that, for a brief moment slightly abusing the notation (relaxing condition (\ref{Ra}) in Definition \ref{defn:goodset}) and for $i \geq 1$ allowing $P'_i \in \Rec(s'_i,2) \cup \Rec(2,s'_i)$ for $s'_i \geq 4$ and even, there exists a $(k,\ell)$-good set $A$ and a good sequence of rectangles $P'_0 \subset P'_1 \subset \ldots \subset P'_r \in \Rec(k,\ell)$ associated with it, with $P'_0 \in \Rec(2,2)$, such that the sequence of moves $(m'_1, m'_2, \ldots, m'_r)$ used to fully infect $P'_r$ from $P'_0$ is of the form $[2]^*[1]^*[3]^*$ or of the form $[3]^*[1]^*[2]^*$. Since in Claim~\ref{claim:moves123} we have $P_0 \in \Rec(s,2) \cup \Rec(2,s)$, with $s \geq 4$, we see that if $(m'_i)_{i=1}^r$ is of the form $[2]^*[1]^*[3]^*$ then the subsequence of moves $2$ is nonempty. Analogously, if $(m'_i)_{i=1}^r$ is of the form $[3]^*[1]^*[2]^*$ then the subsequence of moves $3$ is nonempty. Applying a nonempty sequence of moves $2$ to $P'_0 \in \Rec(2,2)$ fully infects a rectangle $P''_0 \in \Rec(s'',2)$, with $s'' \geq 4$ and even. Analogously, applying a nonempty sequence of moves $3$ to $P'_0 \in \Rec(2,2)$ fully infects a rectangle $P''_0 \in \Rec(2,s'')$, with $s'' \geq 4$ and even.
\end{observation}

Thus by Observation~\ref{observation:niceSet} we obtain the following lemma which, for any $k$ and $\ell$ such that $k \geq 4, \ell \geq 2$ and $k + \ell$ is even, fully characterizes a good sequence of rectangles associated with at least one $(k,\ell)$-good set of initially infected sites.

\begin{lemma}
\label{lemma:niceSet}
Let $k$ and $\ell$ be such that $k \geq 4, \ell \geq 2$ and $k + \ell$ is even. Then there exists a $(k,\ell)$-good set $A$ and a good sequence of rectangles $P_0 \subset P_1 \subset \ldots \subset P_r \in \Rec(k,\ell)$ associated with it, with $P_0 \in \Rec(s,2) \cup \Rec(2,s)$ for some $s \geq 4$, such that the sequence of moves $(m_1, m_2, \ldots, m_r)$ used to fully infect $P_r$ from $P_0$ is either of the form $[1]^*[3]^*$ if $P_0 \in \Rec(s,2)$, or of the form $[1]^*[2]^*$ if $P_0 \in \Rec(2,s)$.
\end{lemma}

\begin{cor}
\label{corollary:niceSet}
For $n \ge 4$, there is a $(n,n)$-good set $A$, whose good sequence of rectangles $P_0 \subset P_1 \subset \ldots \subset P_r \in \Rec(n,n)$ is such that $P_0 \in \Rec(s,2)$ and that the sequence of moves used to build it is of the form $[1]^*[3]^*$. Furthermore, if the number of times we use Move~$1$ equals $m$ then $m=n-s$ and we must use Move~$3$ exactly $\frac{n-2-m}{2}$ times.
\end{cor}
\begin{proof}
Apply Lemma~\ref{lemma:niceSet} with $k = \ell = n$. By symmetry, we can assume that $P_0 \in \Rec(s,2)$ and the sequence of moves obtained is of type $[1]^*[3]^*$. It is trivial to check that, in order to obtain $P_r \in \Rec(n,n)$, we must have $m = n-s$ and we must use Move $3$ exactly $\frac{n-2-m}{2}$ times.
\end{proof}

We are now ready to prove the exact formula for $M(n)$ for $n \geq 4$.
\begin{proofOfThm}{thm:minimalExact}
Given $m \geq 0$, let $A^n_m$ be (if it exists) the $(n,n)$-good set described in Corollary~\ref{corollary:niceSet} for which during the infection process Move $1$ is used exactly $m$ times (note that when $n$ and $m$ have different parities then $A^n_m$ definitely does not exist). For example, Figure~\ref{figure:A^{12}_4} shows the set $A^{12}_4$.
\begin{figure}[ht]
  \centering
  \begin{tikzpicture}[scale=\tikzscale]
    \fill[color=lightgray] (4.5,0) rectangle (5,0.5);
    \fill[color=lightgray] (4,0.5) rectangle (4.5,1);
    \fill[color=lightgray] (3,0) rectangle (3.5,0.5);
    \fill[color=lightgray] (2,0.5) rectangle (2.5,1);
    \fill[color=lightgray] (1,0) rectangle (1.5,0.5);

    \fill[color=lightgray] (0.5,1) rectangle (1,1.5);
    \fill[color=lightgray] (5,1.5) rectangle (5.5,2);
    \fill[color=lightgray] (0,2) rectangle (0.5,2.5);
    \fill[color=lightgray] (5.5,2.5) rectangle (6,3);

    \fill[color=lightgray] (0,3.5) rectangle (0.5,4);
    \fill[color=lightgray] (5.5,4.5) rectangle (6,5);
    \fill[color=lightgray] (0,5.5) rectangle (0.5,6);

    \draw[step=.5cm,gray,thick]
    (0,0) grid (6,6);
    \draw[line width=1mm,black,dashed]
    (1,0) -- (1,1) -- (5,1) -- (5,0) -- (1,0);
    \draw [|-|, black]
      (-0.25,1)  -- (-0.25,3)
       node [black,midway,left=4pt] {$m=4$};
    \draw[black] (3,-0.25) node [below] {$n-m = 8$};
  \end{tikzpicture}
  \caption{Set $A^{12}_4$.}
  \label{figure:A^{12}_4}
\end{figure}
Now, we notice that for every $n \geq 4$ and $0 \leq m \leq n-4$ (with $n$ and $m$ having the same parity) the percolation time of $A^{n}_m$ (if it exists) can be given explicitly as follows:
\begin{enumerate}
\item Infection of the rectangle $P_0 \in \Rec(n-m,2)$ takes time
 \[
  M(n-m,2) = \frac{3(n-m)-4}{2} = \frac{3(n-m)}{2}-2; 
 \]
\item Applying $m$ times Move~$1$ takes time
 \[
  \sum_{i=0}^{m-1} (n-m+i) = mn-m^2+\frac{m(m-1)}{2} = mn-\frac{m(m+1)}{2};  
 \]
\item Finishing the infection with $\frac{n-m-2}{2}$ applications of Move~$3$ takes time
 \[
  \frac{n-m-2}{2}(n+1) = \frac{n^2-n-mn-m-2}{2}.
 \]
\end{enumerate}
Letting $f(n,m)$ denote the percolation time of $A^{n}_m$, by the above calculations we have
\begin{equation*}
f(n,m) = \frac{n^2+n(m+2)-(m^2+5m+6)}{2}.
\end{equation*}
For a given $n$, the function $f_n(m) = f(n,m)$ is a quadratic function of $m$ with maximum value at $m=\frac{n-5}{2}$. As our $(n,n)$-good set  maximizes $f_n(m)$ subject to $m \in \NN$ and $m$ having the same parity as $n$, maximal percolation time is obtained for 
\begin{equation*}
m = m_0 = \floor{\frac{n}{2}-\frac{5}{2}} + \indicator{4 \mid n-1} + \indicator{4 \mid n},
\end{equation*}
where in the above statement we use $\indicator{\phi}$ to denote the indicator function,
\begin{equation*}  
  \indicator{\phi} =
  \begin{cases}
    1, & \text{if the sentence $\phi$ is true,}\\
    0, & \text{otherwise.}
  \end{cases}  
\end{equation*}
Now, by considering the possible values of $n$ (mod 4) we see that for all $n \geq 4$ we have $f(n,m_0) = \lfloor \frac{5n^2-2n}{8} \rceil$. This completes our proof.
\end{proofOfThm}

\bigskip

Using Lemma~\ref{lemma:niceSet}, given $\alpha \in (0,1)$ and $n$ large, assuming $(1+\alpha)n$ is an even natural number we can determine an asymptotic value of $M(n,\alpha n)$. All we need to do is, for both $P_0 \in \Rec(s,2)$ and $P_0 \in \Rec(2,s)$, to optimize $s$ to maximize the cumulative score of our sequence of moves knowing that the number of times we use Move~$1$ is fully determined by $s$ and the horizontal or vertical alignment of $P_0$ in $[n] \times [\alpha n]$, and that the score of all occurrences of Move~1 equals $s-2$.

\bigskip
\bigbreak

\begin{cor}
 \label{cor:maxRectangles}
We have:\nobreak
\begin{enumerate}
 \item If $\frac{1}{2} \leq \alpha < 1$ then
  \[
   M(n,\alpha n) = \left(\frac{\alpha}{2}+\frac{1}{8}\right)n^2 + O(n).
  \]
  To maximize percolation time we should first infect a roughly $\frac{n}{2} \times 2$ rectangle in time $O(n)$, then using Move 1 $\left(\frac{n}{2}+O(1)\right)$ times extend it to a roughly $n \times \frac{n}{2}$ one in time $\frac{3n^2}{8}+O(n)$, and then finish the infection in additional $\left(\frac{\alpha}{2}-\frac{1}{4}\right)n^2+O(n)$ time steps using Move~3 $\left(\left(\frac{\alpha}{2}-\frac{1}{4}\right)n+O(1)\right)$ times.
 \item If $0 < \alpha < \frac{1}{2}$ then
  \[
   M(n,\alpha n) = \left(\alpha-\frac{\alpha^2}{2}\right)n^2 + O(n).
  \]
  To maximize percolation time we should first infect a roughly $(1-\alpha)n \times 2$ rectangle in time $O(n)$, and then finish the infection in additional $\left(\alpha-\frac{\alpha^2}{2}\right)n^2 + O(n)$ time steps using Move 1 $\left(\alpha n+O(1)\right)$ times.
\end{enumerate}
\end{cor}

\bibliographystyle{plain}

\begin{thebibliography}{10}

\bibitem{metastabilityeffects}
M.~Aizenman and J.~Lebowitz.
\newblock Metastability effects in bootstrap percolation.
\newblock {\em Journal of Physics A}, 21:3801--3813, 1988.

\bibitem{sharpbootstrapall}
J.~Balogh, B.~Bollob{\'a}s, H.~Duminil-Copin, and R.~Morris.
\newblock The sharp threshold for bootstrap percolation in all dimensions.
\newblock {\em Transactions of the American Mathematical Society},
  364:2667--2701, 2012.

\bibitem{randomdisease}
J.~Balogh and G.~Pete.
\newblock Random disease on the square grid.
\newblock {\em Random Structures and Algorithms}, 13:409--422, 1998.

\bibitem{benevidesprzykucki01}
F.~S. Benevides and M.~Przykucki.
\newblock Maximum percolation time in two-dimensional bootstrap percolation.
\newblock Preprint, 2013.

\bibitem{densebootstraptime}
B.~Bollob{\'a}s, C.~Holmgren, P.~Smith, and A.J. Uzzell.
\newblock The time of bootstrap percolation for dense initial sets.
\newblock To appear in \textit{Annals of Probability},
  \url{http://arxiv.org/abs/1205.3922}.

\bibitem{densebootstraptimeall}
B.~Bollob{\'a}s, P.~Smith, and A.J. Uzzell.
\newblock The time of bootstrap percolation with dense initial sets for all
  thresholds.
\newblock Preprint, \url{http://arxiv.org/abs/1209.4339}.

\bibitem{bootstrapbethe}
J.~Chalupa, P.L. Leath, and G.R. Reich.
\newblock Bootstrap percolation on a {B}ethe latice.
\newblock {\em Journal of Physics C}, 12:L31--L35, 1979.

\bibitem{sharpmetastability}
A.~E. Holroyd.
\newblock Sharp metastability threshold for two-dimensional bootstrap
  percolation.
\newblock {\em Probability Theory and Related Fields}, 125:195--224, 2003.

\bibitem{largestgridbootstrap}
R.~Morris.
\newblock Minimal percolating sets in bootstrap percolation.
\newblock {\em The Electronic Journal of Combinatorics}, 16(1):1--20, 2009.

\bibitem{theoryautomata}
J.~von Neumann.
\newblock {\em Theory of Self-Reproducing Automata}.
\newblock University of Illinois Press, 1966.

\bibitem{przykucki01}
M.~Przykucki.
\newblock Maximal percolation time in hypercubes under 2-bootstrap percolation.
\newblock {\em The Electronic Journal of Combinatorics}, 19(2):1--13, 2012.

\bibitem{largesthypercubebootstrap}
E.~Riedl.
\newblock Largest minimal percolating sets in hypercubes under 2-bootstrap
  percolation.
\newblock {\em The Electronic Journal of Combinatorics}, 17(1):1--13, 2010.

\bibitem{schrodernumbers}
L.~Shapiro and A.B. Stephens.
\newblock Bootstrap percolation, the {S}chr{\"o}der numbers, and the
  ${N}$-kings problem.
\newblock {\em SIAM Journal on Discrete Mathematics}, 4:275--280, 1991.

\end{thebibliography}
%\printindex
\end{document}