2. For ALL APPLICANTS.

(i) Suppose $x , y$, and $z$ are whole numbers such that $x ^ { 2 } - 19 y ^ { 2 } = z$. Show that for any such $x , y$ and $z$, it is true that
$$\left( x ^ { 2 } + N y ^ { 2 } \right) ^ { 2 } - 19 ( 2 x y ) ^ { 2 } = z ^ { 2 }$$
where $N$ is a particular whole number which you should determine.
(ii) Find $z$ if $x = 13$ and $y = 3$. Hence find a pair of whole numbers ( $x , y$ ) with $x ^ { 2 } - 19 y ^ { 2 } = 4$ and with $x > 2$.
(iii) Hence find a pair of positive whole numbers $( x , y )$ with $x ^ { 2 } - 19 y ^ { 2 } = 1$ and with $x > 1$.
Is your solution the only such pair of positive whole numbers $( x , y )$ ? Justify your answer.
(iv) Prove that there are no whole number solutions $( x , y )$ to $x ^ { 2 } - 25 y ^ { 2 } = 1$ with $x > 1$.
(v) Find a pair of positive whole numbers $( x , y )$ with $x ^ { 2 } - 17 y ^ { 2 } = 1$ and with $x > 1$.
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.
(i) Sketch $y = \left( x ^ { 2 } - 1 \right) ^ { n }$ for $n = 2$ and for $n = 3$ on the same axes, labelling any points that lie on both curves, or that lie on either the $x$-axis or the $y$-axis.
(ii) Without calculating the integral explicitly, explain why there is no positive value of $a$ such that $\int _ { 0 } ^ { a } \left( x ^ { 2 } - 1 \right) ^ { n } \mathrm {~d} x = 0$ if $n$ is even.
If $n > 0$ is odd we will write $n = 2 m - 1$ and define $a _ { m } > 0$ to be the positive real number that satisfies
$$\int _ { 0 } ^ { a _ { m } } \left( x ^ { 2 } - 1 \right) ^ { 2 m - 1 } \mathrm {~d} x = 0$$
if such a number exists.
(iii) Explain why such a number $a _ { m }$ exists for each whole number $m \geqslant 1$.
(iv) Find $a _ { 1 }$.
(v) Prove that $\sqrt { 2 } < a _ { 2 } < \sqrt { 3 }$.
(vi) Without calculating further integrals, find the approximate value of $a _ { m }$ when $m$ is a very large positive whole number. You may use without proof the fact that $\int _ { 0 } ^ { \sqrt { 2 } } \left( x ^ { 2 } - 1 \right) ^ { 2 m - 1 } \mathrm {~d} x < 0$ for any sufficiently large whole number $m$.
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.
(i) Sketch the graph of $y = \sqrt { x } - \frac { x } { 4 }$ for $x \geqslant 0$, and find the coordinates of the turning point.
(ii) Describe in words how the graph of $y = \sqrt { 4 x + 1 } - x - 1$ for $x \geqslant - \frac { 1 } { 4 }$ is related to the graph that you sketched in part (i). Write down the coordinates of the turning point of this new graph.
Point $A$ is at $( - 1,0 )$ and point $B$ is at $( 1,0 )$. Curve $C$ is defined to be all points $P$ that satisfy the equation $| A P | \times | B P | = 1$, that is; the distance from $P$ to $A$, multiplied by the distance from $P$ to $B$, is 1 .
(iii) Find all points that lie on both the $x$-axis and also on the curve $C$.
(iv) Find an equation in the form $y = f ( x )$ for the part of the curve $C$ in the region where $x > 0$ and $y > 0$. You should explicitly determine the function $f ( x )$.
(v) Use part (ii) to determine the coordinates of any turning points of the curve $C$ in the region where $x > 0$ and $y > 0$.
(vi) Sketch the curve $C$, including any parts of the curve with $x < 0$ or $y < 0$ or both.
This page has been intentionally left blank

5. For ALL APPLICANTS.

Alice is participating in a TV game show where $n$ distinct items are placed behind $n$ closed doors. The game proceeds as follows. Alice picks a door $i$ which is opened and the item behind it is revealed. Then the door is shut again and the host secretly swaps the item behind door $i$ with the item behind one of the neighbouring doors, $i - 1$ or $i + 1$. If Alice picks door 1, the host has to then swap the item with the one behind door 2; similarly, if Alice picks door $n$, the host has to swap the item with the one behind door $n - 1$. Alice then gets to pick any door again, and the process repeats for a certain fixed number of rounds. At the end of the game, Alice wins all the items that were revealed to her.
As a concrete example, suppose $n = 3$, and if the original items behind the three doors were ( $a _ { 1 } , a _ { 2 } , a _ { 3 }$ ), then if first Alice picks door 2 , the arrangement after the host has swapped items could be either $\left( a _ { 2 } , a _ { 1 } , a _ { 3 } \right)$ or $\left( a _ { 1 } , a _ { 3 } , a _ { 2 } \right)$. So if Alice was allowed to pick twice, had she chosen door 2 followed by door 1, in the former case she would only get the item $a _ { 2 }$, whereas in the latter she would get items $a _ { 2 }$ and $a _ { 1 }$. Alice's aim is to find a sequence of door choices that guarantee her winning a large number of items, no matter how the swaps were performed.
(i) For $n = 13$, give an increasing sequence of length 7 of distinct doors that Alice can pick that guarantees she wins 7 items.
(ii) For any $n$ of the form $2 k + 1$, give a strategy to pick an increasing sequence of $k + 1$ distinct doors that Alice can use to guarantee that she wins $k + 1$ items. Briefly justify your answer.
(iii) For $n = 13$, give a sequence of length 10 of doors that Alice can pick that guarantees she wins 10 items.
(iv) For any $n$ of the form $3 k + 1$, give a strategy to pick a sequence of $2 k + 2$ doors that Alice can use to guarantee that she wins $2 k + 2$ items. Briefly justify your answer.
(v) (a) For $n = 3$, give a sequence of length 3 of doors that Alice can pick that guarantees she wins all 3 items.
(b) For $n = 5$, give a sequence of length 5 of doors that Alice can pick that guarantees she wins all 5 items.
(vi) For $n = 13$, give a sequence of length 11 of doors that Alice can pick that guarantees she wins 11 items.
(vii) For any $n$ of the form $4 k + 1$, give a strategy to pick a sequence of $3 k + 2$ doors that Alice can use to guarantee that she wins $3 k + 2$ items. Briefly justify your answer.
(viii) For $n = 6$, is there a sequence of any length of doors that Alice can choose that will guarantee that she wins all 6 items? Justify your answer.
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.

This question is about influencer networks. An influencer network consists of $n$ influencers denoted by circles, and arrows between them. Throughout this question, each influencer holds one of two opinions, represented by either a - or a □ in the circle. We say that an influencer $A$ follows influencer $B$ if there is an arrow from $B$ to $A$; this indicates that $B$ has ability to influence $A$.
[Figure]
Figure 1
[Figure]
Figure 2
The example in Figure 1 above shows a network with $A$ and $B$ following each other, $B$ and $C$ following each other, and $C$ also following $A$. In this example, initially $B$ and $C$ have opinion □ , while $A$ has opinion $\triangle$. An influencer will change their mind according to the strict majority rule, that is, they change their opinion if strictly more than half of the influencers they are following have an opinion different from theirs. Opinions in an influence network change in rounds. In each round, each influencer will look at the influencers they are following and simultaneously change their opinion at the end of the round according to the strict majority rule. In the above network, after one round, $A$ changes their opinion because the only influencer they are following, $B$, has a differing opinion, and the network becomes as shown in Figure 2 above.
An influencer network with an initial set of opinions is stable if no influencer changes their opinion, and a network (with initial opinions) is eventually stable if after a finite number of rounds it becomes stable. The network in the above example is eventually stable as it becomes stable after one round.
(i) A network of three influencers (without opinions) is shown below. Is this influencer network eventually stable regardless of the initial opinions of the influencers $A$, $B$ and $C$ ? Justify your answer. [Figure]
(ii) Another network of influencers (without opinions) is shown below. Is this influencer network eventually stable regardless of the initial opinions of the influencers? Justify your answer.
[Figure]
( $\triangle ) A$
(iii) A partial network of influencers (without opinions for $B _ { 1 } , \ldots , B _ { 8 }$ ) is shown below. You can add at most six additional influencers, assign any opinion of your choice to the new influencers, and add any arrows to the network to describe follower relationships. Design a network that is eventually stable regardless of initial opinions, and has the property that when it becomes stable $A$ has opinion □ if and only if each of $B _ { 1 } , B _ { 2 } , \ldots , B _ { 8 }$ had opinion □ at the start. Justify your answer.
( $\triangle ) A$ [Figure]
(iv) You are given two influencer networks, $N _ { 1 }$ and $N _ { 2 }$, with disjoint sets of influencers shown below. Both are eventually stable. Suppose one of the influencers from network $N _ { 2 }$ follows the influencer $X$ from the network $N _ { 1 }$. Is the resulting network guaranteed to be eventually stable? Justify your answer. [Figure] [Figure]
(v) (a) Given a network with $n$ influencers, where the arrows are fixed, but you are allowed to assign opinions ( $\triangle$ or $\square$ ) to each influencer, how many possible assignments of opinions is possible?
(b) Given an influencer network and an initial assignment of opinions, explain how you would determine whether the influencer network is eventually stable. Justify your answer.
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.

A data operator is receiving tokens one by one through an input channel. The data operator will receive a total of $n$ tokens, where $n \geqslant 6$, and these are numbered as $1,2 , \ldots , n$. The data operator is required to pass these tokens to the output channel; however they must do so using a valid sequence. A valid sequence is one where all the odd tokens appear first, followed by the even tokens, or the other way round; furthermore all the odd tokens must appear in either increasing or decreasing order, and likewise all the even tokens must appear in increasing or decreasing order. All valid sequences for $n = 6$ are listed below.

135246	135642	531246	531642
246135	246531	642135	642531

The data operator has a storage unit that can hold a sequence, and can perform the following operations as they receive the tokens one by one.

• pass: Input token goes straight to the output channel.
• pop : Instead of using a token from the input, the token from the right end of the storage unit is removed (provided one exists) and sent to the output channel.
• pushL : Input token is pushed in at the left end of the storage unit.
• pushR : Input token is pushed in at the right end of the storage unit.

As an illustrative example, when $n = 6$, the storage and output channel are shown for the following sequence of operations, which results in the valid output sequence 13 5642.

Input Token	Operation	Storage	Output
1	pass	[ ]	1
2	pushR	$[ 2 ]$	1
3	pass	$[ 2 ]$	13
4	pushR	$[ 24 ]$	13
5	pass	$[ 24 ]$	135
6	pass	$[ 24 ]$	1356
	pop	$[ 2 ]$	13564
	pop	[ ]	135642

(i) For $n = 6$, which valid sequences can the data operator achieve?
(ii) For $n \geqslant 6$ and even, how many valid sequences are there? Justify your answer.
(iii) For $n \geqslant 6$ and even, how many valid sequences can be achieved by the data operator? Briefly justify your answer.
(iv) In the remainder of the question, $n \geqslant 9$ is a multiple of 3 . A 3 -valid output sequence is one where among the tokens $1,2 , \ldots , n$, all tokens of the form $3 k$ appear together in increasing or decreasing order, likewise all tokens of the form $3 k + 1$ appear together in increasing or decreasing order, and the same is the case for all tokens of the form $3 k + 2$. As examples, the two sequences on the left below are 3 -valid, whereas the two on the right are not - the first because it mixes groups and the second because although the groups are separate, the tokens of the form $3 k + 2$ are in neither increasing nor decreasing order.

3 -valid	not 3 -valid
147963852	135642789
258147369	285963147

For $n \geqslant 9$ and multiple of 3 , how many 3 -valid sequences of length $n$ are there? Justify your answer.
(v) For $n \geqslant 9$ and multiple of 3, given the input sequence of tokens $1,2 , \ldots , n$, how many 3 -valid sequences can be achieved by the operator using a single storage unit and the operations pass, pop, pushL and pushR? Justify your answer.
This page has been intentionally left blank
This page has been intentionally left blank [Figure]