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.

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

(i) $\mathrm { A } , \mathrm { B }$ and C are three people. One of them is a liar who always tells lies, another is a saint who always tells the truth, and the third is a switcher who sometimes tells the truth and sometimes lies. They make the following statements:
A: I am the liar.
B : A is the liar. C: I am not the liar. Who is the liar among $\mathrm { A } , \mathrm { B }$ and C ? Briefly explain your answer.
(ii) P , Q and R are three more people, one a liar, one a saint, and the third a contrarian who tells a lie if he is the first to speak or if the preceding speaker told the truth, but otherwise tells the truth. They make the following statements: $\mathrm { P } : \mathrm { Q }$ is the liar. $\mathrm { Q } : \mathrm { R }$ is the liar. $\mathrm { R } : \mathrm { P }$ is the liar. Who is the liar among P, Q and R? Briefly explain your answer.
(iii) $\mathrm { X } , \mathrm { Y }$ and Z are three more people, one a liar, one a switcher and one contrarian. They make the following statements: $\mathrm { X } : \mathrm { Y }$ is the liar. $\mathrm { Y } : \mathrm { Z }$ is the liar. $\mathrm { Z } : \mathrm { X }$ is the liar. $\mathrm { X } : \mathrm { Y }$ is the liar. $\mathrm { Y } : \mathrm { X }$ is the liar. Who is the liar among $\mathrm { X } , \mathrm { Y }$ and Z ? Briefly explain your answer.

7. For APPLICANTS IN COMPUTER SCIENCE ONLY.

Ox-words are sequences of letters $a$ and $b$ that are constructed according to the following rules: I. The sequence consisting of no letters is an Ox-word. II. If the sequence $W$ is an Ox-word, then the sequence that begins with $a$, followed by $W$ and ending in $b$, written $a W b$, is an Ox-word. III. If the sequences $U$ and $V$ are Ox-words, then the sequence $U$ followed by $V$, written $U V$, is an Ox-word.
All Ox-words are constructed using these rules. The length of an Ox-word is the number of letters that occur in it. For example $a a b b$ and $a b a b$ are Ox-words of length 4.
(i) Show that every Ox -word has an even length.
(ii) List all Ox-words of length 6 .
(iii) Let $W$ be an Ox-word. Is the number of occurrences of $a$ in $W$ necessarily equal to the number of occurrences of $b$ in $W$ ? Justify your answer.
You may now assume that every Ox-word (of positive length) can be written uniquely in the form $a W b W ^ { \prime }$ where $W$ and $W ^ { \prime }$ are Ox-words.
(iv) For $n \geqslant 0$, let $C _ { n }$ be the number of Ox-words of length $2 n$. Find an expression for $C _ { n + 1 }$ in terms of $C _ { 0 } , C _ { 1 } , \cdots , C _ { n }$. Explain your reasoning.

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

(i) Alice, Bob, and Charlie make the following statements:
Alice: Bob is lying. Bob: Charlie is lying. Charlie: $1 + 1 = 2$. Who is telling the truth? Who is lying?. Explain your answer.
(ii) Now Alice, Bob, and Charlie make the following statements:
Alice: Bob is telling the truth. Bob: Alice is telling the truth. Charlie: Alice is lying. What are the possible numbers of people telling the truth? Explain your answer.
(iii) They now make the following statements:
Alice: Bob and Charlie are both lying. Bob: Alice is telling the truth or Charlie is lying (or both). Charlie: Alice and Bob are both telling the truth. Who is telling the truth and who is lying on this occasion? Explain your answer.

7. For APPLICANTS IN COMPUTER SCIENCE ONLY.

Consider sequences of the letters M, X and W. Valid sequences are made up according to the rule that an M and a W can never be adjacent in the sequence. So M, XMXW, and XMMXW are examples of valid sequences, whereas the sequences MW and XWMX are not valid.
(i) Clearly, there are 3 valid sequences of length 1 . List all valid sequences of length 2 .
(ii) Let $g ( n )$ denote the number of valid sequences of length $n$. Further, let $m ( n ) , x ( n )$, $w ( n )$ denote the number of valid sequences of length $n$ that start with an M , an X , a W respectively.
Explain why
$$\begin{aligned} m ( n ) & = w ( n ) , \\ m ( n ) & = m ( n - 1 ) + x ( n - 1 ) \quad \text { for } n > 1 , \\ x ( n ) & = 2 m ( n - 1 ) + x ( n - 1 ) \quad \text { for } n > 1 , \end{aligned}$$
and write down a formula for $g ( n )$ in terms of $m ( n )$ and $x ( n )$. Hence compute $g ( 3 )$, and verify that $g ( 4 ) = 41$.
(iii) Given a sequence using these letters then we say that it is reflexive if the following operation on the sequence does not change it: reverse the letters in the sequence, and then replace each occurrence of M by W and vice versa. So MXW, WXXM and XWXMX are reflexive strings, but MXM and XMXX are not. Let $r ( n )$ be the number of valid, reflexive sequences of length $n$.
If a sequence is reflexive and has odd length, what must the middle letter be? Explain your answer.
Hence, show that
$$r ( n ) = \left\{ \begin{array} { c l } x \left( \frac { n + 1 } { 2 } \right) & \text { if } n \text { is odd } \\ x \left( \frac { n } { 2 } \right) & \text { if } n \text { is even. } \end{array} \right.$$

2. For ALL APPLICANTS.

Suppose that $a , b , c$ are integers such that
$$a \sqrt { 2 } + b = c \sqrt { 3 }$$
(i) By squaring both sides of the equation, show that $a = b = c = 0$. [0pt] [You may assume that $\sqrt { 2 } , \sqrt { 3 }$ and $\sqrt { 2 / 3 }$ are all irrational numbers. An irrational number is one which cannot be written in the form $p / q$ where $p$ and $q$ are integers.]
(ii) Suppose now that $m , n , M , N$ are integers such that the distance from the point $( m , n )$ to $( \sqrt { 2 } , \sqrt { 3 } )$ equals the distance from $( M , N )$ to $( \sqrt { 2 } , \sqrt { 3 } )$.
Show that $m = M$ and $n = N$. Given real numbers $a , b$ and a positive number $r$, let $N ( a , b , r )$ be the number of integer pairs $x , y$ such that the distance between the points $( x , y )$ and $( a , b )$ is less than or equal to $r$. For example, we see that $N ( 1.2,0,1.5 ) = 7$ in the diagram below. [Figure]
(iii) Explain why $N ( 0.5,0.5 , r )$ is a multiple of 4 for any value of $r$.
(iv) Let $k$ be any positive integer. Explain why there is a positive number $r$ such that
$$N ( \sqrt { 2 } , \sqrt { 3 } , r ) = k$$
Turn Over

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

In the questions below, the people involved make statements about each other. Each person is either a saint (S) who always tells the truth or a liar (L) who always lies.
(i) Six people, $P _ { 1 } , P _ { 2 } , \ldots , P _ { 6 }$ sit in order around a circular table with $P _ { 1 }$ sitting to $P _ { 6 }$ 's right, as shown in the diagram below. [Figure]
(a) Suppose all six people say "the person directly opposite me is telling the truth". One possibility is that all six are lying. But, in total, how many different possibilities are there? Explain your reasoning.
(b) Suppose now that all six people say "the person to my left is lying". In how many different ways can this happen? Explain your reasoining.
(ii) Now $n$ people $Q _ { 1 } , Q _ { 2 } , \ldots , Q _ { n }$ sit in order around a circular table with $Q _ { 1 }$ sitting to $Q _ { n }$ 's right.
(a) Suppose that all $n$ people make the statement "the person on my left is lying and the person on my right is telling the truth". Explain why everyone is lying.
(b) Suppose now that every person makes the statement "either the people to my left and right are both lying or both are telling the truth". If at least one person is lying, show that $n$ is a multiple of three.
Turn Over

7. For APPLICANTS IN COMPUTER SCIENCE ONLY.

In a game of Cat and Mouse, a cat starts at position 0 , a mouse starts at position $m$ and the mouse's hole is at position $h$. Here $m$ and $h$ are integers with $0 < m < h$. By way of example, a starting position is shown below where $m = 7$ and $h = 12$. [Figure]
With each turn of the game, one of the mouse or cat (but not both) advances one position towards the hole on the condition that the cat is always strictly behind the mouse and never catches it. The game ends when the mouse reaches the safety of its hole at position $h$.
This question is about calculating the number, $g ( h , m )$, of different sequences of moves that make a game of Cat and Mouse.
Let $C$ denote a move of the cat and $M$ denote a move of the mouse. Then, for example, $g ( 3,1 ) = 2$ as $M M$ and $M C M$ are the only possible games. Also $C M C C M$ is not a valid game when $h = 4$ and $m = 2$ as the mouse would be caught on the fourth turn.
(i) Write down the five valid games when $h = 4$ and $m = 2$.
(ii) Explain why $g ( h , h - 1 ) = h - 1$ for $h \geqslant 2$.
(iii) Explain why $g ( h , 2 ) = g ( h , 1 )$ for $h \geqslant 3$.
(iv) By considering the possible first moves of a game, explain why
$$g ( h , m ) = g ( h , m + 1 ) + g ( h - 1 , m - 1 ) \quad \text { when } 1 < m < h - 1 .$$
(v) Below is a table with certain values of $g ( h , m )$ filled in. Complete the remainder of the table and verify that $g ( 6,1 ) = 42$. [Figure]
End of Last Question

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

Alice, Bob, Charlie and Diane are playing together when one of them breaks a precious vase. They all know who broke the vase. When questioned they make the following statements:
Alice: It was Bob. Bob: It was Diane. Charlie: It was not me. Diane: What Bob says is wrong. Each statement is either true or false.
(i) Explain why at least one of the four must be lying.
(ii) Explain why at least one of them must be telling the truth.
(iii) Let us suppose that exactly one of the four is lying, so the other three are telling the truth. Who is lying? Who did break the vase? Explain your answer.
(iv) Let us now suppose that exactly one of the four is telling the truth, so the other three are lying. Who is telling the truth? Who did break the vase? Explain your answer.
(v) Let us now suppose that two of the statements are true and two are false. List the people who might now have broken the vase. Justify your answers.
(vi) Hence show that if we don't know how many of the four statements are true, then any one of the four could have broken the vase.

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

Alice and Bob have a large bag of coins which they use to play a game called HT-2. In this game, Alice and Bob take turns placing one coin at a time on the table, each to the right of the previous one; thus they build a row of coins that grows to the right. Alice always places the first coin. Each coin is placed head-up (H) or tail-up (T), and cannot be flipped or moved once it has been placed.
A player loses the game if he or she places a coin that results in two adjacent coins having the same pattern of heads and tails as another adjacent pair somewhere in the row (reading a pattern from left to right). For example, Bob has lost this game by producing a second instance of HT (where $a$ and $b$ denote coins placed by Alice and Bob respectively):
$$\begin{array} { l l l l l l } a & b & a & b & a & b \\ H & H & T & T & H & T \end{array}$$
and Alice has lost this game by producing a second instance of TT (overlapping pairs can count as repeats):
$$\begin{array} { c c c c c } a & b & a & b & a \\ T & H & T & T & T \end{array}$$
(i) What is the smallest number of coins that might be placed in a game of HT-2 (including the final coin that causes a player to lose)? What is the largest number? Justify each answer.
(ii) Bob can always win a game of HT-2 by adopting a particular strategy. Describe the strategy.
For any positive integer $n$, there is a game HT- $n$ with the same rules as HT-2, except that the game is lost by a player who creates an unbroken sequence of $n$ heads and tails that appears elsewhere in the row. For example, Bob has lost this game of HT-3 by producing a second instance of THT:
$$\begin{array} { c c c c c c c c } a & b & a & b & a & b & a & b \\ H & H & T & T & H & T & H & T \end{array}$$
(iii) Suppose $n$ is odd, and Bob chooses to play by always duplicating Alice's previous play (and Alice knows that this is Bob's strategy). Show that Alice can always win.
In these games, a maximum time of one minute is allowed for each turn.
(iv) Can we be certain that a game of HT-6 will be finished within two hours? Justify your answer.
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

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

Alice [Figure]
Bob [Figure]
Charlie [Figure]
Alice, Bob and Charlie are well-known expert logicians; they always tell the truth. They are sat in a row, as illustrated above. In each of the scenarios below, their father puts a red or blue hat on each of their heads. Alice can see Bob's and Charlie's hats, but not her own; Bob can see only Charlie's hat; Charlie can see none of the hats. All three of them are aware of this arrangement.
(i) Their father puts a hat on each of their heads and says: "Each of your hats is either red or blue. At least one of you has a red hat." Alice then says "I know the colour of my hat." What colour is each person's hat? Explain your answer.
(ii) Their father puts a new hat on each of their heads and again says: "Each of your hats is either red or blue. At least one of you has a red hat." Alice then says "I don't know the colour of my hat." Bob then says "I don't know the colour of my hat." What colour is Charlie's hat? Explain your answer.
(iii) Their father puts a new hat on each of their heads and says: "Each of your hats is either red or blue. At least one of you has a red hat, and at least one of you has a blue hat." Alice says "I know the colour of my hat." Bob then says "Mine is red." What colour is each person's hat? Explain your answer.
(iv) Their father puts a new hat on each of their heads and says: "Each of your hats is either red or blue. At least one of you has a red hat, and at least one of you has a blue hat." Alice then says "I don't know the colour of my hat." Bob then says "My hat is red". What colour is Charlie's hat? Explain your answer.
(v) Their father puts a new hat on each of their heads and says: "Each of your hats is either red or blue. Two of you who are seated adjacently both have red hats." Alice then says "I don't know the colour of my hat." What colour is Charlie's hat? Explain your answer.

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

Amy and Brian play a game together, as follows. They take it in turns to write down a number from the set $\{ 0,1,2 \}$, with Amy playing first. On each turn (except Amy's first turn), the player must not repeat the number just played by the previous player.
In their first version of the game, Brian wins if, after he plays, the sum of all the numbers played so far is a multiple of 3 . For example, Brian will win after the sequence

2,0

1,2

1,0

(where we draw a box around each round) because the sum of the numbers is 6. Amy wins if Brian has not won within five rounds; for example, Amy wins after the sequence

2,0

1,2

1,2

0,2

1,2

(i) Show that if Amy starts by playing either 1 or 2 , then Brian can immediately win.
(ii) Suppose, instead, Amy starts by playing 0. Show that Brian can always win within two rounds.
They now decide to change the rules so that Brian wins if, after he plays, the sum of all the numbers played so far is one less than a multiple of 3. Again, Amy wins if Brian has not won within five rounds. It is still the case that a player must not repeat the number just played previously.
(iii) Show that if Amy starts by playing either 0 or 2, then Brian can immediately win.
(iv) Suppose, instead, Amy starts by playing 1. Explain why it cannot benefit Brian to play 2, assuming Amy plays with the best strategy.
(v) So suppose Amy starts by playing 1, and Brian then plays 0. How should Amy play next?
(vi) Assuming both play with the best strategies, who will win the game? Explain your answer.
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

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

Alice, Bob and Charlie are well-known expert logicians; they always tell the truth. In each of the scenarios below, Charlie writes a whole number on Alice and Bob's foreheads. The difference between the two numbers is one: either Alice's number is one larger than Bob's, or Bob's number is one larger than Alice's. Each of Alice and Bob can see the number on the other's forehead, but can't see their own number.
(i) Charlie writes a number on Alice and Bob's foreheads, and says "Each of your numbers is at least 1 . The difference between the numbers is $1 . "$
Alice then says "I know my number." Explain why Alice's number must be 2 . What is Bob's number?
(ii) Charlie now writes new numbers on their foreheads, and says "Each of your numbers is between 1 and 10 inclusive. The difference between the numbers is 1 . Alice's number is a prime." (A prime number is a number greater than 1 that is divisible only by 1 and itself.)
Alice then says "I don't know my number." Bob then says "I don't know my number." What is Alice's number? Explain your answer.
(iii) Charlie now writes new numbers on their foreheads, and says "Each of your numbers is between 1 and 10 inclusive. The difference between the numbers is 1. "
Alice then says "I don't know my number. Is my number a square number?" Charlie then says "If I told you that, you would know your number." Bob then says "I don't know my number." What is Alice's number? Explain your answer.

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

AB-words are "words" formed from the letters $\mathbf { A }$ and $\mathbf { B }$ according to certain rules. The rules are applied starting with the empty word, containing no letters. The basic rules are:
(1) If the current word is $x$, then it can be replaced with the word that starts with $\mathbf { A }$, followed by $x$ and ending with $\mathbf { B }$, written $\mathbf { A } x \mathbf { B }$.
(2) If the current word ends with $\mathbf { B }$, the final $\mathbf { B }$ can be removed.
(i) Show how the word $\mathbf { A A A B }$ can be produced.
(ii) Describe precisely all the words that can be produced with these two rules. Justify your answer. You might like to write $\mathbf { A } ^ { i }$ for the word containing just $i$ consecutive copies of $\mathbf { A }$, and similarly for $\mathbf { B }$; for example $\mathbf { A } ^ { 3 } \mathbf { B } ^ { 2 } = \mathbf { A } \mathbf { A } \mathbf { A B B }$.
We now add a third rule:
(3) Reverse the word, and replace every $\mathbf { A }$ by $\mathbf { B }$, and every $\mathbf { B }$ by $\mathbf { A }$.
For example, applying this rule to $\mathbf { A A A B }$ would give $\mathbf { A B B B }$.
(iii) Describe precisely all the words that can be produced with these three rules. Justify your answer.
Finally, we add a fourth rule:
(4) Reverse the word.
(iv) Show that every word consisting of $\mathbf { A s }$ and $\mathbf { B s }$ can be formed using these four rules. Hint: show how, if we have produced the word $w$, we can produce (a) the word $\mathbf { A } w$, and (b) the word $\mathbf { B } w$; hence deduce the result.
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

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

Alice plays a game 5 times with her friends Sam and Pam. In each game Alice chooses two integers $x$ and $y$ with $1 \leqslant x \leqslant y$. She whispers the sum $x + y$ to Sam, and the product $x \times y$ to Pam, so that neither knows what the other was told. Sam and Pam then have to try to work out what the numbers $x$ and $y$ are. Sam and Pam are well known expert logicians.
(i) In the first game, Pam says "I know $x$ and $y$."
What can we deduce about the values of $x$ and $y$ ? Explain your answer.
(ii) In the second game, Pam says "I don't know what $x$ and $y$ are."
Sam then says "I know $x$ and $y$." Suppose the sum is 4 . What are $x$ and $y$ ? Explain your answer.
(iii) In the third game, Pam says "I don't know what $x$ and $y$ are."
Sam then says "I don't know what $x$ and $y$ are." Pam then says "I now know $x$ and $y$." Suppose the product is 4 . What are $x$ and $y$ ? Explain your answer.
(iv) In the fourth game, Pam says "I don't know what $x$ and $y$ are."
Sam then says "I already knew that." Pam then says "I now know $x$ and $y$." Suppose the product is 8 . What are $x$ and $y$ ? Explain your answer.
(v) Finally, in the fifth game, Pam says "I don't know what $x$ and $y$ are."
Sam then says "I don't know what $x$ and $y$ are." Pam then says "I don't know what $x$ and $y$ are." Sam then says "I now know $x$ and $y$." Suppose the sum is 5 . What are $x$ and $y$ ? Explain your answer.

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

A finite automaton is a mathematical model of a simple computing device. A small finite automaton is illustrated below. [Figure]
A finite automaton has some finite number of states; the above automaton has three states, labelled $s _ { 0 } , s _ { 1 }$ and $s _ { 2 }$. The initial state, $s _ { 0 }$, is indicated with an incoming arrow. The automaton receives inputs (e.g. via button presses), which might cause it to change state. In the example, the inputs are $a$ and $b$. The state changes are illustrated by arrows; for example, if the automaton is in state $s _ { 1 }$ and it receives input $b$, it changes to state $s _ { 0 }$; if it is in state $s _ { 2 }$ and receives either input, it remains in state $s _ { 2 }$. (For each state, there is precisely one out-going arrow for each input.)
Some of the states are defined to be accepting states; in the example, just $s _ { 1 }$ is defined to be an accepting state, represented by the double circle. A word is a sequence of inputs. The automaton accepts a word $w$ if that sequence of inputs leads to an accepting state from the initial state. For example, the above automaton accepts the word $a b a$.
(i) Write down a description of the set of words accepted by the above automaton. A clear but informal description will suffice.
(ii) Suppose we alter the above automaton by swapping accepting and non-accepting states; i.e. we make $s _ { 0 }$ and $s _ { 2 }$ accepting, and make $s _ { 1 }$ non-accepting. Write down a description of the set of words accepted by this new automaton. Again, a clear but informal description will suffice.
(iii) Draw an automaton that accepts all words containing an even number (possibly zero) of $a$ 's and any number of $b$ 's (and no other words).
(iv) Now draw an automaton that accepts all words containing an even number of $a$ 's or an odd number of $b$ 's (and no other words).
Let $a ^ { n }$ represent $n$ consecutive $a$ 's. Let $L$ be the set of all words of the form $a ^ { n } b ^ { n }$ where $n = 0,1,2 , \ldots$; i.e. all words composed of some number of $a$ 's followed by the same number of $b$ 's. We will show that no finite automaton accepts precisely this set of words.
(v) Suppose a particular finite automaton $A$ does accept precisely the words in $L$. Show that if $i \neq j$ then the words $a ^ { i }$ and $a ^ { j }$ must lead to different states of $A$. Hence show that this leads to a contradiction.
This page has been intentionally left blank
This page has been intentionally left blank
This page has been intentionally left blank

2. For ALL APPLICANTS.

(i) Expand and simplify
$$( a - b ) \left( a ^ { n } + a ^ { n - 1 } b + a ^ { n - 2 } b ^ { 2 } + \cdots + a b ^ { n - 1 } + b ^ { n } \right)$$
(ii) The prime number 3 has the property that it is one less than a square number. Are there any other prime numbers with this property? Justify your answer.
(iii) Find all the prime numbers that are one more than a cube number. Justify your answer.
(iv) Is $3 ^ { 2015 } - 2 ^ { 2015 }$ a prime number? Explain your reasoning carefully.
(v) Is there a positive integer $k$ for which $k ^ { 3 } + 2 k ^ { 2 } + 2 k + 1$ is a cube number? Explain your reasoning carefully.
If you require additional space please use the pages at the end of the booklet

5. For ALL APPLICANTS.

The following functions are defined for all integers $a , b$ and $c$ :
$$\begin{aligned} p ( x ) & = x + 1 \\ m ( x ) & = x - 1 \\ s ( x , y , z ) & = \begin{cases} y & \text { if } x \leqslant 0 \\ z & \text { if } x > 0 \end{cases} \end{aligned}$$
(i) Show that the value of
$$s ( s ( p ( 0 ) , m ( 0 ) , m ( m ( 0 ) ) ) , s ( p ( 0 ) , m ( 0 ) , p ( p ( 0 ) ) ) , s ( m ( 0 ) , p ( 0 ) , m ( p ( 0 ) ) ) )$$
is 2 .
Let $f$ be a function defined, for all integers $a$ and $b$, as follows:
$$f ( a , b ) = s ( b , p ( a ) , p ( f ( a , m ( b ) ) ) ) .$$
(ii) What is the value of $f ( 5,2 )$ ?
(iii) Give a simple formula for the value of $f ( a , b )$ for all integers $a$ and all positive integers $b$, and explain why this formula holds.
(iv) Define a function $g ( a , b )$ in a similar way to $f$, using only the functions $p , m$ and $s$, so that the value of $g ( a , b )$ is equal to the sum of $a$ and $b$ for all integers $a$ and all integers $b \leqslant 0$. Explain briefly why your function gives the correct value for all such values of $a$ and $b$.
If you require additional space please use the pages at the end of the booklet

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

The world is divided into two species, vampires and werewolves. Vampires always tell the truth when talking about a vampire, but always lie when talking about a werewolf. Werewolves always tell the truth when talking about a werewolf, but always lie when talking about a vampire. (Note that this does not imply that creatures necessarily lie when speaking to creatures of the other species. Note also that "Zaccaria is a vampire" is a statement about Zaccaria, rather than necessarily about a vampire.)
These facts are well known to both sides, and creatures can tell instinctively which species an individual belongs to.
In your answers to the questions below, you may abbreviate "vampire" and "werewolf" to "V" and "W", respectively.
(i) Azrael says, "Beela is a werewolf." Explain why Azrael must be a werewolf, but that we cannot tell anything about Beela.
(ii) Cesare says, "Dita says 'Elith is a vampire.'" What can we infer about any of the three from this statement? Explain your answer.
(iii) Suppose $N$ creatures (where $N \geq 2$ ) are sitting around a circular table. Each tells their right-hand neighbour, "You lie about your right-hand neighbour." What can we infer about $N$ ? What can we infer about the arrangement of creatures around the table? Explain your answer.
(iv) Consider a similar situation to that in part (iii) (possibly for a different value of $N$ ), except that now each tells their right-hand neighbour, "Your right-hand neighbour lies about their right-hand neighbour." Again, what can we infer about $N$ and the arrangement of creatures around the table? Explain your answer.
If you require additional space please use the pages at the end of the booklet

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

In this question we will study a mechanism for producing a set of words. We will only consider words containing the letters $a$ and/or $b$, and that have length at least 1 . We will make use of variables, which we shall write as capital letters, including a special start variable called $S$. We will also use rules, which show how a variable can be replaced by a sequence of variables and/or letters. Starting with the start variable $S$, we repeatedly replace one of the variables according to one of the rules (in any order) until no variables remain.
For example suppose the rules are
$$S \rightarrow A B , \quad A \rightarrow A A , \quad A \rightarrow a , \quad B \rightarrow b b .$$
We can produce the word $a a b b$ as follows; at each point, the variable that is replaced is underlined:
$$\underline { S } \rightarrow \underline { A } B \rightarrow A \underline { A } B \rightarrow \underline { A } a B \rightarrow a a \underline { B } \rightarrow a a b b .$$
(i) Show that the above rules can be used to produce all words of the form $a ^ { n } b b$ with $n \geq 1$, where $a ^ { n }$ represents $n$ consecutive $a$ 's. Also briefly explain why the rules can be used to produce no other words.
(ii) Give a precise description of the words produced by the following rules.
$$S \rightarrow a b , \quad S \rightarrow a S b .$$
(iii) A palindrome is a word that reads the same forwards as backwards, for example $b b a a b b$. Give rules that produce all palindromes (and no other words).
(iv) Consider the words with the same number of $a$ 's as $b$ 's; for example, $a a b a b b$. Write down rules that produce these words (and no others).
(v) Suppose you are given a collection of rules that produces the words in $L _ { 1 }$, and another collection of rules that produces the words in $L _ { 2 }$. Show how to produce a single set of rules that produce all words in $L _ { 1 }$ or $L _ { 2 }$, or both (and no other words). Hint: you may introduce new variables if you want.
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
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.

[Figure]
Four people $A , B , C , D$ are performing a dance, holding hands in the arrangement shown above. Each dancer is assigned a 1 or a 0 to determine their steps, and there must always be at least a 1 and a 0 in the group of dancers (dancers cannot all dance the same kind of steps). A dancer is off-beat if their assigned number plus the numbers assigned to the people holding hands with them is odd. The entire dance is an off-beat dance if every dancer is off-beat.
(i) In how many ways can the four dancers perform an off-beat dance? Explain your answer.
A new dance starts and two more people, $E$ and $F$, join the dance such that each dancer holds hands with their neighbours to form a ring.
(ii) In how many ways can the ring of six dancers perform an off-beat dance? Explain your answer.
(iii) In a ring of $n$ dancers explain why an off-beat dance can only occur if $n$ is a multiple of 3 .
(iv) For a new dance a ring of $n > 4$ dancers, each holds hands with dancers one person away from them round the ring (so $C$ holds hands with $A$ and $E$ and $D$ holds hands with $B$ and $F$ and so on). For which values of $n$ can the dance be off-beat?
On another planet the alien inhabitants have three (extendible) arms and still like to dance according to the rules above.
(v) If four aliens dance, each holding hands with each other, how many ways can they perform an off-beat dance?
(vi) Six aliens standing in a ring perform a new dance where each alien holds hands with their direct neighbours and the alien opposite them in the ring. In how many ways can they perform an off-beat dance?
If you require additional space please use the pages at the end of the booklet

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

An $n$-fan consists of a row of $n$ points, the tips, in a straight line, together with another point, the hub, that is not on the line. The $n$ tips are joined to each other and to the hub with line segments. For example, the left-hand picture here shows a 6 -fan, [Figure] [Figure]
For a given $n$-fan, an $n$-span is a subset containing all $n + 1$ points and exactly $n$ of the line segments, chosen so that all the points are connected together, with a unique path between any two points. The right-hand picture shows one of many 6 -spans obtained from the given 6 -fan; in this 6 -span, the tips are in "groups" of 3,1 and 2 , with the top "group" containing 3 tips.
(i) Draw all three 2 -spans.
(ii) Draw all 3 -spans.
(iii) By considering the possible sizes of the top group of tips and how the group is connected to the hub, calculate the number of 4 -spans.
(iv) For $n \geqslant 1$ let $z _ { n }$ denote the number of $n$-spans. Give an expression for $z _ { n }$ in terms of $z _ { k }$, where $1 \leqslant k < n$. Use this expression to show that $z _ { 5 } = 55$.
(v) Use this relationship to calculate $z _ { 6 }$.
If you require additional space please use the pages at the end of the booklet
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
M

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

You need to pack several items into your shopping bag, without squashing any item. Suppose each item $i$ has a (positive) weight $w _ { i }$, and a strength $s _ { i }$ which is the maximum weight that can be placed above it without it being squashed. For the purposes of this question, suppose that the items will be arranged one on top of the other within your bag. We will say that a particular packing order is safe if no item is squashed, that is, for each item $i , s _ { i }$ is at least the sum of the $w _ { j }$ corresponding to items $j$ placed above item $i$. For example, suppose we have the following items, packed in the order given

Ordering	Item	$w _ { i }$	$s _ { i }$
Top	Apples	5	6
Middle	Bread	4	4
Bottom	Carrots	12	9

This packing is not safe: the bread is squashed, since the weight above it (5) is greater than its strength (4). However, swapping the apples and the bread gives a safe packing.
(i) Which of the other four orderings of apples, bread, and carrots are safe or unsafe?
(ii) Consider the tactic of packing the items in weight order, with the heaviest at the bottom. Show by giving an example that this might not produce a safe packing order, even if a safe packing order exists.
(iii) Now consider the tactic of packing the items in strength order, with the strongest at the bottom. Again show by giving an example that this might not produce a safe packing order, even if one exists.
(iv) Suppose we have a safe packing order, with item $j$ directly on top of item $i$. Suppose further that
$$w _ { j } - s _ { i } \geqslant w _ { i } - s _ { j }$$
Show that if we swap items $i$ and $j$, we still have a safe packing order.
(v) Hence suggest a practical method of producing a safe packing order if one exists. Explain why your method works. (Listing all possible orderings is not practical.)

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

A simple computer can operate on lists of numbers in several ways.

• Given two lists $a$ and $b$, it can make the join $a + b$, by placing list $b$ after list $a$. For example if

$$a = ( 1,2,3,4 ) \quad \text { and } \quad b = ( 5,6,7 ) \quad \text { then } \quad a + b = ( 1,2,3,4,5,6,7 ) .$$

• Given a list $a$ it can form the reverse sequence $R ( a )$ by listing $a$ in reverse order. For example if

$$a = ( 1,2,3,4 ) \quad \text { then } \quad R ( a ) = ( 4,3,2,1 ) .$$
(i) Given sequences $a$ and $b$, express $R ( a + b )$ as the join of two sequences. What is $R ( R ( a ) )$ ?

• Given a sequence $a$ of length $n$ and $0 \leqslant k \leqslant n$, then the $k$ th shuffle $S _ { k }$ of a moves the first $k$ elements of $a$ to the end of the sequence in reverse order. For example

$$S _ { 2 } ( 1,2,3,4,5 ) = ( 3,4,5,2,1 ) \quad \text { and } \quad S _ { 3 } ( 1,2,3,4,5 ) = ( 4,5,3,2,1 ) .$$
(ii) Given two sequences $a$ and $b$, both of length $k$, express $S _ { k } ( a + b )$ as the join of two sequences. What is $S _ { k } \left( S _ { k } ( a + b ) \right)$ ?
(iii) Now let $a = ( 1,2,3,4,5,6,7,8 )$. Write down
$$S _ { 5 } \left( S _ { 5 } ( a ) \right)$$
as the join of three sequences that are either in order or in reverse order. Show that the sequence $a$ is back in its original order after four $S _ { 5 }$ shuffles.
(iv) Now let $a$ be a sequence of length $n$ with $k \geqslant n / 2$. Prove, after $S _ { k }$ is performed four times, that the sequence returns to its original order.
(v) Give an example to show that when $k < n / 2$, the sequence need not be in its original order after $S _ { k }$ is performed four times. For your example how many times must $S _ { k }$ be performed to first return the sequence to its original order?
This page has been intentionally left blank for candidate use
This page has been intentionally left blank for candidate use
This page has been intentionally left blank for candidate use
This page has been intentionally left blank for candidate use
This page has been intentionally left blank for candidate use
This page has been intentionally left blank for candidate use
This page has been intentionally left blank for candidate use

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]