Q62. Let $0 \leq \mathrm { r } \leq \mathrm { n }$. If ${ } ^ { \mathrm { n } + 1 } \mathrm { C } _ { \mathrm { r } + 1 } : { } ^ { n } \mathrm { C } _ { \mathrm { r } } : { } ^ { \mathrm { n } - 1 } \mathrm { C } _ { \mathrm { r } - 1 } = 55 : 35 : 21$, then $2 \mathrm { n } + 5 \mathrm { r }$ is equal to:
(1) 50
(2) 62
(3) 55
(4) 60

Q62. The number of ways five alphabets can be chosen from the alphabets of the word MATHEMATICS, where the chosen alphabets are not necessarily distinct, is equal to :
(1) 179
(2) 177
(3) 181
(4) 175

Q63. There are 5 points $P _ { 1 } , P _ { 2 } , P _ { 3 } , P _ { 4 } , P _ { 5 }$ on the side $A B$, excluding $A$ and $B$, of a triangle $A B C$. Similarly there are 6 points $\mathrm { P } _ { 6 } , \mathrm { P } _ { 7 } , \ldots , \mathrm { P } _ { 11 }$ on the side BC and 7 points $\mathrm { P } _ { 12 } , \mathrm { P } _ { 13 } , \ldots , \mathrm { P } _ { 18 }$ on the side $C A$ of the triangle. The number of triangles, that can be formed using the points $\mathrm { P } _ { 1 } , \mathrm { P } _ { 2 } , \ldots , \mathrm { P } _ { 18 }$ as vertices, is :
(1) 776
(2) 796
(3) 751
(4) 771

Q68. Let the set $S = \{ 2,4,8,16 , \ldots , 512 \}$ be partitioned into 3 sets $A , B , C$ with equal number of elements such that $\mathrm { A } \cup \mathrm { B } \cup \mathrm { C } = \mathrm { S }$ and $\mathrm { A } \cap \mathrm { B } = \mathrm { B } \cap \mathrm { C } = \mathrm { A } \cap \mathrm { C } = \phi$. The maximum number of such possible partitions of $S$ is equal to:
(1) 1680
(2) 1640
(3) 1520
(4) 1710

Q70. Let $A = \{ 1,3,7,9,11 \}$ and $B = \{ 2,4,5,7,8,10,12 \}$. Then the total number of one-one maps $f : \mathrm { A } \rightarrow \mathrm { B }$, such that $f ( 1 ) + f ( 3 ) = 14$, is :
(1) 480
(2) 240
(3) 120
(4) 180

Q81. There are 4 men and 5 women in Group A, and 5 men and 4 women in Group B. If 4 persons are selected from each group, then the number of ways of selecting 4 men and 4 women is $\_\_\_\_$

Q85. In a survey of 220 students of a higher secondary school, it was found that at least 125 and at most 130 students studied Mathematics; at least 85 and at most 95 studied Physics; at least 75 and at most 90 studied Chemistry; 30 studied both Physics and Chemistry; 50 studied both Chemistry and Mathematics; 40 studied both Mathematics and Physics and 10 studied none of these subjects. Let m and n respectively be the least and the most number of students who studied all the three subjects. Then $\mathrm { m } + \mathrm { n }$ is equal to $\_\_\_\_$

Number of ways to distribute 6 identical oranges among 4 persons such that each gets at least one orange is (A) 8 (B) 12 (C) 10 (D) 13

If the product $\left(\frac{1}{{}^{15}C_0} + \frac{1}{{}^{15}C_1}\right)\left(\frac{1}{{}^{15}C_1} + \frac{1}{{}^{15}C_2}\right) \cdots \left(\frac{1}{{}^{15}C_{12}} + \frac{1}{{}^{15}C_{13}}\right) = \frac{\alpha^{13}}{{}^{14}C_0 \cdot {}^{14}C_1 \cdot {}^{14}C_2 \cdots {}^{14}C_{12}}$, then $30\alpha$ is equal to
(A) 16
(B) 32
(C) 15
(D) 28

A bag contains 100 balls in which 10 are defective and 90 are nondefective balls. Find the number of ways to select 8 balls without replacement in which at least 7 balls should be defective?

On a coordinate plane, 12 points are arranged as shown in the figure to the right. If we are to select three points as vertices of a triangle, how many triangles are possible in total?
First, there are $\mathbf { K L M }$ ways to select three points from the 12 points.
Next, let us find how many ways it is possible to select three or more points in a straight line.
Let us look at the two cases.
(i) There are $\mathbf { N }$ straight lines that pass through four points.
(ii) There are $\mathbf { O }$ straight lines that pass through three points.
Hence, among all combinations of three points that are in a straight line and so cannot be the vertices of a triangle, $\mathbf { P Q }$ combinations belong to case (i), and $\mathbf { Q }$ combinations belong to case (ii).
Thus, the total number of possible triangles is $\mathbf{STU}$.
In particular, if we set $( 1,1 )$ as point A and $( 4,1 )$ as point B , then $\mathbf { V W }$ triangles have two vertices on segment AB.

On a coordinate plane, 12 points are arranged as shown in the figure to the right. If we are to select three points as vertices of a triangle, how many triangles are possible in total?
First, there are $\mathbf { K L M }$ ways to select three points from the 12 points.
Next, let us find how many ways it is possible to select three or more points in a straight line.
Let us look at the two cases.
(i) There are $\mathbf { N }$ straight lines that pass through four points.
(ii) There are $\mathbf { O }$ straight lines that pass through three points.
Hence, among all combinations of three points that are in a straight line and so cannot be the vertices of a triangle, $\mathbf { P Q }$ combinations belong to case (i), and $\mathbf { Q }$ combinations belong to case (ii).
Thus, the total number of possible triangles is $\mathbf{STU}$.
In particular, if we set $( 1,1 )$ as point A and $( 4,1 )$ as point B , then $\mathbf { V W }$ triangles have two vertices on segment AB.

In a box there are ten cards on which the numbers from 0 to 9 have been written successively. We take three cards out of the box using two methods and consider the probabilities.
(1) We take out three cards simultaneously.
(i) The probability that each number on the three cards is 2 or more and 6 or less is $\dfrac{\mathbf{KL}}{\mathbf{MN}}$.
(ii) The probability that the smallest number is 2 or less and the greatest number is 8 or more is $\dfrac { \mathbf { N O } } { \mathbf { P Q } }$.
(2) Three times we take out one card from the box, check its number, and then return it to the box. The probability that the smallest number is 2 or more and the greatest number is 6 or less is $\dfrac { \mathbf { R } } { \mathbf { S } }$.

We have four white cards, three red cards and three black cards. A different number is written on each of the ten cards.
(1) Choose two of the ten cards and put one in box A, and one in box B. There are $\mathbf{NO}$ ways of putting two cards in the two boxes.
(2) There are $\mathbf { P Q }$ ways of choosing two cards of the same color, and $\mathbf { R S }$ ways of choosing two cards of different colors.
Next, put the ten cards in a box and take out one card and without returning it to the box, take out second card.
(3) The probability that the two cards taken out have the same color is $\square\mathbf{T UV}$
(4) The probability that the color of the first card taken out is white or red, and the color of the second card taken out is red or black is $\frac { \mathbf { W X } } { \mathbf { Y } \mathbf { Y } }$.

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]

7. For APPLICANTS IN COMPUTER SCIENCE ONLY.

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.
(i) Consider the two-by-two version of the game with starting pattern [Figure]
Draw, in the blank patterns below, the eight different target patterns (including the starting pattern) that it is possible to obtain. [Figure]
What are the possible numbers of white counters that may be present in these target patterns?
(ii) 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.]
(iii) 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.

7.

For APPLICANTS IN COMPUTER SCIENCE ONLY.

Suppose you have an unlimited supply of black and white pebbles. There are four ways in which you can put two of them in a row: $B B , B W , W B$ and $W W$.
(i) Write down the eight different ways in which you can put three pebbles in a row.
(ii) In how many different ways can you put $N$ pebbles in a row?
Suppose now that you are not allowed to put black pebbles next to each other. There are now only three ways of putting two pebbles in a row, because $B B$ is forbidden.
(iii) Write down the five 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 restriction that black pebbles may not be next to each other, so $r _ { 2 } = 3$ and $r _ { 3 } = 5$.
(iv) Show that for $N \geq 4$ we have $r _ { N } = r _ { N - 1 } + r _ { N - 2 }$. Hint: consider separately the case where the last pebble is white, and the case where it is black.
Finally, suppose that we impose the further restriction that the first pebble and the last pebble cannot both be black. Let $w _ { N }$ be the number of such arrangements for $N$ pebbles; for example, $w _ { 3 } = 4$, since the configuration $B W B$ is now forbidden.
(v) For $N \geq 5$, write down a formula for $w _ { N }$ in terms of the numbers $r _ { i }$, and explain why it is correct.

7. For APPLICANTS IN COMPUTER SCIENCE ONLY.

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.
(i) Consider the two-by-two version of the game with starting pattern [Figure]
Draw, in the blank patterns below, the eight different target patterns (including the starting pattern) that it is possible to obtain. [Figure]
What are the possible numbers of white counters that may be present in these target patterns?
(ii) 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.]
(iii) 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.

7.

For APPLICANTS IN COMPUTER SCIENCE ONLY.

Suppose you have an unlimited supply of black and white pebbles. There are four ways in which you can put two of them in a row: $B B , B W , W B$ and $W W$.
(i) Write down the eight different ways in which you can put three pebbles in a row.
(ii) In how many different ways can you put $N$ pebbles in a row?
Suppose now that you are not allowed to put black pebbles next to each other. There are now only three ways of putting two pebbles in a row, because $B B$ is forbidden.
(iii) Write down the five 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 restriction that black pebbles may not be next to each other, so $r _ { 2 } = 3$ and $r _ { 3 } = 5$.
(iv) Show that for $N \geq 4$ we have $r _ { N } = r _ { N - 1 } + r _ { N - 2 }$. Hint: consider separately the case where the last pebble is white, and the case where it is black.
Finally, suppose that we impose the further restriction that the first pebble and the last pebble cannot both be black. Let $w _ { N }$ be the number of such arrangements for $N$ pebbles; for example, $w _ { 3 } = 4$, since the configuration $B W B$ is now forbidden.
(v) For $N \geq 5$, write down a formula for $w _ { N }$ in terms of the numbers $r _ { i }$, and explain why it is correct.

5. A total of 12 noughts and 4 crosses are arranged in 4 rows of 4 . One such arrangement is illustrated below.

0	0	$\times$	0
0	$\times$	0	$\times$
0	0	0	0
$\times$	0	0	0

(a) How many arrangements are there altogether?
(b) How many arrangements are there in which there is a cross in every row?
(c) How many arrangements are there in which there is a cross in every row and in every column?

A set of 12 rods, each 1 metre long, is arranged so that the rods form the edges of a cube. Two corners, $A$ and $B$, are picked with $A B$ the diagonal of a face of the cube.
An ant starts at $A$ and walks along the rods from one corner to the next, never changing direction while on any rod. The ant's goal is to reach corner $B$. A path is any route taken by the ant in travelling from $A$ to $B$.
(a) What is the length of the shortest path, and how many such shortest paths are there?
(b) What are the possible lengths of paths, starting at $A$ and finishing at $B$, for which the ant does not visit any vertex more than once (including $A$ and $B$ )?
(c) How many different possible paths of greatest length are there in (b)?
(d) Can the ant travel from $A$ to $B$ by passing through every vertex exactly twice before arriving at $B$ without revisting $A$ ? Give brief reasons for your answer.

7. For APPLICANTS IN COMPUTER SCIENCE ONLY.

Suppose we have a collection of tiles, each containing two strings of letters, one above the other. A match is a list of tiles from the given collection (tiles may be used repeatedly) such that the string of letters along the top is the same as the string of letters along the bottom. For example, given the collection
$$\left\{ \left[ \frac { \mathrm { AA } } { \mathrm {~A} } \right] , \left[ \frac { \mathrm { B } } { \mathrm { ABA } } \right] , \left[ \frac { \mathrm { CCA } } { \mathrm { CA } } \right] \right\}$$
the list
$$\left[ \frac { \mathrm { AA } } { \mathrm {~A} } \right] \left[ \frac { \mathrm { B } } { \mathrm { ABA } } \right] \left[ \frac { \mathrm { AA } } { \mathrm {~A} } \right]$$
is a match since the string AABAA occurs both on the top and bottom. Consider the following set of tiles:
$$\left\{ \left[ \frac { \mathrm { X } } { \mathrm { U } } \right] , \left[ \frac { \mathrm { UU } } { \mathrm { U } } \right] , \left[ \frac { \mathrm { Z } } { \mathrm { X } } \right] , \left[ \frac { \mathrm { E } } { \mathrm { ZE } } \right] , \left[ \frac { \mathrm { Y } } { \mathrm { U } } \right] , \left[ \frac { \mathrm { Z } } { \mathrm { Y } } \right] \right\} .$$
(a) What tile must a match begin with?
(b) Write down all the matches which use four tiles (counting any repetitions).
(c) Suppose we replace the tile $\left[ \frac { \mathrm { E } } { \mathrm { ZE } } \right]$ with $\left[ \frac { \mathrm { E } } { \mathrm { ZZZE } } \right]$.
What is the least number of tiles that can be used in a match? How many different matches are there using this smallest numbers of tiles? [0pt] [Hint: you may find it easiest to construct your matches backwards from right to left.] Consider a new set of tiles $\left\{ \left[ \frac { X X X X X X X } { X } \right] , \left[ \frac { X } { X X X X X X X X X X } \right] \right\}$. (The first tile has seven $\mathrm { X } _ { \mathrm { s } }$ on top, and the second tile has ten $\mathrm { X } _ { \mathrm { s } }$ on the bottom.)
(d) For which numbers $n$ do there exist matches using $n$ tiles? Briefly justify your answer.

5. For ALL APPLICANTS.

The Millennium school has 1000 students and 1000 student lockers. The lockers are in a line in a long corridor and are numbered from 1 to 1000.
Initially all the lockers are closed (but unlocked). The first student walks along the corridor and opens every locker. The second student then walks along the corridor and closes every second locker, i.e. closes lockers 2, 4, 6, etc. At that point there are 500 lockers that are open and 500 that are closed.
The third student then walks along the corridor, changing the state of every third locker. Thus s/he closes locker 3 (which had been left open by the first student), opens locker 6 (closed by the second student), closes locker 9 , etc.
All the remaining students now walk by in order, with the $k$ th student changing the state of every $k$ th locker, and this continues until all 1000 students have walked along the corridor.
(i) How many lockers are closed immediately after the third student has walked along the corridor? Explain your reasoning.
(ii) How many lockers are closed immediately after the fourth student has walked along the corridor? Explain your reasoning.
(iii) At the end (after all 1000 students have passed), what is the state of locker 100 ? Explain your reasoning.
(iv) After the hundredth student has walked along the corridor, what is the state of locker 1000 ? Explain your reasoning.

5. For ALL APPLICANTS.

Given an $n \times n$ grid of squares, where $n > 1$, a tour is a path drawn within the grid such that:

• along its way the path moves, horizontally or vertically, from the centre of one square to the centre of an adjacent square;
• the path starts and finishes in the same square;
• the path visits the centre of every other square just once.

For example, below is a tour drawn in a $6 \times 6$ grid of squares which starts and finishes in the top-left square. [Figure]
For parts (i)-(iv) it is assumed that $n$ is even.
(i) With the aid of a diagram, show how a tour, which starts and finishes in the top-left square, can be drawn in any $n \times n$ grid.
(ii) Is a tour still possible if the start/finish point is changed to the centre of a different square? Justify your answer.
Suppose now that a robot is programmed to move along a tour of an $n \times n$ grid. The robot understands two commands:

• command $R$ which turns the robot clockwise through a right angle;
• command $F$ which moves the robot forward to the centre of the next square.

The robot has a program, a list of commands, which it performs in the given order to complete a tour; say that, in total, command $R$ appears $r$ times in the program and command $F$ appears $f$ times.
(iii) Initially the robot is in the top-left square pointing to the right. Assuming the first command is an $F$, what is the value of $f$ ? Explain also why $r + 1$ is a multiple of 4 .
(iv) Must the results of part (iii) still hold if the robot starts and finishes at the centre of a different square? Explain your reasoning.
(v) Show that a tour of an $n \times n$ grid is not possible when $n$ is odd.

5. For ALL APPLICANTS.

This question concerns calendar dates of the form
$$d _ { 1 } d _ { 2 } / m _ { 1 } m _ { 2 } / y _ { 1 } y _ { 2 } y _ { 3 } y _ { 4 }$$
in the order day/month/year. The question specifically concerns those dates which contain no repetitions of a digit. For example, the date $23 / 05 / 1967$ is one such date but $07 / 12 / 1974$ is not such a date as both $1 = m _ { 1 } = y _ { 1 }$ and $7 = d _ { 2 } = y _ { 3 }$ are repeated digits.
We will use the Gregorian Calendar throughout (this is the calendar system that is standard throughout most of the world; see below.)
(i) Show that there is no date with no repetition of digits in the years from 2000 to 2099.
(ii) What was the last date before today with no repetition of digits? Explain your answer.
(iii) When will the next such date be? Explain your answer.
(iv) How many such dates were there in years from 1900 to 1999? Explain your answer. [0pt] [The Gregorian Calendar uses 12 months, which have, respectively, 31,28 or $29,31,30$, $31,30,31,31,30,31,30$ and 31 days. The second month (February) has 28 days in years that are not divisible by 4 , or that are divisible by 100 but not 400 (such as 1900 ); it has 29 days in the other years (leap years).]
Turn Over