2. For ALL APPLICANTS.

In this question you may use without proof the following fact:
$$\ln ( 1 - x ) = - x - \frac { x ^ { 2 } } { 2 } - \frac { x ^ { 3 } } { 3 } - \frac { x ^ { 4 } } { 4 } \cdots - \frac { x ^ { n } } { n } \ldots \quad \text { for any } x \text { with } | x | < 1 .$$
[Note that $\ln x$ is alternative notation for $\log _ { e } x$.]
(i) By choosing a particular value of $x$ with $| x | < 1$, show that
$$\ln 2 = \frac { 1 } { 2 } + \frac { 1 } { 2 \times 2 ^ { 2 } } + \frac { 1 } { 3 \times 2 ^ { 3 } } + \frac { 1 } { 4 \times 2 ^ { 4 } } + \frac { 1 } { 5 \times 2 ^ { 5 } } + \ldots$$
(ii) Use part (i) and the fact that
$$\frac { 1 } { n 2 ^ { n } } < \frac { 1 } { 3 \times 2 ^ { n } } \quad \text { for } n \geqslant 4$$
to find the integer $k$ such that $\frac { k } { 24 } < \ln 2 < \frac { k + 1 } { 24 }$.
(iii) Show that
$$\ln \left( \frac { 3 } { 2 } \right) = \frac { 1 } { 2 } - \frac { 1 } { 2 \times 2 ^ { 2 } } + \frac { 1 } { 3 \times 2 ^ { 3 } } - \frac { 1 } { 4 \times 2 ^ { 4 } } + \frac { 1 } { 5 \times 2 ^ { 5 } } - \ldots$$
and deduce that
$$\ln 3 = 1 + \frac { 1 } { 3 \times 2 ^ { 2 } } + \frac { 1 } { 5 \times 2 ^ { 4 } } + \frac { 1 } { 7 \times 2 ^ { 6 } } + \ldots$$
(iv) Deduce that $\frac { 13 } { 12 } < \ln 3 < \frac { 11 } { 10 }$.
(v) Which is larger: $3 ^ { 17 }$ or $4 ^ { 13 }$ ? Without calculating either number, justify your answer.
This page has been intentionally left blank

3. For APPLICANTS IN $\left\{ \begin{array} { l } \text { MATHEMATICS } \\ \text { MATHEMATICS \& STATISTICS } \\ \text { MATHEMATICS \& PHILOSOPHY } \\ \text { MATHEMATICS \& COMPUTER SCIENCE } \end{array} \right\}$ ONLY.

Computer Science and Computer Science \& Philosophy applicants should turn to page 20.
The degree of a polynomial is the highest exponent that appears among its terms. For example, $2 x ^ { 6 } - 3 x ^ { 2 } + 1$ is a polynomial of degree 6 .
(i) A polynomial $p ( x )$ has a turning point at ( 0,0 ). Explain why $p ( 0 ) = 0$ and why $p ^ { \prime } ( 0 ) = 0$, and explain why there is a polynomial $q ( x )$ such that
$$p ( x ) = x ^ { 2 } q ( x ) .$$
(ii) A polynomial $r ( x )$ has a turning point at ( $a , 0$ ) for some real number $a$. Write down an expression for $r ( x )$ that is of a similar form to the expression (*) above. Justify your answer in terms of a transformation of a graph.
(iii) You are now given that $f ( x )$ is a polynomial of degree 4 , and that it has two turning points at $( a , 0 )$ and at $( - a , 0 )$ for some positive number $a$.
(a) Write down the most general possible expression for $f ( x )$. Justify your answer.
(b) Describe a symmetry of the graph of $f ( x )$, and prove algebraically that $f ( x )$ does have this symmetry.
(c) Write down the $x$-coordinate of the third turning point of $f ( x )$.
(iv) Is there a polynomial of degree 4 which has turning points at $( 0,0 )$, at $( 1,3 )$, and at $( 2,0 )$ ? Justify your answer.
(v) Is there a polynomial of degree 4 which has turning points at ( 1,6 ), at ( 2,3 ), and at $( 4,6 )$ ? Justify your answer.
This page has been intentionally left blank

4. For APPLICANTS IN $\left\{ \begin{array} { l } \text { MATHEMATICS } \\ \text { MATHEMATICS \& STATISTICS } \\ \text { MATHEMATICS \& PHILOSOPHY } \end{array} \right\}$ ONLY.

Mathematics \& Computer Science, Computer Science and Computer Science \& Philosophy applicants should turn to page 20.
Charlie is trying to cut a cake. The cake is a square with side length 2 , and its corners are at $( 0,0 ) , ( 2,0 ) , ( 2,2 )$, and $( 0,2 )$. Charlie's first cut is a straight line segment from the point $( x , y )$ to $( x , 0 )$, where $0 \leqslant x \leqslant 2$ and $0 \leqslant y \leqslant 2$.
Charlie plans to make a second straight cut from the point $( x , y )$ to a point $( 0 , k )$ somewhere on the left-hand edge of the cake. This will make a slice of cake which is bounded to the left of the first cut and bounded below the second cut. [Figure]
(i) Find the area of the slice of cake in terms of $x , y$, and $k$. Check your expression by verifying that if $x = 1$ and $y = 1$, then choosing $k = 1$ gives a slice of cake with area 1 .
(ii) Find another point ( $x , y$ ) on the cake such that choosing $k = 1$ gives a slice of cake with area 1 .
(iii) Show that it is only possible to choose a value of $k$ that gives a slice of cake with area 1 if both $x y \leqslant 2$ and $x ( 2 + y ) \geqslant 2$.
(iv) Sketch the region $R$ of the cake for which both inequalities in part (iii) hold, indicating any relevant points on the edges of the cake.
(v) Charlie may instead plan to make the second straight cut from $( x , y )$ to a point $( m , 2 )$ on the top edge of the cake in order to make a slice bounded to the left of the two cuts. Find two necessary and sufficient inequalities for $x$ and $y$ which must both hold in order for this to give a slice of area 1 for some value of $m$. Sketch the region of the cake for which both inequalities hold.
This page has been intentionally left blank

5. For ALL APPLICANTS.

A triangular triple is a triple of positive integers ( $a , b , c$ ) such that we can construct a triangle with sides of length $a , b$ and $c$. This means that the sum of any two of the numbers is strictly greater than the third; so if $a \leqslant b \leqslant c$, then it is equivalent to requiring $a + b > c$. For example, ( $3,3,3$ ) and ( $4,5,3$ ) are triangular triples, but ( $1,3,2$ ) and ( $3,3,6$ ) are not. For any positive integer $P$, we define $f ( P )$ to be the number of triangular triples such that the perimeter $a + b + c$ is equal to $P$. Triples with the same numbers, but in a different order, are counted as being distinct. So $f ( 12 ) = 10$, because there are 10 triangular triples with perimeter 12, shown below:

$( 3,4,5 )$	$( 3,5,4 )$	$( 4,3,5 )$	$( 4,5,3 )$	$( 5,3,4 )$	$( 5,4,3 )$
$( 2,5,5 )$	$( 5,2,5 )$	$( 5,5,2 )$
$( 4,4,4 )$

(i) Write down the values of $f ( 3 ) , f ( 4 ) , f ( 5 )$ and $f ( 6 )$.
(ii) If ( $a , b , c$ ) is a triangular triple, show that ( $a + 1 , b + 1 , c + 1$ ) is also a triangular triple.
(iii) If ( $x , y , z$ ) is a triangular triple, with $x + y + z$ equal to an even number greater than or equal to 6 , show that each of $x , y , z$ is at least 2 and that $( x - 1 , y - 1 , z - 1 )$ is also a triangular triple.
(iv) Using the previous two parts, prove that for any positive integer $k \geqslant 3$,
$$f ( 2 k - 3 ) = f ( 2 k )$$
(v) We will now consider the case where $P \geqslant 6$ is even, and we will write $P = 2 S$.
(a) Show that in this case ( $a , b , c$ ) is a triangular triple with $a + b + c = P$ if and only if each of $a , b , c$ is strictly smaller than $S$.
(b) For any $a$ such that $2 \leqslant a \leqslant S - 1$, show that the number of possible values of $b$ such that $( a , b , P - a - b )$ is a triangular triple is $a - 1$. Hence find an expression for $f ( P )$ for any even $P \geqslant 6$.
(vi) Find $f ( 21 )$.
This page has been intentionally left blank

6. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { MATHEMATICS \& COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.

Distinct numbers are arranged in an $m \times n$ rectangular table with $m$ rows and $n$ columns so that in each row the numbers are in increasing order (left to right), and in each column the numbers are in increasing order (top to bottom). Such a table is called a sorted table and each location of the table containing a number is called a cell. Two examples of sorted tables with 3 rows and 4 columns (and thus $3 \times 4 = 12$ cells) are shown below.

3	12	33	64
15	26	37	78
19	40	51	92

5	22	53	68
18	36	67	78
19	45	81	92

We index the cells of the table with a pair of integers $( i , j )$, with the top-left corner being $( 1,1 )$ and the bottom-right corner being $( m , n )$. Observe that the smallest entry in a sorted table can only occur in cell $( 1,1 )$; however, note that the second smallest entry can appear either in cell ( 1,2 ), as in the first example above, or in cell ( 2,1 ) as in the second example above.
(i) (a) Assuming that $m , n \geqslant 3$, where in an $m \times n$ sorted table can the third-smallest entry appear?
(b) For any $k \geqslant 4$ satisfying $m , n \geqslant k$, where in an $m \times n$ sorted table can the $k ^ { \text {th } }$ smallest entry appear? Justify your answer.
(ii) Given an $m \times n$ sorted table, consider the problem of determining whether a particular number $y$ appears in the table. Outline a procedure that inspects at most $m + n - 1$ cells in the table, and that correctly determines whether or not $y$ appears in the table. Briefly justify why your procedure terminates correctly in no more than $m + n - 1$ steps. [0pt] [Hint: As the first step, consider inspecting the top-right cell.]
(iii) Consider an $m \times n$ table, say $A$, which might not be sorted; an example is shown below. Obtain table $B$ from $A$ by re-arranging the entries in each row so that they are in sorted order. Then obtain table $C$ from $B$ by re-arranging the entries in each column so that they are in sorted order. Fill in tables $B$ and $C$ here:
\begin{table}[h]
$A$ :

33	92	46	24
25	26	37	8
49	40	81	22

\end{table}
$C$ :
$B$ : [Figure]
[Figure]
(iv) Show that for any $m \times n$ table $A$, performing the two operations from part (iii) results in a sorted table $C$.
This page has been intentionally left blank

7. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.

Throughout this question, all functions will be Boolean functions of Boolean input variables. A Boolean variable can be either 0 or 1 . A Boolean function may have one or more Boolean input variables, and the output of a Boolean function is also either 0 or 1 . Three elementary Boolean functions are defined as follows:

• The function $\min \left( x _ { 1 } , \ldots , x _ { k } \right)$ can take any number of inputs. It outputs the value 1 exactly when each of its inputs is 1 , that is the output of the function is the minimum value among its inputs.
• The function $\max \left( x _ { 1 } , \ldots , x _ { k } \right)$ can take any number of inputs. It outputs the value 1 exactly when at least one of its inputs is 1 , that is the output of the function is the maximum value among its inputs.
• The function flip takes a single input and is defined as flip $\left( x _ { 1 } \right) = 1 - x _ { 1 }$.

First we will consider Boolean functions obtained by combining the three elementary Boolean functions. One such function is shown below:
$$f \left( x _ { 1 } , x _ { 2 } , x _ { 3 } \right) = \min \left( \max \left( x _ { 1 } , x _ { 2 } , x _ { 3 } \right) , \operatorname { flip } \left( \min \left( x _ { 1 } , x _ { 2 } , x _ { 3 } \right) \right) \right) .$$
(i) Describe in words when the function $f$ outputs 1 and when it outputs 0 .
(ii) The function majority $\left( x _ { 1 } , \ldots , x _ { k } \right)$ takes $k$ inputs and outputs 1 exactly when strictly greater than $k / 2$ of its inputs are 1 . Explain how you could combine elementary Boolean functions to obtain the following functions:
(a) majority $\left( x _ { 1 } , x _ { 2 } \right)$
(b) majority $\left( x _ { 1 } , x _ { 2 } , x _ { 3 } \right)$
Now we will consider Boolean functions that can be obtained by combining only majority functions.
(iii) There are exactly 16 distinct Boolean functions of two input variables. Some of these can be represented using only majority functions that take 3 inputs; the use of 0 or 1 as fixed inputs to majority is permitted. For example, majority $\left( x _ { 1 } , x _ { 2 } , 1 \right)$ represents the function $\max \left( x _ { 1 } , x _ { 2 } \right)$. Find any four other Boolean functions of two variables that can be represented by combining one or more majority functions of 3 inputs. Write your answers in terms of majority functions.
(iv) Give an example of a Boolean function $g$ of two input variables that cannot be represented by combining majority functions (of any number of inputs). You should write your answer by explicitly specifying $g ( 0,0 ) , g ( 0,1 ) , g ( 1,0 )$ and $g ( 1,1 )$. Justify your answer.
In the last part, you may express Boolean functions by combining any of the elementary Boolean functions or the majority function.
(v) Consider four input variables $x _ { 1 } , x _ { 2 } , x _ { 3 } , x _ { 4 }$. Let $z _ { 1 } = \min \left( x _ { 1 } , x _ { 2 } \right) , z _ { 2 } = \min \left( x _ { 2 } , x _ { 3 } \right)$, $z _ { 3 } = \min \left( x _ { 3 } , x _ { 4 } \right) , z _ { 4 } = \min \left( x _ { 4 } , x _ { 1 } \right)$. It is sometimes possible to represent a function $s \left( x _ { 1 } , x _ { 2 } , x _ { 3 } , x _ { 4 } \right)$ using a function $t \left( z _ { 1 } , z _ { 2 } , z _ { 3 } , z _ { 4 } \right)$. For example, $\min \left( x _ { 1 } , x _ { 2 } , x _ { 3 } , x _ { 4 } \right) = \min \left( z _ { 1 } , z _ { 2 } , z _ { 3 } , z _ { 4 } \right)$, as both functions output 1 if and only if all four $x _ { i }$ are 1 . Can you represent the following functions of inputs $x _ { 1 } , x _ { 2 } , x _ { 3 } , x _ { 4 }$ as some Boolean function of inputs $z _ { 1 } , z _ { 2 } , z _ { 3 } , z _ { 4 }$ ? Justify your answers.
(a) majority $\left( x _ { 1 } , x _ { 2 } , x _ { 3 } , x _ { 4 } \right)$.
(b) The function parity $\left( x _ { 1 } , x _ { 2 } , x _ { 3 } , x _ { 4 } \right)$ which outputs 1 exactly when an odd number of its inputs are 1 .
This page has been intentionally left blank
This page has been intentionally left blank [Figure]