Problem: Let $M$ be a finite set of lattice points
and $n$ be a positive integer.
A \emph{mine-avoiding path} is a path of lattice points with length $n$,
beginning at $(0,0)$ and ending at a point on the line $x+y=n$,
that does not contain any point in $M$.
Prove that if there exists a mine-avoiding path,
then there exist at least $2^{n-|M|}$ mine-avoiding paths.

Solution: We present two approaches.

\paragraph{Solution 1.}
We prove the statement by induction on $n$. We use $n=0$ as a base case, where
the statement follows from $1\geq 2^{-|M|}$. For the inductive step, let $n >
0$. There exists at least one mine-avoiding path, which must pass through either
$(0, 1)$ or $(1, 0)$. We consider two cases:

\textbf{Case 1: there exist mine-avoiding paths starting at both $(1, 0)$ and
$(0, 1)$.}

By the inductive hypothesis, there are at least $2^{n-1-|M|}$ mine-avoiding
paths starting from each of $(1, 0)$ and $(0, 1)$. Then the total number of
mine-avoiding paths is at least $2^{n-1-|M|}+2^{n-1-|M|}=2^{n-|M|}$.

\textbf{Case 2: only one of $(1, 0)$ and $(0, 1)$ is on a mine-avoiding path.}

Without loss of generality, suppose no mine-avoiding path starts at $(0, 1)$.
Then some element of $M$ must be of the form $(0, k)$ for $1\leq k\leq n$ in
order to block the path along the $y$-axis. This element can be ignored for any
mine-avoiding path starting at $(1, 0)$. By the inductive hypothesis, there are
at least $2^{n-1-(|M|-1)}=2^{n-|M|}$ mine-avoiding paths.

This completes the induction step, which solves the problem.

\paragraph{Solution 2.}

\begin{lemma*}
  If $|M|<n$, there is more than one mine-avoiding path.
\end{lemma*}

\begin{proof}
  Let $P_0,P_1,\dots,P_{n}$ be a mine-avoiding path. Set $P_i=(x_i,y_i)$. For $0 \leq i < n$, define a path $Q_i$ as follows:

  \begin{itemize}
    \item Make the first $i+1$ points $P_0,P_1,\dots,P_i$.
    \item If $P_i \to P_{i+1}$ is one unit up, go right until $(n-y_i,y_i)$.
    \item If $P_i \to P_{i+1}$ is one unit right, go up until $(x_i,n-x_i)$.
  \end{itemize}

  \begin{center}
    \begin{asy}
      unitsize(3);
      draw((0,0)--(10,0)--(20,0)--(20,10)--(30,10)--(30,20));
      draw((0,0)--(0,10)--(0,20)--(0,30)--(0,40)--(0,50), rgb(1,0,0));
      draw((10,0)--(10,40),rgb(1,0,0));
      draw((20,0)--(50,0),rgb(1,0,0));
      draw((20,10)--(20,30),rgb(1,0,0));
      draw((30,10)--(40,10),rgb(1,0,0));
      draw((0,50)--(50,0),rgb(0,0,1) + dashed);
    \end{asy}

  \end{center}

  The diagram above is an example for $n=5$ with the new segments formed by the $Q_i$ in red, and the line $x+y=n$ in blue.

  By definition, $M$ has less than $n$ points, none of which are in the original path. Since all $Q_i$ only intersect in the original path, each mine is in at most one of $Q_0,Q_1,\dots,Q_{n-1}.$ By the Pigeonhole Principle, one of the $Q_i$ is mine-avoiding.
\end{proof}

Now, consider the following process:
\begin{itemize}
  \item Start at $(0,0)$.
  \item If there is only one choice of next step that is part of a mine-avoiding path, make that choice.
  \item Repeat the above until at a point with two possible steps that are part of mine-avoiding paths.
  \item Add a mine to the choice of next step with more mine-avoiding paths through it. If both have the same number of mine-avoiding paths through them, add a mine arbitrarily.
\end{itemize}

\begin{center}
  \begin{asy}
    unitsize(3);
    draw((-5,-5)--(45,-5));
    draw((-5,5)--(45,5));
    draw((-5,15)--(35,15));
    draw((-5,25)--(25,25));
    draw((-5,35)--(15,35));
    draw((-5,45)--(5,45));
    draw((-5,-5)--(-5,45));
    draw((5,-5)--(5,45));
    draw((15,-5)--(15,35));
    draw((25,-5)--(25,25));
    draw((35,-5)--(35,15));
    draw((45,-5)--(45,5));
    fill((-5,5)--(-5,15)--(5,15)--(5,5)--cycle);
    fill((25,5)--(25,15)--(35,15)--(35,5)--cycle);
    label("$1$",(10,30));
    label("$1$",(20,20));
    label("$1$",(40,0));
    label("$1$",(30,0));
    label("$2$",(20,0));
    label("$2$",(10,20));
    label("$1$",(20,10));
    label("$3$",(10,10));
    label("$5$",(10,0));
    label("$5$",(0,0));
    label("$0$",(0,20));
    label("$0$",(0,30));
    label("$0$",(0,40));
  \end{asy}
\end{center}

For instance, consider the above diagram for $n=4$. Lattice points are replaced with squares. Mines are black squares and each non-mine is labelled with the number of mine-avoiding paths passing through it. This process would start at $(0,0)$, go to $(1,0)$, then place a mine at $(1,1)$.


This path increases the size of $M$ by one, and reduces the number of mine-avoiding paths to a nonzero number at most half of the original. Repeat this process until there is only one path left. By our lemma, the number of mines must be at least $n$ by the end of the process, so the process was iterated at least $n-|M|$ times. By the halving property, there must have been at least $2^{n-|M|}$ mine-avoiding paths before the process, as desired.