Let $$f _ { n } ( x ) = \left( 2 + ( - 2 ) ^ { n } \right) x ^ { 2 } + ( n + 3 ) x + n ^ { 2 }$$ where $n$ is a positive integer and $x$ is any real number. (i) Write down $f _ { 3 } ( x )$. Find the maximum value of $f _ { 3 } ( x )$. For what values of $n$ does $f _ { n } ( x )$ have a maximum value (as $x$ varies)? [0pt] [Note you are not being asked to calculate the value of this maximum.] (ii) Write down $f _ { 1 } ( x )$. Calculate $f _ { 1 } \left( f _ { 1 } ( x ) \right)$ and $f _ { 1 } \left( f _ { 1 } \left( f _ { 1 } ( x ) \right) \right)$. Find an expression, simplified as much as possible, for $$f _ { 1 } \left( f _ { 1 } \left( f _ { 1 } \left( \cdots f _ { 1 } ( x ) \right) \right) \right)$$ where $f _ { 1 }$ is applied $k$ times. [Here $k$ is a positive integer.] (iii) Write down $f _ { 2 } ( x )$. The function $$f _ { 2 } \left( f _ { 2 } \left( f _ { 2 } \left( \cdots f _ { 2 } ( x ) \right) \right) \right) ,$$ where $f _ { 2 }$ is applied $k$ times, is a polynomial in $x$. What is the degree of this polynomial?
Computer Science applicants should turn to page 14. Let $$I ( c ) = \int _ { 0 } ^ { 1 } \left( ( x - c ) ^ { 2 } + c ^ { 2 } \right) \mathrm { d } x$$ where $c$ is a real number. (i) Sketch $y = ( x - 1 ) ^ { 2 } + 1$ for the values $- 1 \leqslant x \leqslant 3$ on the axes below and show on your graph the area represented by the integral $I$ (1). (ii) Without explicitly calculating $I ( c )$, explain why $I ( c ) \geqslant 0$ for any value of $c$. (iii) Calculate $I ( c )$. (iv) What is the minimum value of $I ( c )$ (as $c$ varies)? (v) What is the maximum value of $I ( \sin \theta )$ as $\theta$ varies? [Figure]
4. For APPLICANTS IN $\left\{ \begin{array} { l } \text { MATHEMATICS } \\ \text { MATHEMATICS \& STATISTICS } \\ \text { MATHEMATICS \& PHILOSOPHY } \end{array} \right\}$ ONLY.
Mathematics \& Computer Science and Computer Science applicants should turn to page 14. In the diagram below is sketched the circle with centre ( 1,1 ) and radius 1 and a line $L$. The line $L$ is tangential to the circle at $Q$; further $L$ meets the $y$-axis at $R$ and the $x$-axis at $P$ in such a way that the angle $O P Q$ equals $\theta$ where $0 < \theta < \pi / 2$. [Figure] (i) Show that the co-ordinates of $Q$ are $$( 1 + \sin \theta , 1 + \cos \theta ) ,$$ and that the gradient of $P Q R$ is $- \tan \theta$. Write down the equation of the line $P Q R$ and so find the co-ordinates of $P$. (ii) The region bounded by the circle, the $x$-axis and $P Q$ has area $A ( \theta )$; the region bounded by the circle, the $y$-axis and $Q R$ has area $B ( \theta )$. (See diagram.) Explain why $$A ( \theta ) = B ( \pi / 2 - \theta )$$ for any $\theta$. Calculate $A ( \pi / 4 )$. (iii) Show that $$A \left( \frac { \pi } { 3 } \right) = \sqrt { 3 } - \frac { \pi } { 3 } .$$
Let $f ( n )$ be a function defined, for any integer $n \geqslant 0$, as follows: $$f ( n ) = \left\{ \begin{array} { c c }
1 & \text { if } n = 0 \\
( f ( n / 2 ) ) ^ { 2 } & \text { if } n > 0 \text { and } n \text { is even } \\
2 f ( n - 1 ) & \text { if } n > 0 \text { and } n \text { is odd }
\end{array} \right.$$ (i) What is the value of $f ( 5 )$ ? The recursion depth of $f ( n )$ is defined to be the number of other integers $m$ such that the value of $f ( m )$ is calculated whilst computing the value of $f ( n )$. For example, the recursion depth of $f ( 4 )$ is 3 , because the values of $f ( 2 ) , f ( 1 )$, and $f ( 0 )$ need to be calculated on the way to computing the value of $f ( 4 )$. (ii) What is the recursion depth of $f ( 5 )$ ? Now let $g ( n )$ be a function, defined for all integers $n \geqslant 0$, as follows: $$g ( n ) = \left\{ \begin{array} { c c }
0 & \text { if } n = 0 \\
1 + g ( n / 2 ) & \text { if } n > 0 \text { and } n \text { is even } \\
1 + g ( n - 1 ) & \text { if } n > 0 \text { and } n \text { is odd }
\end{array} \right.$$ (iii) What is $g ( 5 )$ ? (iv) What is $g \left( 2 ^ { k } \right)$, where $k \geqslant 0$ is an integer? Briefly explain your answer. (v) What is $g \left( 2 ^ { l } + 2 ^ { k } \right)$ where $l > k \geqslant 0$ are integers? Briefly explain your answer. (vi) Explain briefly why the value of $g ( n )$ is equal to the recursion depth of $f ( n )$.
6. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { MATHEMATICS \& COMPUTER SCIENCE } \end{array} \right\}$ ONLY.
Three people called Alf, Beth, and Gemma, sit together in the same room. One of them always tells the truth. One of them always tells a lie. The other one tells truth or lies at random. In each of the following situations, your task is determine how each person acts. (i) Suppose that Alf says "I always tell lies" and Beth says "Yes, that's true, Alf always tells lies". Who always tells the truth? Who always lies? Briefly explain your answer. (ii) Suppose instead that Gemma says "Beth always tells the truth" and Beth says "That's wrong." Who always tells the truth? Who always lies? Briefly explain your answer. (iii) Suppose instead that Alf says "Beth is the one who behaves randomly" and Gemma says "Alf always lies". Then Beth says "You have heard enough to determine who always tells the truth". Who always tells the truth? Who always lies? Briefly explain your answer.
Suppose we have a collection of tiles, each containing two strings of letters, one above the other. A match is a list of tiles from the given collection (tiles may be used repeatedly) such that the string of letters along the top is the same as the string of letters along the bottom. For example, given the collection $$\left\{ \left[ \frac { \mathrm { AA } } { \mathrm {~A} } \right] , \left[ \frac { \mathrm { B } } { \mathrm { ABA } } \right] , \left[ \frac { \mathrm { CCA } } { \mathrm { CA } } \right] \right\}$$ the list $$\left[ \frac { \mathrm { AA } } { \mathrm {~A} } \right] \left[ \frac { \mathrm { B } } { \mathrm { ABA } } \right] \left[ \frac { \mathrm { AA } } { \mathrm {~A} } \right]$$ is a match since the string AABAA occurs both on the top and bottom. Consider the following set of tiles: $$\left\{ \left[ \frac { \mathrm { X } } { \mathrm { U } } \right] , \left[ \frac { \mathrm { UU } } { \mathrm { U } } \right] , \left[ \frac { \mathrm { Z } } { \mathrm { X } } \right] , \left[ \frac { \mathrm { E } } { \mathrm { ZE } } \right] , \left[ \frac { \mathrm { Y } } { \mathrm { U } } \right] , \left[ \frac { \mathrm { Z } } { \mathrm { Y } } \right] \right\} .$$ (a) What tile must a match begin with? (b) Write down all the matches which use four tiles (counting any repetitions). (c) Suppose we replace the tile $\left[ \frac { \mathrm { E } } { \mathrm { ZE } } \right]$ with $\left[ \frac { \mathrm { E } } { \mathrm { ZZZE } } \right]$. What is the least number of tiles that can be used in a match? How many different matches are there using this smallest numbers of tiles? [0pt] [Hint: you may find it easiest to construct your matches backwards from right to left.] Consider a new set of tiles $\left\{ \left[ \frac { X X X X X X X } { X } \right] , \left[ \frac { X } { X X X X X X X X X X } \right] \right\}$. (The first tile has seven $\mathrm { X } _ { \mathrm { s } }$ on top, and the second tile has ten $\mathrm { X } _ { \mathrm { s } }$ on the bottom.) (d) For which numbers $n$ do there exist matches using $n$ tiles? Briefly justify your answer.