Let $S$ and $T$ denote transformations of the $x y$-plane $$S ( x , y ) = ( x + 1 , y ) , \quad T ( x , y ) = ( - y , x )$$ We will write, for example, $T S$ to denote the composition of applying $S$ then $T$, that is $$T S ( x , y ) = T ( S ( x , y ) )$$ and write $T ^ { n }$ to denote $n$ applications of $T$ where $n$ is a positive integer. (i) Show that $T S ( x , y ) \neq S T ( x , y )$. (ii) For what values of $n$ is it the case that $T ^ { n } ( x , y ) = ( x , y )$ for all $x , y$ ? (iii) Show that applications of $S$ and $T$ in some order can produce the transformation $$U ( x , y ) = ( x - 1 , y )$$ What is the least number of applications (of $S$ and $T$ in total) that can produce $U$ ? Justify your answer. (iv) Show that for any integers $a$ and $b$ there is some sequence of applications of $S$ and $T$ that maps $( 0,0 )$ to $( a , b )$. (v) The parabola $C$ has equation $y = x ^ { 2 } + 2 x + 2$. What is the equation of the curve obtained by applying $S$ to $C$ ? What is the equation of the curve obtained by applying $T$ to $C$ ?
Computer Science and Computer Science \& Philosophy applicants should turn to page 14. Let $g ( x )$ be the function defined by $$g ( x ) = \begin{cases} ( x - 1 ) ^ { 2 } + 1 & \text { if } x \geqslant 0 \\ 3 - ( x + 1 ) ^ { 2 } & \text { if } x \leqslant 0 \end{cases}$$ and for $x \neq 0$ write $m ( x )$ for the gradient of the chord between ( $0 , g ( 0 )$ ) and ( $x , g ( x )$ ). (i) Sketch the graph $y = g ( x )$ for $- 3 \leqslant x \leqslant 3$. (ii) Write down expressions for $m ( x )$ in the two cases $x \geqslant 0$ and $x < 0$. (iii) Show that $m ( x ) + 2 = x$ for $x > 0$. What is the value of $m ( x ) + 2$ when $x < 0$ ? (iv) Explain why $g$ has derivative - 2 at 0 . (v) Suppose that $p < q$ and that $h ( x )$ is a cubic with a maximum at $x = p$ and a minimum at $x = q$. Show that $h ^ { \prime } ( x ) < 0$ whenever $p < x < q$. Suppose that $c$ and $d$ are real numbers and that there is a cubic $h ( x )$ with a maximum at $x = - 1$ and a minimum at $x = 1$ such that $h ^ { \prime } ( 0 ) = - 3 c$ and $h ( 0 ) = d$. (vi) Show that $c > 0$ and find a formula for $h ( x )$ in terms of $c$ and $d$ (and $x$ ). (vii) Show that there are no values of $c$ and $d$ such that the graphs of $y = g ( x )$ and $y = h ( x )$ are the same for $- 3 \leqslant x \leqslant 3$.
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 14. Consider two circles $S _ { 1 }$ and $S _ { 2 }$ centred at $A$ and $B$ and with radii $\sqrt { 6 }$ and $\sqrt { 3 } - 1$, respectively. Suppose that the two circles intersect at two distinct points $C$ and $D$. Suppose further that the two centres $A$ and $B$ are of distance 2 apart. The sketch below is not to scale. [Figure] (i) Find the angle $\angle C B A$, and deduce that $A$ and $B$ lie on the same side of the line $C D$. (ii) Show that $C D$ has length $3 - \sqrt { 3 }$ and hence calculate the angle $\angle C A D$. (iii) Show that the area of the region lying inside the circle $S _ { 2 }$ and outside of the circle $S _ { 1 }$ (that is the shaded region in the picture) is equal to $$\frac { \pi } { 6 } ( 5 - 4 \sqrt { 3 } ) + 3 - \sqrt { 3 } .$$ (iv) Suppose that a line through $C$ is drawn such that the total area covered by $S _ { 1 }$ and $S _ { 2 }$ is split into two equal areas. Let $E$ be the intersection of this line with $S _ { 1 }$ and $x$ denote the angle $\angle C A E$. You may assume that $E$ lies on the larger $\operatorname { arc } C D$ of $S _ { 1 }$. Write down an equation which $x$ satisfies and explain why there is a unique solution $x$.
Let $n$ be a positive integer. An $n$-brick is a rectangle of height 1 and width $n$. A 1 -tower is defined as a 1 -brick. An $n$-tower, for $n \geqslant 2$, is defined as an $n$-brick on top of which exactly two other towers are stacked: a $k _ { 1 }$-tower and a $k _ { 2 }$-tower such that $1 \leqslant k _ { 1 } \leqslant n - 1$ and $k _ { 1 } + k _ { 2 } = n$. The $k _ { 1 }$-tower is placed to the left of the $k _ { 2 }$-tower so that side-by-side they fit exactly on top of the $n$-brick. For example, here is a 4 -tower: [Figure] (i) Draw the four other 4 -towers. (ii) What is the maximum height of an $n$-tower? Justify your answer. (iii) The area of a tower is defined as the sum of the widths of its bricks. For example, the 4 -tower drawn above has area $4 + 4 + 3 + 2 = 13$. Give an expression for the area of an $n$-tower of maximum height. (iv) Show that there are infinitely many $n$ such that there is an $n$-tower of height exactly $1 + \log _ { 2 } n$. (v) Write $t _ { n }$ for the number of $n$-towers. We have $t _ { 1 } = 1$. For $n \geqslant 2$ give a formula for $t _ { n }$ in terms of $t _ { k }$ for $k < n$. Use your formula to compute $t _ { 6 }$. (vi) Show that $t _ { n }$ is odd if and only if $t _ { 2 n }$ is odd.
A positive rational number $q$ is expressed in friendly form if it is written as a finite sum of reciprocals of distinct positive integers. For example, $\frac { 4 } { 5 } = \frac { 1 } { 2 } + \frac { 1 } { 4 } + \frac { 1 } { 20 }$. (i) Express the following numbers in friendly form: $\frac { 2 } { 3 } , \frac { 2 } { 5 } , \frac { 23 } { 40 }$. (ii) Let $q$ be a rational number with $0 < q < 1$, and $m$ be the smallest natural number such than $\frac { 1 } { m } \leqslant q$. Suppose $q = \frac { a } { b }$ and $q - \frac { 1 } { m } = \frac { c } { d }$ in their lowest terms. Show that $c < a$. (iii) Suggest a procedure by which any rational $q$ with $0 < q < 1$ can be expressed in friendly form. Use the result in part (ii) to show that the procedure always works, generating distinct reciprocals and finishing within a finite time. (iv) Demonstrate your procedure by finding a friendly form for $\frac { 4 } { 13 }$. (v) Assuming that $\sum _ { n = 1 } ^ { N } \frac { 1 } { n }$ increases without bound as $N$ becomes large, show that every positive rational number can be expressed in friendly form.
7. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.
A character in a video game is collecting the magic coins that are attached to a cliff face. The character starts at the bottom left corner $S$ and must reach the top right corner $E$. One point is scored for each coin $C$ that is collected on the way, and the aim is to reach the top right corner with the highest possible score. At each step the character may move either one cell to the right or one cell up, but never down or to the left. [Figure] (i) Let $c ( i , j ) = 1$ if there is a coin at position $( i , j )$, and $c ( i , j ) = 0$ otherwise. Describe how the maximum score $m ( i , j )$ achievable on reaching position $( i , j )$, where $i \geqslant 2$ and $j \geqslant 2$, can be determined in terms of the maximum scores $m ( i , j - 1 )$ and $m ( i - 1 , j )$ achievable at the positions immediate below and to the left. Briefly justify your answer. (ii) Use the result from part (i) to fill in each cell in the diagram above to show the maximum score achievable on reaching that cell. What is the maximum score achievable in the game? A spare copy of the diagram appears at the end of the question. (iii) Given the array of scores $m ( i , j )$, describe a method for tracing backwards from $E$ to $S$ a path that, if followed in a forward direction by the character, would achieve the maximum score. Draw one such path across the cliff. (iv) With the pattern of coins shown, how many different paths from $S$ to $E$ achieve the maximum score? Describe a method for computing the number of such paths. [Figure] End of last question 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 [Figure]