\section*{7. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.}
A simple computer can operate on lists of numbers in several ways.

\begin{itemize}
  \item Given two lists $a$ and $b$, it can make the join $a + b$, by placing list $b$ after list $a$. For example if
\end{itemize}

$$a = ( 1,2,3,4 ) \quad \text { and } \quad b = ( 5,6,7 ) \quad \text { then } \quad a + b = ( 1,2,3,4,5,6,7 ) .$$

\begin{itemize}
  \item Given a list $a$ it can form the reverse sequence $R ( a )$ by listing $a$ in reverse order. For example if
\end{itemize}

$$a = ( 1,2,3,4 ) \quad \text { then } \quad R ( a ) = ( 4,3,2,1 ) .$$

(i) Given sequences $a$ and $b$, express $R ( a + b )$ as the join of two sequences. What is $R ( R ( a ) )$ ?

\begin{itemize}
  \item Given a sequence $a$ of length $n$ and $0 \leqslant k \leqslant n$, then the $k$ th shuffle $S _ { k }$ of a moves the first $k$ elements of $a$ to the end of the sequence in reverse order. For example
\end{itemize}

$$S _ { 2 } ( 1,2,3,4,5 ) = ( 3,4,5,2,1 ) \quad \text { and } \quad S _ { 3 } ( 1,2,3,4,5 ) = ( 4,5,3,2,1 ) .$$

(ii) Given two sequences $a$ and $b$, both of length $k$, express $S _ { k } ( a + b )$ as the join of two sequences. What is $S _ { k } \left( S _ { k } ( a + b ) \right)$ ?\\
(iii) Now let $a = ( 1,2,3,4,5,6,7,8 )$. Write down

$$S _ { 5 } \left( S _ { 5 } ( a ) \right)$$

as the join of three sequences that are either in order or in reverse order. Show that the sequence $a$ is back in its original order after four $S _ { 5 }$ shuffles.\\
(iv) Now let $a$ be a sequence of length $n$ with $k \geqslant n / 2$. Prove, after $S _ { k }$ is performed four times, that the sequence returns to its original order.\\
(v) Give an example to show that when $k < n / 2$, the sequence need not be in its original order after $S _ { k }$ is performed four times. For your example how many times must $S _ { k }$ be performed to first return the sequence to its original order?

This page has been intentionally left blank for candidate use

This page has been intentionally left blank for candidate use

This page has been intentionally left blank for candidate use

This page has been intentionally left blank for candidate use

This page has been intentionally left blank for candidate use

This page has been intentionally left blank for candidate use

This page has been intentionally left blank for candidate use