\section*{5. For ALL APPLICANTS.}
An $n \times n$ grid consists of squares arranged in $n$ rows and $n$ columns; for example, a chessboard is an $8 \times 8$ grid. Let us call a semi-grid of size $n$ the lower left part of an $n \times n$ grid - that is, the squares located on or below the grid's diagonal. For example, Figure C shows an example of a semi-grid of size 4.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{fc6f49e6-218d-48e2-a799-b90a6c6181d7-14_415_418_595_816}
\captionsetup{labelformat=empty}
\caption{Figure C}
\end{center}
\end{figure}

Let us suppose that a robot is located in the lower-left corner of the grid. The robot can move only up or right, and its goal is to reach one of the goal squares, which are all located on the semi-grid's diagonal. In the example shown in Figure C , the robot is initially located in the square denoted with R , and the goal squares are shown in grey. Let us call a solution a sequence of the robot's moves that leads the robot from the initial location to some goal square.\\
(i) Write down all 8 solutions for a robot on a semi-grid of size 4 .\\
(ii) Devise a concise way of representing the possible journeys of the robot in a semi-grid of size $n$. In your notation, which of the journeys are solutions?\\
(iii) Write down a formula for the number of possible solutions in a semi-grid of size $n$. Explain why your formula is correct.

Now let us change the problem slightly and redefine a goal square as any square that can be described as follows:

\begin{itemize}
  \item the lower-left square is not a goal square;
  \item each square that is located immediately above or immediately to the right of a non-goal square is a goal square; and
  \item each square that is located immediately above or immediately to the right of a goal square is a non-goal square.\\
Furthermore, let us assume that, upon reaching a goal square, the robot may decide to stop or to continue moving (provided that there are more allowed moves).\\
(iv) With these modifications in place, write down all the solutions in a semi-grid of size 4, and all the solutions in a semi-grid of size 5.\\
(v) How many solutions are there now in a semi-grid of size $n$, where $n$ is a positive integer? You may wish to consider separately the cases where $n$ is even or odd.
\end{itemize}