5. For ALL APPLICANTS.

An $n \times n$ grid consists of squares arranged in $n$ rows and $n$ columns; for example, a chessboard is an $8 \times 8$ grid. Let us call a semi-grid of size $n$ the lower left part of an $n \times n$ grid - that is, the squares located on or below the grid's diagonal. For example, Figure C shows an example of a semi-grid of size 4.
[Figure]
Figure C
Let us suppose that a robot is located in the lower-left corner of the grid. The robot can move only up or right, and its goal is to reach one of the goal squares, which are all located on the semi-grid's diagonal. In the example shown in Figure C , the robot is initially located in the square denoted with R , and the goal squares are shown in grey. Let us call a solution a sequence of the robot's moves that leads the robot from the initial location to some goal square.
(i) Write down all 8 solutions for a robot on a semi-grid of size 4 .
(ii) Devise a concise way of representing the possible journeys of the robot in a semi-grid of size $n$. In your notation, which of the journeys are solutions?
(iii) Write down a formula for the number of possible solutions in a semi-grid of size $n$. Explain why your formula is correct.
Now let us change the problem slightly and redefine a goal square as any square that can be described as follows:

• the lower-left square is not a goal square;
• each square that is located immediately above or immediately to the right of a non-goal square is a goal square; and
• each square that is located immediately above or immediately to the right of a goal square is a non-goal square. Furthermore, let us assume that, upon reaching a goal square, the robot may decide to stop or to continue moving (provided that there are more allowed moves).
  (iv) With these modifications in place, write down all the solutions in a semi-grid of size 4, and all the solutions in a semi-grid of size 5.
  (v) How many solutions are there now in a semi-grid of size $n$, where $n$ is a positive integer? You may wish to consider separately the cases where $n$ is even or odd.

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

A positive rational number $q$ is expressed in friendly form if it is written as a finite sum of reciprocals of distinct positive integers. For example, $\frac { 4 } { 5 } = \frac { 1 } { 2 } + \frac { 1 } { 4 } + \frac { 1 } { 20 }$.
(i) Express the following numbers in friendly form: $\frac { 2 } { 3 } , \frac { 2 } { 5 } , \frac { 23 } { 40 }$.
(ii) Let $q$ be a rational number with $0 < q < 1$, and $m$ be the smallest natural number such than $\frac { 1 } { m } \leqslant q$. Suppose $q = \frac { a } { b }$ and $q - \frac { 1 } { m } = \frac { c } { d }$ in their lowest terms. Show that $c < a$.
(iii) Suggest a procedure by which any rational $q$ with $0 < q < 1$ can be expressed in friendly form. Use the result in part (ii) to show that the procedure always works, generating distinct reciprocals and finishing within a finite time.
(iv) Demonstrate your procedure by finding a friendly form for $\frac { 4 } { 13 }$.
(v) Assuming that $\sum _ { n = 1 } ^ { N } \frac { 1 } { n }$ increases without bound as $N$ becomes large, show that every positive rational number can be expressed in friendly form.

5. For ALL APPLICANTS.

This question is about counting the number of ways of partitioning a set of $n$ elements into subsets, each with at least two and at most $n$ elements. If $n$ and $k$ are integers with $1 \leqslant k \leqslant n$, let $f ( n , k )$ be the number of ways of partitioning a set of $n$ elements into $k$ such subsets. For example, $f ( 5,2 ) = 10$ because the allowable partitions of $\{ 1,2,3,4,5 \}$ are
$$\begin{array} { l l } \{ 1,5 \} , \{ 2,3,4 \} , & \{ 1,2,5 \} , \{ 3,4 \} , \\ \{ 2,5 \} , \{ 1,3,4 \} , & \{ 3,4,5 \} , \{ 1,2 \} , \\ \{ 3,5 \} , \{ 1,2,4 \} , & \{ 1,3,5 \} , \{ 2,4 \} , \\ \{ 4,5 \} , \{ 1,2,3 \} , & \{ 2,4,5 \} , \{ 1,3 \} , \\ & \{ 1,4,5 \} , \{ 2,3 \} , \\ & \{ 2,3,5 \} , \{ 1,4 \} . \end{array}$$
(i) Explain why $f ( n , k ) = 0$ if $k > n / 2$.
(ii) What is the value of $f ( n , 1 )$ and why?
(iii) In forming an allowable partition of $\{ 1,2 , \ldots , n + 1 \}$ into subsets of at least two elements, we can either

• pair $n + 1$ with one other element, leaving $n - 1$ elements to deal with, or
• take an allowable partition of $\{ 1,2 , \ldots , n \}$ and add $n + 1$ to one of the existing subsets, making a subset of size three or more.

Use this observation to find an equation for $f ( n + 1 , k )$ in terms of $f ( n - 1 , k - 1 )$ and $f ( n , k )$ that holds when $2 \leqslant k < n$.
(iv) Use this equation to compute the value of $f ( 7,3 )$.
(v) Give a formula for $f ( 2 n , n )$ in terms of $n$ when $n \geqslant 1$ and show that it is correct.
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.

A flexadecimal number consists of a sequence of digits, with the rule that the rightmost digit must be 0 or 1 , the digit to the left of it is 0,1 , or 2 , the third digit (counting from the right) must be at most 3 , and so on. As usual, we may omit leading digits if they are zero. We write flexadecimal numbers in angle brackets to distinguish them from ordinary, decimal numbers. Thus $\langle 34101 \rangle$ is a flexadecimal number, but $\langle 231 \rangle$ is not, because the digit 3 is too big for its place. (If flexadecimal numbers get very long, we will need 'digits' with a value more than 9 .)
The number 1 is represented by $\langle 1 \rangle$ in flexadecimal. To add 1 to a flexadecimal number, work from right to left. If the rightmost digit $d _ { 1 }$ is 0 , replace it by 1 and finish. Otherwise, replace $d _ { 1 }$ by 0 and examine the digit $d _ { 2 }$ to its left, appending a zero at the left if needed at any stage. If $d _ { 2 } < 2$, then increase it by 1 and finish, but if $d _ { 2 } = 2$, then replace it by 0 , and again move to the left. The process stops when it reaches a digit that can be increased without becoming too large. Thus, the numbers 1 to 4 are represented as $\langle 1 \rangle , \langle 10 \rangle , \langle 11 \rangle , \langle 20 \rangle$.
(i) Write the numbers from 5 to 13 in flexadecimal.
(ii) Describe a workable procedure for converting flexadecimal numbers to decimal, and explain why it works. Demonstrate your procedure by converting $\langle 1221 \rangle$ to decimal.
(iii) Describe a workable procedure for converting decimal numbers to flexadecimal, and demonstrate it by converting 255 to flexadecimal.
(iv) We could add flexadecimal numbers by converting them to decimal, adding the decimal numbers and converting the result back again. Describe instead a procedure for addition that works directly on the digits of two flexadecimal numbers, and demonstrate it by performing the addition $\langle 1221 \rangle + \langle 201 \rangle$.
(v) Given a flexadecimal number, how could you test whether it is a multiple of 3 without converting it to decimal?
(vi) If the $\langle 100000 \rangle$ arrangements of the letters abcdef are listed in alphabetical order and numbered $\langle 0 \rangle$ : abcdef, $\langle 1 \rangle$ : abcdfe, $\langle 10 \rangle$ : abcedf, etc., what arrangement appears in position $\langle 34101 \rangle$ in the list?
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 cancellation of the Wimbledon tournament has led to a world surplus of tennis balls, and Santa has decided to use them as stocking fillers. He comes down the chimney with $n$ identical tennis balls, and he finds $k$ named stockings waiting for him.
Let $g ( n , k )$ be the number of ways that Santa can put the $n$ balls into the $k$ stockings; for example, $g ( 2,2 ) = 3$, because with two balls and two children, Miriam and Adam, he can give both balls to Miriam, or both to Adam, or he can give them one ball each.
(i) What is the value of $g ( 1 , k )$ for $k \geqslant 1$ ?
(ii) What is the value of $g ( n , 1 )$ ?
(iii) If there are $n \geqslant 2$ balls and $k \geqslant 2$ children, then Santa can either give the first ball to the first child, then distribute the remaining balls among all $k$ children, or he can give the first child none, and distribute all the balls among the remaining children. Use this observation to formulate an equation relating the value of $g ( n , k )$ to other values taken by $g$.
(iv) What is the value of $g ( 7,5 )$ ?
(v) After the first house, Rudolf reminds Santa that he ought to give at least one ball to each child. Let $h ( n , k )$ be the number of ways of distributing the balls according to this restriction. What is the value of $h ( 7,5 )$ ?
This page has been intentionally left blank

5. For ALL APPLICANTS.

A triangular triple is a triple of positive integers ( $a , b , c$ ) such that we can construct a triangle with sides of length $a , b$ and $c$. This means that the sum of any two of the numbers is strictly greater than the third; so if $a \leqslant b \leqslant c$, then it is equivalent to requiring $a + b > c$. For example, ( $3,3,3$ ) and ( $4,5,3$ ) are triangular triples, but ( $1,3,2$ ) and ( $3,3,6$ ) are not. For any positive integer $P$, we define $f ( P )$ to be the number of triangular triples such that the perimeter $a + b + c$ is equal to $P$. Triples with the same numbers, but in a different order, are counted as being distinct. So $f ( 12 ) = 10$, because there are 10 triangular triples with perimeter 12, shown below:

$( 3,4,5 )$	$( 3,5,4 )$	$( 4,3,5 )$	$( 4,5,3 )$	$( 5,3,4 )$	$( 5,4,3 )$
$( 2,5,5 )$	$( 5,2,5 )$	$( 5,5,2 )$
$( 4,4,4 )$

(i) Write down the values of $f ( 3 ) , f ( 4 ) , f ( 5 )$ and $f ( 6 )$.
(ii) If ( $a , b , c$ ) is a triangular triple, show that ( $a + 1 , b + 1 , c + 1$ ) is also a triangular triple.
(iii) If ( $x , y , z$ ) is a triangular triple, with $x + y + z$ equal to an even number greater than or equal to 6 , show that each of $x , y , z$ is at least 2 and that $( x - 1 , y - 1 , z - 1 )$ is also a triangular triple.
(iv) Using the previous two parts, prove that for any positive integer $k \geqslant 3$,
$$f ( 2 k - 3 ) = f ( 2 k )$$
(v) We will now consider the case where $P \geqslant 6$ is even, and we will write $P = 2 S$.
(a) Show that in this case ( $a , b , c$ ) is a triangular triple with $a + b + c = P$ if and only if each of $a , b , c$ is strictly smaller than $S$.
(b) For any $a$ such that $2 \leqslant a \leqslant S - 1$, show that the number of possible values of $b$ such that $( a , b , P - a - b )$ is a triangular triple is $a - 1$. Hence find an expression for $f ( P )$ for any even $P \geqslant 6$.
(vi) Find $f ( 21 )$.
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.

Distinct numbers are arranged in an $m \times n$ rectangular table with $m$ rows and $n$ columns so that in each row the numbers are in increasing order (left to right), and in each column the numbers are in increasing order (top to bottom). Such a table is called a sorted table and each location of the table containing a number is called a cell. Two examples of sorted tables with 3 rows and 4 columns (and thus $3 \times 4 = 12$ cells) are shown below.

3	12	33	64
15	26	37	78
19	40	51	92

5	22	53	68
18	36	67	78
19	45	81	92

We index the cells of the table with a pair of integers $( i , j )$, with the top-left corner being $( 1,1 )$ and the bottom-right corner being $( m , n )$. Observe that the smallest entry in a sorted table can only occur in cell $( 1,1 )$; however, note that the second smallest entry can appear either in cell ( 1,2 ), as in the first example above, or in cell ( 2,1 ) as in the second example above.
(i) (a) Assuming that $m , n \geqslant 3$, where in an $m \times n$ sorted table can the third-smallest entry appear?
(b) For any $k \geqslant 4$ satisfying $m , n \geqslant k$, where in an $m \times n$ sorted table can the $k ^ { \text {th } }$ smallest entry appear? Justify your answer.
(ii) Given an $m \times n$ sorted table, consider the problem of determining whether a particular number $y$ appears in the table. Outline a procedure that inspects at most $m + n - 1$ cells in the table, and that correctly determines whether or not $y$ appears in the table. Briefly justify why your procedure terminates correctly in no more than $m + n - 1$ steps. [0pt] [Hint: As the first step, consider inspecting the top-right cell.]
(iii) Consider an $m \times n$ table, say $A$, which might not be sorted; an example is shown below. Obtain table $B$ from $A$ by re-arranging the entries in each row so that they are in sorted order. Then obtain table $C$ from $B$ by re-arranging the entries in each column so that they are in sorted order. Fill in tables $B$ and $C$ here:
\begin{table}[h]
$A$ :

33	92	46	24
25	26	37	8
49	40	81	22

\end{table}
$C$ :
$B$ : [Figure]
[Figure]
(iv) Show that for any $m \times n$ table $A$, performing the two operations from part (iii) results in a sorted table $C$.
This page has been intentionally left blank

How many line segments are there in the first diagram in total? Explain your answer.

A 3-star is a collection of three distinct points, with each pair connected by a straight line segment. How many 3-stars are there in the first diagram in total? Explain your answer.

For $n \geq 4$, an $n$-star is a collection of $n$ distinct points, with each pair connected by a straight line segment. For $n = 4,5,6,7,8$, how many $n$-stars are there in the first diagram in total? Explain your answers.

A new diagram is formed of three separate collections of points named $A , B$, and $C$ respectively. $A$ contains 3 points, $B$ contains 4 points, and $C$ contains 5 points. Each point in $A$ is connected with a straight line segment to each point in $B$. Each point in $B$ is connected with a straight line segment to each point in $C$. Each point in $C$ is connected with a straight line segment to each point in $A$. No other pairs of points are connected with a straight line segment. How many 3-stars are there in this new diagram in total? Justify your answer carefully.

For $n \geq 2$, an $n$-loop is a sequence of $n$ distinct points with each point connected to the next in sequence with a straight line segment, and with the last connected to the first with a straight line segment. For which values of $n \geq 4$ does the new diagram described in part (iv) contain at least one $n$-loop? Justify your answer.

A graduating class has 8 students responsible for planning a class trip, divided into three groups A, B, and C, consisting of 3, 3, and 2 people respectively. Each of the 8 students will be assigned to one of the groups, and two students, A and B, must be in the same group. How many ways are there to divide the 8 students into groups?
(1) 140 ways
(2) 150 ways
(3) 160 ways
(4) 170 ways
(5) 180 ways

From the nine numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, any three distinct numbers are randomly selected, with each number having equal probability of being selected. The probability that the product of the three numbers is a perfect square is (20). (Express as a fraction in lowest terms)

A convenience store packages three building block models (A, B, C) and five character figurines ($a, b, c, d, e$), totaling eight toys, into two bags for sale. Each bag contains four toys, and the packaging follows these principles: (I) A and $a$ must be in the same bag. (II) Each bag must contain at least one building block model. (III) $d$ and $e$ must be in different bags. Based on the above, select the correct options.
(1) Each bag must contain at least two character figurines
(2) B and C must be in different bags
(3) If B and $d$ are in the same bag, then C and $e$ must be in the same bag
(4) If B and $d$ are in different bags, then $b$ and $c$ must be in different bags
(5) If $b$ and $c$ are in different bags, then B and C must be in the same bag

An ice cream shop needs to prepare at least $n$ buckets of different flavors of ice cream to satisfy the advertisement claim that ``the number of combinations of selecting two scoops of different flavors exceeds 100 types.'' How many ways can a customer select two scoops (which may be the same flavor) from $n$ buckets?
(1) 101
(2) 105
(3) 115
(4) 120
(5) 225

A bag contains blue, green, and yellow balls totaling 10 balls. Two balls are randomly drawn from the bag (each ball has an equal probability of being drawn). The probability that both balls drawn are blue is $\frac{1}{15}$, and the probability that both are green is $\frac{2}{9}$. The probability that two randomly drawn balls are of different colors is $\frac{\text{(16--1)}}{\text{(16--3)}}$. (Express as a fraction in lowest terms)

Arrange the digits $1, 2, 3, \ldots, 9$ into a nine-digit number (digits cannot be repeated) such that the first 5 digits are increasing from left to right and the last 5 digits are decreasing from left to right. How many nine-digit numbers satisfy the conditions?
(1) $\frac{8!}{4!4!}$
(2) $\frac{8!}{5!3!}$
(3) $\frac{9!}{5!4!}$
(4) $\frac{8!}{5!}$
(5) $\frac{9!}{5!}$

A department store holds a Father's Day card drawing promotion with the following rules: The organizer prepares ten cards numbered $1, 2, \ldots, 9$, of which there are two cards numbered 8, and only one card for each other number. Four cards are randomly drawn from these ten cards without replacement and arranged from left to right in order to form a four-digit number. If the four-digit number satisfies any one of the following conditions, a prize is won:
(1) The four-digit number is greater than 6400
(2) The four-digit number contains two digits 8 For example: If the four cards drawn are numbered $5, 8, 2, 8$ in order, then the four-digit number is 5828, and a prize is won. According to the above rules, there are (11-1)(11-2)(11-3)(11-4) four-digit numbers that can win prizes.

It is desired to place 4 identical chess rooks on a $5 \times 5$ chessboard. Since rooks can capture pieces in the same row or column, the placement rule is that at most one rook can be placed in each row and each column. Given that rooks are not placed in the first, third, and fifth squares of the first row (as shown by the crossed squares in the diagram), how many ways are there to place the rooks?
(1) 216
(2) 240
(3) 288
(4) 312
(5) 360

A store launches a lottery activity offering four different styles of fruit figurines as prizes. Each lottery draw yields 1 figurine, and each style has an equal probability of being drawn. A person decides to draw 4 times. What is the probability that he draws exactly 3 different styles of figurines?
(1) $\frac { 5 } { 16 }$
(2) $\frac { 3 } { 8 }$
(3) $\frac { 1 } { 2 }$
(4) $\frac { 9 } { 16 }$
(5) $\frac { 5 } { 8 }$

A company hires 8 new employees, including 2 translators, 3 engineers, and 3 assistants. These 8 people are assigned to research and testing departments, with 4 people assigned to each department. Each department must include 1 translator and at least 1 engineer. There are (15--1)(15--2) ways to make such assignments.

A large circular table has 40 chairs round it.
What is the smallest number of people who can be sitting at the table already such that the next person to sit down must sit next to someone?

Answer the following questions.
(1) Calculate the number of possible ways to distribute $n$ equivalent balls to $r$ distinguishable boxes such that each box contains at least one ball, where $n \geq 1$ and $1 \leq r \leq n$.
Next, consider to place $n$ black balls and $m$ white balls in a line uniformly at random. A run is defined to be a succession of the same color. Let $r$ be the number of runs of black balls and $s$ be the number of runs of white balls. Assume that $n \geq 1 , m \geq 1,1 \leq r \leq n$, and $1 \leq s \leq m$.
(2) Calculate the total number of arrangements when we do not distinguish among balls of the same color.
(3) Calculate the probability $P ( r , s )$ that the number of runs of black balls is $r$ and the number of runs of white balls is $s$.
(4) Calculate the probability $P ( r )$ that the number of runs of black balls is $r$.
(5) Using $( 1 + x ) ^ { n } ( 1 + x ) ^ { m } = ( 1 + x ) ^ { n + m }$, show that the following equations hold.
$$\begin{aligned} \sum _ { \ell = 0 } ^ { \min \{ n , m \} } \binom { n } { \ell } \binom { m } { \ell } & = \binom { n + m } { m } \\ \sum _ { \ell = 0 } ^ { \min \{ n - 1 , m \} } \binom { n } { \ell + 1 } \binom { m } { \ell } & = \binom { n + m } { m + 1 } \end{aligned}$$
(6) Calculate the expected value $E ( r )$ and the variance $V ( r )$ of $r$.
Calculate $\lim _ { N \rightarrow \infty } \frac { E ( r ) } { N }$ and $\lim _ { N \rightarrow \infty } \frac { V ( r ) } { N }$ supposing that $N = n + m$ and $\lim _ { N \rightarrow \infty } \frac { n } { N } = \lambda$, where $\lambda$ is a real constant.

Let $n$ be an odd number greater than or equal to 5. Consider a circle centered at point O in the plane, and a regular $n$-gon inscribed in it. Choose 4 distinct points simultaneously from the $n$ vertices. Assume that any 4 points are equally likely to be chosen. Find the probability $p_n$ that the quadrilateral with the chosen 4 points as vertices contains O in its interior.