Consider a figure made by cutting two corners from a rectangle, as in the diagram to the right. The lengths of the sides are
$$\begin{array}{lll} \mathrm{AB} = 11, & \mathrm{BC} = 4, & \mathrm{CD} = 2\sqrt{13} \\ \mathrm{DE} = 5, & \mathrm{EF} = 2\sqrt{5}, & \mathrm{FA} = 6 \end{array}$$
We are to find the area of this figure.
First, extend the sides of the figure as in the diagram and denote the sides forming the right angles by $x, y, u$ and $v$. Then
$$u = \mathbf{A} - y, \quad v = x + \mathbf{B}.$$
Substituting these expressions in the equation $u^2 + v^2 = \mathbf{CD}$ and also using the equation $x^2 + y^2 = \mathbf{EF}$, we obtain
$$x = \mathbf{G}.\, y - \mathbf{H}.$$
Then, since
$$\mathbf{I}y^2 - \mathbf{J} = \mathbf{J}y - \mathbf{K} = 0,$$
we obtain $y = \mathbf{L}$.
From this we have $x = \mathbf{M}$, and further $u = \mathbf{N}$ and $v = \mathbf{O}$. Finally we conclude that the area of this figure is $\mathbf{PQ}$.

Consider the integral expression
$$P = ( x - 1 ) ^ { 2 } ( y + 5 ) + ( 2 x - 3 ) ( y + 4 ) - ( x - 1 ) ^ { 2 } .$$
(1) $P$ can be transformed into
$$P = \left( x ^ { 2 } - \mathbf { K } \right) ( y + \mathbf { L } ) .$$
(2) The pairs $( x , y )$ of integers $x$ and $y$ which give $P = 7$ are
$$( \pm \mathbf { M } , \mathbf { N O P } ) , \quad ( \pm \mathbf { Q } , \mathbf { R S } ) .$$
(3) Let $a$ be a rational number. If $x = \sqrt { 2 } + 2 \sqrt { 3 }$ and $y = a + \sqrt { 6 }$, then the value of $a$ such that the value of $P$ is a rational number is $\mathbf { T U }$.

A natural number $n$ is said to be a perfect square when there exists a natural number $x$ satisfying $n = x ^ { 2 }$. Similarly, $n$ is said to be a perfect cube when there exists a natural number $x$ satisfying $n = x ^ { 3 }$.
In the following two cases, find the natural number $n$ that satisfies the conditions.
(i) $n$ is a perfect square. Furthermore, the number obtained by adding 13 to $n$ is also a perfect square.
(ii) $n$ is a perfect cube. Furthermore, the number obtained by adding 61 to $n$ is also a perfect cube.
First, consider (i). From the definition of a perfect square number, $n$ can be expressed as $n = x ^ { 2 }$, where $x$ is a natural number. In addition, there exists a natural number $y$ such that
$$x ^ { 2 } + 13 = y ^ { 2 } .$$
Since $x < y$, $y - x = \square \mathbf { J }$ and $y + x = \mathbf { K L }$. It follows that
$$x = \mathbf { M } , \quad y = \mathbf { N } ,$$
and finally that $n = \mathbf { O P }$.
Next, consider (ii). Similar to (i), in (ii), there exists a natural number $x$ such that $n = x ^ { 3 }$, and there also exists a natural number $y$ such that
$$x ^ { 3 } + 61 = y ^ { 3 } .$$
When we solve this equation, we obtain
$$x = \mathbf { Q } , \quad y = \mathbf { R } ,$$
and hence the perfect cube $n = \mathbf{ST}$.

Q2 Let $p$ be a prime number, and let $x$ and $y$ be positive integers. Then we are to find all triples of $p$, $x$ and $y$ which satisfy
$$\frac{p}{x} + \frac{7}{y} = p.$$
We can transform this equation into
$$(x - \mathbf{N})(py - \mathbf{OO}) = \mathbf{OP}.$$
From this, we obtain
$$x - \mathbf{N} = \mathbf{Q} \text{ or } \mathbf{R}, \quad (\text{note: have } \mathbf{Q} < \mathbf{R})$$
and hence
$$x = \mathbf{S} \text{ or } \mathbf{T}. \quad (\text{note: have } S < T)$$
First, if $x = S$, then
$$p = \mathbf{U}, \quad y = \mathbf{V}$$
or
$$p = \mathbf{W}, \quad y = \mathbf{X}. \quad (\text{note: have } \mathbf{U} < \mathbf{W})$$
Next, if $x = T$, then
$$p = \mathbf{Y}, \quad y = \mathbf{Z}.$$

Consider the sets $A = \{ 4 m \mid m$ is a natural number $\}$ and $B = \{ 6 m \mid m$ is a natural number $\}$.
(1) For each of the following $\mathbf { L } \sim \square \mathbf { O }$, choose the correct answer from among (0) $\sim$ (3) below.
Let $n$ be a natural number.
(i) $n \in A$ is $\mathbf { L }$ for $n$ to be divisible by 2 .
(ii) $n \in B$ is $\mathbf { M }$ for $n$ to be divisible by 24 .
(iii) $n \in A \cup B$ is $\mathbf { N }$ for $n$ to be divisible by 3 .
(iv) $n \in A \cap B$ is $\mathbf{O}$ for $n$ to be divisible by 12 . (0) a necessary and sufficient condition
(1) a necessary condition but not a sufficient condition
(2) a sufficient condition but not a necessary condition
(3) neither a necessary condition nor a sufficient condition
(2) Let $C = \{ m \mid m$ is a natural number satisfying $1 \leqq m \leqq 100 \}$.
The number of elements which belong to $( \bar { A } \cup \bar { B } ) \cap C$ is $\mathbf { P Q }$, and the number of elements which belong to $\bar { A } \cap \bar { B } \cap C$ is $\mathbf { R S }$. Note that $\bar { A }$ and $\bar { B }$ denote the complements of $A$ and $B$, where the universal set is the set of all natural numbers.

We are to find the natural number $a$ such that $3a + 1$ is a divisor of $a^2 + 5$.
Set $b = 3a + 1$. Then we have $$a^2 + 5 = \frac{b^2 - \mathbf{OO}b + \mathbf{PQ}}{\mathbf{R}}.$$
On the other hand, since $b$ is a divisor of $a^2 + 5$, $a^2 + 5$ can be expressed as $$a^2 + 5 = bc$$ for some natural number $c$. From (1) and (2), we have $$b(\mathbf{S}c - b + \mathbf{IT}) = \mathbf{UV}.$$
This shows that $b$ must also be one of the divisors of UV. Of these, only $b = \mathbf{WX}$ is a number such that $a$ is a natural number. Hence, $a = \mathbf{YZ}$.

Let $a$ and $b$ be natural numbers such that the greatest common divisor of $a$ and $b$ is 3. We are to find the natural numbers $a$ and $b$ such that
$$3 a - 2 b = \ell + 3$$
is satisfied, where $\ell$ is the least common multiple of $a$ and $b$.
When we set $a = 3 p$ and $b = 3 q$, the natural numbers $p$ and $q$ are mutually prime (co-prime), and hence $\ell = \mathbf { N } p q$. Thus using $p$ and $q$, the equality (1) can be transformed to
$$p q - \mathbf { O } p + \mathbf { P } q + \mathbf { Q } = 0 .$$
This can be further transformed to
$$( p + \mathbf { R } ) ( q - \mathbf { S } ) = - \mathbf { S } \mathbf { T } .$$
Among the pairs of integers $p$ and $q$ which satisfy this equation, the pair such that both $a$ and $b$ are natural numbers is
$$p = \mathbf { U } , \quad q = \mathbf { V } ,$$
which gives
$$a = \mathbf { W X } , \quad b = \mathbf { Y } .$$

Let $n$ be a natural number and $a$ be a real number, where $a \neq 0$. Suppose that the integral expression $x ^ { n } + y ^ { n } + z ^ { n } + a ( x y + y z + z x )$ can be expressed as the product of $x + y + z$ and an integral expression $P$ in $x$, $y$ and $z$, i.e.
$$x ^ { n } + y ^ { n } + z ^ { n } + a ( x y + y z + z x ) = ( x + y + z ) P .$$
We are to find the values of $n$ and $a$.
The equality (1) holds for all $x$, $y$ and $z$. So, consider for example, two triples of $x$, $y$ and $z$ that satisfy $x + y + z = 0$:
$$x = y = 1 , \quad z = - \mathbf { A }$$
and
$$x = y = - \frac { \mathbf { B } } { \mathbf { C } } , \quad z = 1 .$$
By substituting each triple in (1), we obtain the following two equations:
$$\left( - \mathbf { A } \right) ^ { n } = \mathbf { D } \text{ a} - \frac{\mathbf{E}}{\mathbf{F}}$$
$$\left( - \frac { \mathbf { B } } { \mathbf { C } } \right) ^ { n } = \frac { \mathbf{E} }{ \mathbf{F} } \text{ a} - \frac { \mathbf { H } } { \mathbf { I } } .$$
From these two equations, we get an equation in $a$. Solving this, we obtain $a = \mathbf { K }$ and hence by the first equation that $n = \mathbf { L }$.
Conversely, when $a = \mathbf{K}$ and $n = \mathbf{L}$, there exists a $P$ such that (1) holds, and hence these values of $a$ and $n$ are the solution.

Let $n$ be a positive integer, and $x$ and $y$ be non-negative integers. We are to examine the solutions of the following equation in $x$ and $y$
$$x ^ { 2 } - y ^ { 2 } = n . \tag{1}$$
First of all, by transforming (1), we obtain
$$( x + y ) ( x - y ) = n . \tag{2}$$
(1) When we find the solutions $( x , y )$ of (1) in the cases where $n = 8$ and $n = 9$, we have that if $n = 8$, then $( x , y ) = ( \mathbf { A } , \mathbf { B } )$, and if $n = 9$, then $( x , y ) = ( \mathbf { C } , \mathbf { D } ) , ( \mathbf { E } , \mathbf { F } )$. Note that you should write the solutions in the order such that $\mathbf{C} \leq \mathbf{E}$.
(2) For each of $\mathbf { G }$ $\sim$ $\mathbf { R }$ in the following sentences, choose the correct answer from among (0) $\sim$ (9) given below.
The following is a proof that (3) given below is the necessary and sufficient condition for (1) to have a solution.
Proof: First, suppose that $( x , y )$ satisfies (1). If $x$ and $y$ are both even or both odd, then both $x + y$ and $x - y$ are $\mathbf { G }$. Hence, by (2) we see that $n$ is a multiple of $\mathbf { H }$.
Next, if one of $x$ and $y$ is even and the other is odd, then both $x + y$ and $x - y$ are $\mathbf{I}$, and hence $n$ is $\mathbf{J}$.
Thus we see that
$$\text{``} n \text{ is a multiple of } \mathbf{H} \text{, or } n \text{ is } \mathbf{J} \text{''} \quad \ldots\ldots (3)$$
is a necessary condition for (1) to have a solution.
Conversely, suppose that $n$ satisfies the condition (3). If $n$ is a multiple of $\mathbf{H}$, then $n$ can be represented as $n = \mathbf{H} \cdot k$, where $k$ is a positive integer. So, if for example we take $x + y = \mathbf { K } \cdot k$ and $x - y = 2$, then $( x , y ) = ( k + \mathbf { L } , k - \mathbf { M } )$, which shows that (1) has a solution.
On the other hand, if $n$ is $\mathbf{J}$, then $n$ can be represented as $n = \mathbf { N } \ell + \mathbf { O }$, where $\ell$ is a non-negative integer. So, if for example we take $x + y = \mathbf { P } \ell + \mathbf { Q }$ and $x - y = 1$, then $( x , y ) = ( \ell + \mathbf { R } , \ell )$, which shows that (1) has a solution.
From the above, we see that the necessary and sufficient condition for (1) to have a solution is (3).
(0) 0 (1) 1 (2) 2 (3) 3 (4) 4 (5) 5 (6) 6 (7) even (8) odd (9) prime

Where $m$ and $n$ are positive integers, consider the rational number
$$r = \frac { m } { 3 } + \frac { n } { 7 } .$$
We are to find $m$ and $n$ such that among all $r$'s satisfying $r < \sqrt { 2 }$, $r$ is closest to $\sqrt { 2 }$.
It is sufficient that among all $m$'s and $n$'s which satisfy the inequality
$$\mathbf { A } m + \mathbf { B } n < \mathbf { CD } \sqrt { 2 }$$
we find the $m$ and $n$ such that $\mathrm { A } m + \mathrm { B } n$ is closest to $\mathrm { CD } \sqrt { 2 }$.
Squaring both sides of (1), we have
$$(\mathrm { A } m + \mathrm { B } n ) ^ { 2 } < \mathbf { EFG } .$$
Here, the greatest square number which is smaller than EFG is $\mathbf{HIJ} = \mathbf{KL}^{2}$. So, let us consider the equation
$$\mathrm { A } m + \mathrm { B } n = \mathrm { KL } .$$
Transforming this equation, we have
$$n = \frac { \mathbf { MN } - \mathbf { O } m } { \mathbf { P } } .$$
Since $n$ is an integer, $\mathbf { MN } - \mathbf { O } m$ is a multiple of $\mathbf { Q }$. Thus, we obtain
$$m = \mathbf { R } , \quad n = \mathbf { S } .$$

Let $m$ and $n$ be positive integers satisfying $0 < m - n\sqrt{2} < 1$. Denote the integral part of $(m + n\sqrt{2})^3$ by $a$ and the fractional part by $b$.
(1) We are to prove that $a$ is an odd number and $(m - n\sqrt{2})^3 = 1 - b$.
If $(m + n\sqrt{2})^3 = p + q\sqrt{2}$, where $p$ and $q$ are integers, then $$p = m^3 + \mathbf{A}mn^2, \quad q = \mathbf{B}m^2n + \mathbf{C}n^3.$$ Thus, we see that $(m - n\sqrt{2})^3 = p - q\sqrt{2}$.
Furthermore, the integral part of $(m - n\sqrt{2})^3$ is $\mathbf{D}$. When we denote its fractional part by $c$, the following two equations hold: $$\left\{\begin{array}{l} p + q\sqrt{2} = a + b \\ p - q\sqrt{2} = c \end{array}\right.$$
From these we obtain $$\mathbf{E} \quad p - a = b + c.$$
Here, since the left side is an integer and the range of values which the right side takes is $\mathbf{F} < b + c < \mathbf{G}$, we see that $$b + c = \mathbf{H}$$
Hence we see that $a = \mathbf{E}p - \mathbf{H}$, which shows that $a$ is an odd number and that $(m - n\sqrt{2})^3 = 1 - b$.
(2) Let us find the values of $m$ and $n$ when $a = 197$.
Since $a = 197$, we see that $p = \mathbf{IJ}$, that is, $m^3 + \mathbf{A}mn^2 = \mathbf{IJ}$. The positive integers $m$ and $n$ satisfying this equation are $$m = \mathbf{K}, \quad n = \mathbf{L}.$$

Consider integers $a$ and $b$ satisfying the equation $$14a + 9b = 147. \tag{1}$$
(1) We are to find the positive integers $a$ and $b$ satisfying equation (1).
Since $$14a = \mathbf{A}(\mathbf{BC} - \mathbf{D}b) \text{ and } 9b = \mathbf{E}(\mathbf{FG} - \mathbf{H}a),$$ $a$ is a multiple of $\mathbf{A}$, and $b$ is a multiple of $\mathbf{E}$.
So, when we set $a = \mathbf{A}m$ and $b = \mathbf{E}n$, where $m$ and $n$ are integers, from (1) we have $$\mathbf{I}m + \mathbf{J}n = \mathbf{K}.$$
Since the positive integers $m$ and $n$ satisfying this are $$m = \mathbf{L} \text{ and } n = \mathbf{M},$$ we obtain $$a = \mathbf{N} \text{ and } b = \mathbf{O}.$$
(2) We are to find the solutions $a$ and $b$ of equation (1) satisfying $0 < a + b < 5$.
Since $14 \times \mathbf{N} + 9 \times \mathbf{O} = 147$, from this equality and (1) we have $$14(a - \mathbf{N}) = 9(\mathbf{O} - b).$$
Since 14 and 9 are relatively prime, $a$ and $b$ can be expressed in terms of an integer $k$ as $$a = \mathbf{P} + \mathbf{Q}k, \quad b = -\mathbf{RS}k + \mathbf{T}.$$
Since $0 < a + b < 5$, we have $k = \mathbf{U}$, and we obtain $$a = \mathbf{VW}, \quad b = -\mathbf{XY}.$$

5. For ALL APPLICANTS.

Songs of the Martian classical period had just two notes (let us call them $x$ and $y$ ) and were constructed according to rigorous rules: I. the sequence consisting of no notes was deemed to be a song (perhaps the most pleasant); II. a sequence starting with $x$, followed by two repetitions of an existing song and ending with $y$ was also a song; III. the sequence of notes obtained by interchanging $x$ s and $y$ s in a song was also a song.
All songs were constructed using those rules.
(i) Write down four songs of length six (that is, songs with exactly six notes).
(ii) Show that if there are $k$ songs of length $m$ then there are $2 k$ songs of length $2 m + 2$. Deduce that for each natural number there are $2 ^ { n }$ songs of length $2 ^ { n + 1 } - 2$.
Songs of the Martian later period were constructed using also the rule: IV. if a song ended in $y$ then the sequence of notes obtained by omitting that $y$ was also a song.
(iii) What lengths do songs of the later period have? That is, for which natural numbers $n$ is there a song with exactly $n$ notes? Justify your answer.

5. For ALL APPLICANTS.

Songs of the Martian classical period had just two notes (let us call them $x$ and $y$ ) and were constructed according to rigorous rules: I. the sequence consisting of no notes was deemed to be a song (perhaps the most pleasant); II. a sequence starting with $x$, followed by two repetitions of an existing song and ending with $y$ was also a song; III. the sequence of notes obtained by interchanging $x$ s and $y$ s in a song was also a song.
All songs were constructed using those rules.
(i) Write down four songs of length six (that is, songs with exactly six notes).
(ii) Show that if there are $k$ songs of length $m$ then there are $2 k$ songs of length $2 m + 2$. Deduce that for each natural number there are $2 ^ { n }$ songs of length $2 ^ { n + 1 } - 2$.
Songs of the Martian later period were constructed using also the rule: IV. if a song ended in $y$ then the sequence of notes obtained by omitting that $y$ was also a song.
(iii) What lengths do songs of the later period have? That is, for which natural numbers $n$ is there a song with exactly $n$ notes? Justify your answer.

5. For ALL APPLICANTS.

An $n \times n$ square array contains 0 s and 1 s. Such a square is given below with $n = 3$.

0	0	1
1	0	0
1	1	0

Two types of operation $C$ and $R$ may be performed on such an array.

• The first operation $C$ takes the first and second columns (on the left) and replaces them with a single column by comparing the two elements in each row as follows; if the two elements are the same the $C$ replaces them with a 1 , and if they differ $C$ replaces them with a 0 .
• The second operation $R$ takes the first and second rows (from the top) and replaces them with a single row by comparing the two elements in each column as follows; if the two elements are the same the $R$ replaces them with a 1 , and if they differ $R$ replaces them with a 0 .

By way of example, the effects of performing $R$ then $C$ on the square above are given below.
$$\begin{array} { c c c } 0 & 0 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \end{array} \xrightarrow { R } \begin{array} { c c c } 0 & 1 & 0 \\ 1 & 1 & 0 \end{array} \xrightarrow { C } \begin{array} { c c } 0 & 0 \\ 1 & 0 \end{array}$$
(a) If $R$ then $C$ are performed on a $2 \times 2$ array then only a single number ( 0 or 1 ) remains.
(i) Write down in the grids on the next page the eight $2 \times 2$ arrays which, when $R$ then $C$ are performed, produce a 1 .
(ii) By grouping your answers accordingly, show that if $\begin{array} { l l } a & b \\ c & d \end{array}$ is amongst your answers to part (i) then so is $\begin{array} { l l } a & c \\ b & d \end{array}$. Explain why this means that doing $R$ then $C$ on a $2 \times 2$ array produces the same answer as doing $C$ first then $R$.
(b) Consider now a $n \times n$ square array containing 0 s and 1 s , and the effects of performing $R$ then $C$ or $C$ then $R$ on the square.
(i) Explain why the effect on the right $n - 2$ columns is the same whether the order is $R$ then $C$ or $C$ then $R$. [This then also applies to the bottom $n - 2$ rows.]
(ii) Deduce that performing $R$ then $C$ on an $n \times n$ square produces the same result as performing $C$ then $R$. [Figure] [Figure] [Figure] [Figure] [Figure] [Figure] [Figure] [Figure]

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

Alice, Bob and Charlie are well-known expert logicians.
(i) The King places a hat on each of their heads. Each of the logicians can see the others' hats, but not his or her own.
The King says "Each of your hats is either black or white, but you don't all have the same colour hat".
All four are honest, and all trust one another. The King now asks Alice "Do you know what colour your hat is?". Alice says "Yes, it's white". [0pt] What colour are the others' hats? [Hint: think about how Alice can deduce that her hat is white.]
(ii) The King now changes some of the hats, and again says "Each of your hats is either black or white, but you don't all have the same colour hat". He now asks Alice "Do you know what colour your hat is?".
Alice replies "No" [0pt] Can Bob work out what colour his hat is? Explain your answer. [Hint: what can Bob deduce from the fact that Alice can't tell what colour her hat is?]
(iii) The King now changes some of the hats, and then says "Each of your hats is either black or white. At least one of you has a white hat."
He now asks them all "Do you know what colour your hat is?". They all simultaneously reply "No".
What can you deduce about the colour of their hats? Explain your answer.
(iv) He again asks "Do you know what colour your hat is?" Alice says "No", but Bob and Charlie both say "Yes" (all three answer simultaneously).
What colour are their hats? Explain your answer.

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

(i) Alice, Bob, Charlie and Dianne each make the following statements:
Alice: I am telling the truth. Bob: Alice is telling the truth. Charlie: Bob is telling the truth. Dianne: Charlie is lying.
Only one of the 4 people is telling the truth. Which one? Explain your answer.
(ii)They now make the following statements:
Alice: Bob is lying. Bob: Charlie is lying. Charlie: I like beer. Dianne: $2 + 2 = 4$.
Now two of the four people are telling the truth. Which two? Explain your answer.
(iii) They are now joined by Egbert. They each make the following statements:
Alice: I like wine. Bob: Charlie is lying. Charlie: Alice is lying. Dianne: Alice likes beer. Egbert: Alice likes beer.
Now three of the five people are telling the truth. Which ones? Explain your answer.

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

Alice, Bob and Charlie are well-known expert logicians.
(i) The King places a hat on each of their heads. Each of the logicians can see the others' hats, but not his or her own.
The King says "Each of your hats is either black or white, but you don't all have the same colour hat".
All four are honest, and all trust one another. The King now asks Alice "Do you know what colour your hat is?". Alice says "Yes, it's white". [0pt] What colour are the others' hats? [Hint: think about how Alice can deduce that her hat is white.]
(ii) The King now changes some of the hats, and again says "Each of your hats is either black or white, but you don't all have the same colour hat". He now asks Alice "Do you know what colour your hat is?".
Alice replies "No" [0pt] Can Bob work out what colour his hat is? Explain your answer. [Hint: what can Bob deduce from the fact that Alice can't tell what colour her hat is?]
(iii) The King now changes some of the hats, and then says "Each of your hats is either black or white. At least one of you has a white hat."
He now asks them all "Do you know what colour your hat is?". They all simultaneously reply "No".
What can you deduce about the colour of their hats? Explain your answer.
(iv) He again asks "Do you know what colour your hat is?" Alice says "No", but Bob and Charlie both say "Yes" (all three answer simultaneously).
What colour are their hats? Explain your answer.

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

(i) Alice, Bob, Charlie and Dianne each make the following statements:
Alice: I am telling the truth. Bob: Alice is telling the truth. Charlie: Bob is telling the truth. Dianne: Charlie is lying.
Only one of the 4 people is telling the truth. Which one? Explain your answer.
(ii)They now make the following statements:
Alice: Bob is lying. Bob: Charlie is lying. Charlie: I like beer. Dianne: $2 + 2 = 4$.
Now two of the four people are telling the truth. Which two? Explain your answer.
(iii) They are now joined by Egbert. They each make the following statements:
Alice: I like wine. Bob: Charlie is lying. Charlie: Alice is lying. Dianne: Alice likes beer. Egbert: Alice likes beer.
Now three of the five people are telling the truth. Which ones? Explain your answer.

A square made of cardboard has sides of unit length and corners marked $A , B , C , D$.\ (a) Show that there are eight different ways of placing the cardboard square so that it completely covers the square region in the $( x , y )$ plane with corners at the points $( 0,0 ) , ( 0,1 ) , ( 1,1 ) , ( 1,0 )$.\ (b) Initially the square is positioned so that $A , B , C , D$ are over the points $( 0,0 ) , ( 0,1 )$, $( 1,1 ) , ( 1,0 )$, respectively. You may move the square by either\ (i) rotating it in the plane by $90 ^ { \circ }$ about one of the corners, or\ (ii) turning it over keeping one of the edges fixed in contact with the plane.
Show that after two moves it is possible to return the square to its initial position but with the corners $B$ and $D$ interchanged.\ (c) Show that four of the eight configurations in (a) can be achieved from the initial position and moves described in (b).

Songs of the Martian classical period had just two notes (let us call them $x$ and $y$ ) and were constructed according to rigorous rules:\ I. the sequence consisting of no notes was deemed to be a song (perhaps the most pleasant);\ II. a sequence starting with $x$, followed by two repetitions of an existing song and ending with $y$ was also a song;\ III. the sequence of notes obtained by interchanging $x$ 's and $y$ 's in a song was also a song.\ All songs were constructed using those rules.\ (a) Write down four songs of length 6 (that is, songs with exactly 6 notes).\ (b) Show that if there are $k$ songs of length $m$ then there are $2 k$ songs of length $2 m + 2$. Deduce that for each natural number $n$ there are $2 ^ { n }$ songs of length $2 ^ { n + 1 } - 2$.
Songs of the Martian later period were constructed using also the rule:\ IV. if a song ended in $y$ then the sequence of notes obtained by omitting that $y$ was also a song.\ (c) What lengths do songs of the later period have? That is, for which natural numbers $n$ is there a song with exactly $n$ notes? Justify your answer.

5. With an unlimited supply of black pebbles and white pebbles, there are 4 ways in which you can put two of them in a row: $B B , B W , W B$ and $W W$.
(a) Write down the 8 different ways in which you can put three of the pebbles in a row. In how many different ways can you put $N$ of the pebbles in a row?
Suppose now that you are not allowed to put black pebbles next to each other: with two pebbles there are now only 3 ways of putting them in a row, because $B B$ is forbidden.
(b) Write down the 5 different ways that are still allowed for three pebbles.
Now let $r _ { N }$ be the number of possible arrangements for $N$ pebbles in a row, still under the no-two-black-together restriction, so that $r _ { 2 } = 3$ and $r _ { 3 } = 5$.
(c) Show that for $N \geqslant 4$ we have $r _ { N } = r _ { N - 1 } + r _ { N - 2 }$. [Hint: Consider separately the two possible cases for the colour of the last pebble.]
Finally, suppose that we impose the further restriction that the first pebble and the last pebble cannot both be black. For $N$ pebbles call the number of such arrangements $w _ { N }$, so that for example $w _ { 3 } = 4$ (although $r _ { 3 } = 5$, the arrangement $B W B$ is now forbidden).
(d) When $N \geqslant 5$, write down a formula for $w _ { N }$ in terms of the numbers $r _ { i }$, and explain why it is correct.

5. The game of Oxflip is for one player and involves circular counters, which are white on one side and black on the other, placed in a grid. During a game, the counters are flipped over (changing between black and white side uppermost) following certain rules. Given a particular size of grid and a set starting pattern of whites and blacks, the aim of the game is to reach a certain target pattern. Each "move" of the game is to flip over either a whole row or a whole column of counters (so one whole row or column has all its blacks swapped to whites and vice versa). For example, in a game played in a three-by-three square grid, if you are given the starting and target patterns [Figure] [Figure] a sequences of three moves to achieve the target is: [Figure]
There are many other sequences of moves which also have the same result.
(a) Consider the two-by-two version of the game with starting pattern [Figure]
Draw, in the blank patterns opposite, the eight different target patterns (including the starting pattern) which it is possible to obtain. What are the possible numbers of white counters that may be present in these target patterns?
(b) In the four-by-four version of the game, starting with pattern [Figure] explain why it is impossible to reach a pattern with only one white counter. [0pt] [Hint: don't try to write out every possible combination of moves.]
(c) In the five-by-five game, explain why any sequence of moves which begins [Figure] and ends with an all-white pattern, must involve an odd number of moves. What is the least number of moves needed? Give reasons for your answer. [Figure]

4. An $n \times n$ square array contains 0 s and 1 s. Such a square is given below with $n = 3$.

0	0	1
1	0	0
1	1	0

Two types of operation $C$ and $R$ may be performed on such an array.

• The first operation $C$ takes the first and second columns (on the left) and replaces them with a single column by comparing the two elements in each row as follows: if the two elements are the same then $C$ replaces them with a 1 , and if they differ $C$ replaces them with a 0 .
• The second operation $R$ takes the first and second rows (from the top) and replaces them with a single row by comparing the two elements in each column as follows: if the two elements are the same then $R$ replaces them with a 1 , and if they differ $R$ replaces them with a 0 .

By way of example, the effects of performing $R$ then $C$ on the square above are given below.

0	0	1
1	0	0
1	1	0

$\xrightarrow { R }$

0	1	0
1	1	0

$\xrightarrow { C }$

0	0
1	0

(a) If $R$ then $C$ are performed (in that order) on a $2 \times 2$ array then only a single number (0 or 1 ) remains.
(i) Write down, in the grids on the next page, the eight $2 \times 2$ arrays which, when $R$ then $C$ are performed, produce a 1.
(ii) By grouping your answers accordingly, show that if

$a$	$b$
$c$	$d$

is amongst your answers to part (i) then so is

$a$	$c$
$b$	$d$

Explain why this means that doing $R$ then $C$ on a $2 \times 2$ array produces the same answer as doing $C$ first then $R$.
(b) Consider now an $n \times n$ square array containing 0 s and 1 s , and the effects of performing $R$ then $C$ or $C$ then $R$ on the square.
(i) Explain why the effect on the right $n - 2$ columns is the same whether the order is $R$ then $C$ or $C$ then $R$. [This then also applies to the bottom $n - 2$ rows.]
(ii) Deduce that performing $R$ then $C$ on an $n \times n$ square produces the same result as performing $C$ then $R$.

l

1. (a) Three points $P , A , B$ lie on a circle which has centre $O$. The point $C$ is where $P O$ extends to meet $A B$ as shown in the diagram below. [Figure]

Show that $\measuredangle A O C = 2 \measuredangle A P C$ and $\measuredangle B O C = 2 \measuredangle B P C$. Why does this mean that $\angle A P B$ is independent of the choice of the point $P$ ?
(b) Four points $K , L , M , N$ lie on a circle and the lines $L K$ and $M N$ meet outside the circle at a point $S$, as shown in the diagram below. [Figure]
Using part (a) and the Sine Rule show that
$$\frac { K S } { N S } = \frac { S M } { S L }$$
[You may also assume that part (b) holds true in the special case when $M = N$ in which case the line $S M$ is the tangent to the circle at $M$.]
(c) A tower has height $h$. Assuming the earth to be a perfect sphere of radius $r$, determine the greatest distance $x$ from the top of the tower at which an observer can still see it. [Figure]

5. For ALL APPLICANTS.

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 )$.