\section*{7. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.}
You are given two identical black boxes, each with an $N$-digit display and each with two buttons marked $A$ and $B$. Button $A$ resets the display to 0 , and button $B$ updates the display using a complex, unknown but fixed, function $f$, so that pressing button $A$ then repeatedly pressing button $B$ displays a fixed sequence

$$x _ { 0 } = 0 , x _ { 1 } = f \left( x _ { 0 } \right) , x _ { 2 } = f \left( x _ { 1 } \right) , \ldots ,$$

the same for both boxes. In general $x _ { i } = f ^ { i } ( 0 )$ where $f ^ { i }$ denotes applying function $f$ repeatedly $i$ times.

You have no pencil and paper, and the display has too many digits for you to remember more than a few displayed values, but you can compare the displays on the two boxes to see if they are equal, and you can count the number of times you press each button.\\
(i) Explain briefly why there must exist integers $i , j$ with $0 \leqslant i < j$ such that $x _ { i } = x _ { j }$.\\
(ii) Show that if $x _ { i } = x _ { j }$ then $x _ { i + s } = x _ { j + s }$ for any $s \geqslant 0$.\\
(iii) Let $m$ be the smallest number such that $x _ { m }$ appears more than once in the sequence, and let $p > 0$ be the smallest number such that $x _ { m } = x _ { m + p }$. Show that if $i \geqslant m$ and $k \geqslant 0$ then $x _ { i + k p } = x _ { i }$.\\
(iv) Given integers $i , j$ with $0 \leqslant i < j$, show that $x _ { i } = x _ { j }$ if and only if $i \geqslant m$ and $j - i$ is a multiple of $p$. [Hint: let $r$ be the remainder on dividing $j - i$ by $p$, and argue that $r = 0$.]\\
(v) You conduct an experiment where (after resetting both boxes) you repeatedly press button $B$ once on one box and button $B$ twice on the other box and compare the displays, thus determining the smallest number $u > 0$ such that $x _ { u } = x _ { 2 u }$. What relates the value of $u$ to the (unknown) values of $m$ and $p$ ?\\
(vi) Once $u$ is known, what experiment would you perform to determine the value of $m$ ?\\
(vii) Once $u$ and $m$ are known, what experiment would tell you the value of $p$ ?

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

\section*{BLANK PAGE}
\section*{BLANK PAGE}
\section*{BLANK PAGE}
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{9b5230b6-1357-4a2a-9c24-53c6f69fdc21-32_573_558_718_754}
\end{center}