6.

For Oxford applicants in Computer Science / Mathematics \& Computer Science / Computer Science \& Philosophy ONLY.

In an octatree, all the digits 1 to 8 are arranged in a diagram like trees $T _ { 1 }$ and $T _ { 2 }$ shown below. There is a single digit at the root, drawn at the top (so the root is 3 in $T _ { 1 }$ ), and every other digit has another digit as its parent, so that by moving up the tree from parent to parent, each non-root digit has a unique path to the root. The order in which the children of any parent are drawn does not matter, so for simplicity we show them in increasing order from left to right.

A leaf is a digit that is not the parent of any other digit: in tree $T _ { 1 }$, the leaves are $2,4,6$ and 7 .

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{$T _ { 1 }$}
  \includegraphics[alt={},max width=\textwidth]{79d0ff85-041b-4bab-874a-dce185c34bcb-11_336_334_1001_640}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{$T _ { 2 }$}
  \includegraphics[alt={},max width=\textwidth]{79d0ff85-041b-4bab-874a-dce185c34bcb-11_336_282_1001_1134}
\end{center}
\end{figure}

The code for an octatree is a sequence of seven digits obtained as follows. We use $T _ { 1 }$ as an example.

\begin{itemize}
  \item Remove the numerically smallest leaf and write down its parent. In $T _ { 1 }$, we remove 2 and write down its parent 8 .
  \item In the tree that remains, remove the smallest leaf and write down its parent. In $T _ { 1 }$, after having removed 2, we remove 4 and write down its parent 5 .
  \item Continue in this way until only the root remains. In $T _ { 1 }$, we would have deleted the digits $2,4,5,6,7,1,8$ in that order and obtained the code 8538183.\\
(i) $[ 1$ mark $]$ Find the code for the octatree $T _ { 2 }$.\\[0pt]
(ii) [1 mark] Draw the octatree that has the code $\mathbf { 8 8 8 8 8 8 8 }$.\\[0pt]
(iii) [2 marks] Draw the octatree that has the code $\mathbf { 3 1 6 5 4 7 2 }$.\\[0pt]
(iv) [3 marks] What are the leaves of the octatree that has the code $\mathbf { 1 6 1 8 3 8 8 }$ ? Justify your answer.\\[0pt]
(v) [2 marks] Find all the digits in the octatree that has the code $\mathbf { 1 6 1 8 3 8 8 }$ that have 1 as their parent.\\[0pt]
(vi) [2 marks] Reconstruct the whole tree that has the code 1618388.\\[0pt]
(vii) [2 marks] Briefly describe a procedure that given a sequence of seven digits from 1 to 8 constructs an octatree with that sequence as its code.\\[0pt]
(viii) [2 marks] Is the number of distinct octatrees greater than or smaller than $2,000,000$ ? Justify your answer. (You may use the fact that $2 ^ { 10 } = 1024$.)
\end{itemize}