\section*{7. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.}
Quantiles is game for a single player. It is played with an inexhaustible supply of tiles, each bearing one of the symbols $\mathrm { A } , \mathrm { B }$ or C . In each move, the player lays down a row of tiles containing exactly one A and one B , but varying numbers of C 's. The rules are as follows:

\begin{itemize}
  \item The player may play the basic rows CACBCC and CCACBCCC.
  \item If the player has already played rows of the form $r \mathrm {~A} s \mathrm {~B} t$ and $x \mathrm {~A} y \mathrm {~B} z$ (they may be the same row), where each of $r , s , t , x , y , z$ represents a sequence of C's, then he or she may add the row $r x \mathrm {~A} s y \mathrm {~B} t z$, in which copies of the sequences of C's from the previous rows are concatenated with an intervening A and B : this is called a join move. The original rows remain, and may be used again in subsequent join moves.
  \item No other rows may be played.
\end{itemize}

The player attempts to play one row after another so as to finish with a specified goal row.\\
(i) Give two examples of rows, other than basic rows, that may be played in the game.\\
(ii) Give two examples of rows, each containing exactly one A and one B , that may never be played, and explain why.\\
(iii) Let $\mathrm { C } ^ { n }$ denote an unbroken sequence of $n$ tiles each labelled with C . Can the goal row $\mathrm { C } ^ { 64 } \mathrm { AC } ^ { 48 } \mathrm { BC } ^ { 112 }$ be achieved? Justify your answer.\\
(iv) Can the goal row $\mathrm { C } ^ { 128 } \mathrm { AC } ^ { 48 } \mathrm { BC } ^ { 176 }$ be achieved? Justify your answer.\\
(v) The goal row $\mathrm { C } ^ { 31 } \mathrm { AC } ^ { 16 } \mathrm { BC } ^ { 47 }$ is achievable; show that it can be reached with 7 join moves.\\
(vi) In any game, we call a row useless if it repeats an earlier row or it is not used in a subsequent join move. What is the maximum number of join moves in a game that ends with $\mathrm { C } ^ { 31 } \mathrm { AC } ^ { 16 } \mathrm { BC } ^ { 47 }$ and contains no useless rows?

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank\\
\includegraphics[max width=\textwidth, alt={}, center]{197f6ad6-3a31-43db-af23-48285e63cd42-32_573_558_718_754}