CMI Entrance Exam 2020 Question Paper Solution B.Sc Maths & Computer

Solutions to 2020 Entrance Examination for BSc Programmes at CMI

Part A solutions

Part A is worth a total of 40 (= 4 × 10) points. Unless specified otherwise, each answer
is either a number (rational/real/complex) or, where appropriate, ∞ or −∞. If a desired
answer “does not exist” or is “not possible to decide”, state so. Write integer answers in the
usual decimal form. Write non-integer rationals as ratios of two integers.

A1. Each student in a small school has to be a member of at least one of THREE school
clubs. It is known that each club has 35 members. It is not known how many students are
members of two of the three clubs, but it is known that exactly 10 students are members of
all three clubs. What is the largest possible total number of students in the school? What
is the smallest possible total number of students in the school?

Answer: Let a, b, c be the numbers of students that are members of exactly one of the clubs
and x, y, z the numbers of students with double membership. Labelling a suitable Venn
diagram appropriately, we have a + x + y = b + y + z = c + x + z = 25. We want to find
max/min values of n = a + b + c + x + y + z + 10. Adding the three constraints we get
a + b + c + 2x + 2y + 2z = 75, giving n = 85 − (x + y + z). The maximum possible n
cannot be more than 85 and it is achieved when x = y = z = 0 and a = b = c = 25. For
minimum n we need to maximize x + y + z, which can be at most 37.5 (if we could take
a = b = c = 0), hence at most 37 as it needs to be an integer. This is achieved by, say
a = 1, b = c = 0, x = y = 12, z = 13 giving minimum n = 38 + 10 = 48.

A2. Let P be the plane containing the vectors (6, 6, 9) and (7, 8, 10). Find a unit vector that
is perpendicular to (2, −3, 4) and that lies in the plane P. (Note: all vectors are considered
as line segments starting at the origin (0, 0, 0). In particular the origin lies in the plane P.)

Answer: The desired vector is of the form v = t(6, 6, 9) + s(7, 8, 10) = (6t + 7s, 6t + 8s, 9t +
10s) and we need 0 = v · (2, −3, 4) = 2(6t + 7s) − 3(6t + 8s) + 4(9t + 10s) = 30t + 30s = 0.
Taking s = 1, t = −1, we get (1, 2, 1) and scaling it to a unit vector gives v = ±( √16 , √26 , √16 ).

A3. Calculate the following two definite integrals. It may be useful to first sketch the graph.
Z e2 Z 1
ln |x|
ln |x| dx dx
1 −1 |x|

R
Answer: Integrating by parts, ln |x| dx = x ln |x|−x+C, hence by the second fundamental
R e2 2
theorem of calculus, 1 ln |x| dx = (x ln |x| − x) |e1 = e2 + 1. For the second integral,
because of the discontinuity at 0, we need to break up the calculation there and take a limit.
2
Antiderivative of lnx|x| is (ln |x|)
2
. As x → 0+ , ln x → −∞. So the integral from 0 to 1 is −∞
and it is the same on the negative side because the integrand is even. So the final answer is
−∞ (which is better than saying undefined/does not exist).

1

A4. A fair die is thrown 100 times in succession. Find probabilities of the following events.
(i) 4 is the outcome of one or more of the first three throws.
(ii) Exactly 2 of the last 4 throws give an outcome divisible by 3 (i.e., outcome 3 or 6).
91
Answer: (i) 1 − ( 56 )3 = 216 (ii) 42 ( 13 )2 ( 23 )2 = 27
8


. .

A5. Write your answers to each question below as a series of three letters Y (for Yes) or N
(for No). Leave space between the group of three letters answering (i), the answers to (ii)
and the answers to (iii). Consider the graphs of functions

x3 x2 − x x3 − x
f (x) = 2 g(x) = h(x) = 3 .
x −x x3 x +x
(i) Does f have a horizontal asymptote? A vertical asymptote? A removable discontinuity?
(ii) Does g have a horizontal asymptote? A vertical asymptote? A removable discontinuity?
(ii) Does h have a horizontal asymptote? A vertical asymptote? A removable discontinuity?

Answer: (i) NYY (ii) YYN (iii) YNY

A rational function is continuous wherever it is defined and its only discontinuities are where
the denominator vanishes (so f is discontinuous at x = 0 and x = 1 and g and h only
at x = 0). Such a discontinuity is removable precisely when the rational function has a
(finite) limit at that x-value; otherwise the rational function has a vertical asymptote there,
3
because in that case the limit on either side must be ±∞. Now f (x) = x2x−x has a removable
discontinuity at (0, 0), vertical asymptote at x = 1 and f approaches ±∞ as x → ±∞, so
f has no horizontal asymptote. g has a vertical asymptote at x = 0, so the discontinuity
at x = 0 cannot be removed. g(x) approaches 0 as x → ±∞, so g(x) has X-axis as the
3 −x
horizontal asymptote. h(x) = xx3 +x has a removable discontinuity at (0, −1), no vertical
asymptote and h approaches 1 as x → ±∞, so h has y = 1 as the horizontal asymptote.

A6. Recall the function arctan(x), also denoted as tan−1 (x). Complete the sentence:

arctan(20202019) + arctan(20202021) 2 arctan(20202020),

because in the relevant region, the graph of y = arctan(x) .
Fill in the first blank with one of the following: is less than / is equal to / is greater than. Fill
in the second blank with a single correct reason consisting of one of the following phrases:
is bounded / is continuous / has positive first derivative / has negative first derivative / has
positive second derivative / has negative second derivative / has an inflection point.

Answer: “is less than” because in the relevant region (here the interval (0, ∞)), the graph
“has negative second derivative”, which ensures that any chord stays below the graph. The
point on the graph of y = arctan(x) at x = 20202020 is above the midpoint of the chord
joining the points at x = 20202019 and x = 20202021.

2

A7. The polynomial p(x) = 10x400 + ax399 + bx398 + 3x + 15, where a, b are real constants,
is given to be divisible by x2 − 1.
(i) If you can, find the values of a and b. Write your answers as a = ,b = . If it
is not possible to decide, state so.
(ii) If you can, find the sum of reciprocals of all 400 (complex) roots of p(x). Write your
answer as sum = . If it is not possible to decide, state so.

Answer: (i) By factor theorem, as x−1 and x+1 both divide p(x), we must have respectively
p(1) = 10+a+b+3+15 = 0 and p(−1) = 10−a+b−3+15 = 0. This gives a = −3, b = −25.
(ii) If roots are ri , then
P
X1 product of all roots except ri −coefficient of x/leading coefficient 1
= i = =− .
ri product of all roots constant term/leading coefficient 5

A8. For a positive integer n, let D(n) = number of positive integer divisors of n. For
example, D(6) = 4 because 6 has four divisors, namely 1, 2, 3 and 6. Find the number of
n ≤ 60 such that D(n) = 6.

Answer: There are 9 such n because n must have prime factorisation of type p2 q (giving
D(n) = (2 + 1)(1 + 1) = 6), or of type p5 (giving D(n) = 5 + 1 = 6). There are 8 possibilities
of the first type: 22 ×(3, 5, 7, 11 or 13), 32 ×(2 or 5), 52 × 2. Only 25 is of the second type.

A9. Notice that the quadratic polynomial p(x) = 1 + x + 21 x(x − 1) satisfies p(j) = 2j for
j = 0, 1 and 2. A polynomial q(x) of degree 7 satisfies q(j) = 2j for j = 0, 1, 2, 3, 4, 5, 6, 7.
Find the value of q(10).

Answer: Looking at the hint, recall that ni=0 ni = 2n . So, taking xi := x(x−1)···(x−i+1)
P


i!
,
P7 x

the polynomial p(x) = i=0 i satisfies
the given requirements (note that

for10
an integer
x 10
value of x that is < i, the value of i is 0). Therefore p(10) = 2 − 8 − 9 − 10
10


10
=
1024 − 45 − 10 − 1 = 968. (Given n + 1 distinct numbers xi , and a list of numbers yi , there
always exists a polynomial p(x) of degree at most n satisfying p(xi ) = yi . One can write such
p(x) explicitly by Lagrange interpolation but in this particular case a trick could be used.
Such a polynomial p(x) is also unique because the difference between two such polynomials
would have degree at most n but the difference would also have all n + 1 numbers xi as its
roots, forcing the difference to be the zero polynomial.)

A10. Note that 25 × 16 − 19 × 21 = 1. Using this or otherwise, find positive integers a, b
and c, all ≤ 475 = 25 × 19, such that

• a is 1 mod 19 and 0 mod 25,

• b is 0 mod 19 and 1 mod 25, and

• c is 4 mod 19 and 10 mod 25.

3

(Recall the mod notation: since 13 divided by 5 gives remainder 3, we say 13 is 3 mod 5.)

Answer: a = 400 = 25 × 16 = 1 + 19 × 21 is 1 mod 19 and 0 mod 25. Next, −399 =
−19 × 21 = −25 × 16 + 1 is 0 mod 19 and 1 mod 25, so take b = −399 + 475 = 76. Finally
4 × 400 + 10 × 76 = 2360 is 4 mod 19 and 10 mod 25, so take c = 2360 − 4 × 475 = 460. It is
easy to check that these work. This is an example of Chinese remainder theorem in action.
One can use the Euclidean algorithm to express gcd(25, 19) = 1 in the form 25 × 16 − 19 × 21,
but here this information is already given to you, so the answers can be just read off.

Part B solutions

Clearly explain your entire reasoning. No credit will be given without reasoning. Partial
solutions may get partial credit.

B1. [7 points] Suppose A, B, C, D are points on a circle such that AC and BD are diameters
of that circle. Suppose AB = 12 and BC = 5. Let P be a point on the arc of the circle from
A to B (the arc that does not contain points C and D). Let the distances of P from A, B, C
and D be a, b, c and d respectively. Find the values of a+b
c+d
and a−b
d−c
. You may assume d 6= c
so the second ratio makes sense.
Answer: Since AC and BD are diameters, all angles of ABCD are√ right angles (being angles
in a semicircle) and so ABCD is a rectangle. Its diameter is 13 = 122 + 52 . Use Ptolemy’s
theorem in PADB to get 12d = 13a + 5b and in PACB to get 12c = 5a + 13b. Add the two
equations to get a+b
c+d
= 32 . Subtract to get a−b
d−c
= 32 .
2πi
B2. [7 points] Let z = e( n ) . Here n ≥ 2 is a positive integer, i2 = −1 and the real number
2π
n
can also be considered as an angle in radians.

(i) Show that n−1 k
(ii) Show that 8k=0 cos(40k + 1)◦ = 0, i.e.,
P P
k=0 z = 0.

cos(1◦ ) + cos(41◦ ) + cos(81◦ ) + cos(121◦ ) + · · · + cos(241◦ ) + cos(281◦ ) + cos(321◦ ) = 0.
n 2πi
Answer: (i) z = cos( 2π
n
) + i sin( 2π
n
) 6= 1 so (1 + z + · · · + z n−1 ) = 1−z
1−z
= 1−e
1−z
= 0.
2πi
(ii) Take the equation in part (i) for n = 9. Multiply it by e( 360 ) and take the real part. Or
use cos(A + B) = cos A cos B − sin A sin B on the LHS with B = 1◦ , take out cos(1◦ ) as a
common factor from half the terms and sin(1◦ ) from the rest, and show using (i) that the
cos part and sin part in parentheses are each 0.
B3. [10 points] A spider starts at the origin and runs in the first quadrant along the graph
of y = x3 at the constant speed of 10 unit/second. The speed is measured along the length
of the curve y = x3 . Thepformula for the curve length along the graph of y = f (x) from
Rb
x = a to x = b is ` = a 1 + f 0 (x)2 dx. As the spider runs, it spins out a thread that is
always maintained in a straight line connecting the spider with the origin. What is the rate
in unit/second at which the thread is elongating when the spider is at ( 21 , 81 )?

4

You should use the following names for variables. At any given time t, the spider is at the
point (u, u3 ), the length of the thread joining it to the origin in a straight line is s and the
curve length along y = x3 from the origin till (u, u3 ) is `. You are asked to find ds dt
when
u = 21 . (Do not try to evaluate the integral for `: it is unnecessary and any attempt to do so
will not get any credit because a closed formula in terms of basic functions does not exist.)
Answer: s2 = u2 + u6√. Differentiate with respect to t to get 2s ds dt
= (2u + 6u5 ) du
dt
. Plug
17
1
in u = 2 to get s = 8 and dt = 4√17 dt at the point of interest. To calculate du
ds 19 du
dt
, we
d` d` du d`
use `. By chain rule dt = du dt . We are given dt = 10. By the fundamental theorem of
d`
√
calculus, du = 1 + 9u4 = 45 at u = 12 . Using these values first get du
dt
= 8 and then ds
dt
= √3817
unit/second.
B4. [12 points] Throughout this problem we are interested in real valued functions f satis-
fying two conditions: at each x in its domain, f is continuous and f (x2 ) = f (x)2 . Prove the
following independent statements about such functions. The hints below may be useful.
(i) There is a unique such function f with domain [0,1] and f (0) 6= 0.
(ii) If the domain of such f is (0, ∞), then (f (x) = 0 for every x) OR (f (x) 6= 0 for every x).
R∞
(iii) There are infinitely many such f with domain (0, ∞) such that 0 f (x) dx < 1.
Hints: (1) Suppose a number a and a sequence xn are in the domain of a continuous function
f and xn converges to a. Then f (xn ) must converge to f (a). For example f (0.5n ) → f (0)
1
and f (2 n ) → f (1) if all the mentioned points are in the domain of f . In parts (i) and (ii)
suitable sequences may be useful. (2) Notice that f (x) = xr satisfies f (x2 ) = f (x)2 .
Answer: Throughout the question the domain contains no negative real numbers, so all
numbers in the domain are squares and hence by f (x2 ) = f (x)2 , the output values of f can
only be nonnegative. (i) f (0)2 = f (0), so f (0) = 0 or 1, but we are given than f (0) 6= 0,
n
so f (0) = 1. Now take a ∈ (0, 1). Squaring repeatedly, we get the sequence a2 → 0. By
n n n
continuity of f , we have f (a2 ) → f (0) = 1. Since f (x2 ) = f (x)2 , we have f (a2 ) = f (a)2 ,
n
so f (a)2 → 1. For this to happen, the only possible (necessarily nonnegative) value of f (a)
is 1. Continuity forces f (1) = 1 as well. So only the constant function f (x) = 1 is possible.
√ √ p
(ii) Letting u = x2 in f (x2 ) = f (x)2 , we get f (u) = f ( u)2 , i.e., f ( u) = f (u). Suppose
f (a) = 0 and f (b) > 0 for positive real numbers a, b. Taking repeated square roots, we
−n −n −n −n
get two sequences a2 and b2 , both converging to 1. But f (a2 ) = f (a)2 → 0 and
−n −n
f (b2 ) = f (b)2 → 1, giving two values for f (1), which is a contradiction.
(iii) We may assume f (x) is never 0 on (0, ∞) and hence f (1) = 1. Since all powers of x
work we can splice suitable powers at x = 1 to get total integral less than 1. For finiteness,
in (0, 1] we must use xr with r > −1 and in [1, ∞), use xs with s < −1. This gives total
1 1
integral r+1 − s+1 , which is less than 1 for infinitely many combinations of r and s, e.g. take
r ≥ 1 and s < −3.

5

B5. [12 points] Consider polynomials p(x) with the following property, called (†).
(†) If r is a root of p(x), then r2 − 4 is also a root of p(x).
(i) We want to find every quadratic polynomial of the form p(x) = x2 + bx + c such that p(x)
has two distinct roots, has integer coefficients and has property (†). Prove that there are
exactly two such polynomials and list them in the provided space on a later page.
(ii) It is also true that there are exactly two cubic polynomials of the form p(x) = x3 +
ax2 + bx + c with the property (†) such that p(x) shares no root with the polynomials you
found in part (i). Explain fully how you will prove this along with the method to find the
polynomials, but do not try to explicitly find the polynomials.
Answer: (i) Let the set of two distinct roots be A = {r, s} and consider the function
f (x) = x2 − 4. The condition (†) ensures that this function maps the set A to itself. When
considered as a function on the set of roots, we will symbolically denote it by r → r2 − 4.
There are four possibilities for this function from A to A: (1) r → r and s → s (2) r → s
and s → r (3) r → s and s → s (4) r → r and s → r. In the first case, both r and s must be
roots of the polynomial x2 − x − 4, which does have two real solutions. In the second case we
have r → s → r, so f (f (r)) = (r2 − 4)2 − 4 = r and also f (f (s)) = s, so both r and s must
be roots of (x2 − 4)2 − 4 − x. This quartic polynomial MUST have x2 − x − 4 as a factor
(why?) and the roots of the remaining factor must automatically satisfy r → s → r (why?).
By long division one gets the other factor as x2 + x − 3, which also has two real roots.
In cases 3 and 4, one of the roots t is still a root of x2 − x − 4 and the other must and can be
−t, because f (x) = f (−x). However the resulting two polynomials of form (x − t)(x + t) do
not have integer coefficients, as can be seen explicitly by writing down the roots of x2 − x − 4.
(Note: The integer coefficients condition was mistakenly omitted in the exam, leading to
four polynomials instead of the claimed two. Therefore, part (i) was graded leniently and
anyone writing at least two correct polynomials, even in rough work, was given full credit.)
(ii) Similar, but now one has to argue that the only possibility is r → s → t → r with
r, s, t distinct. Proof: f (any root) must be a different root, because otherwise, this root
would satisfy the polynomial x2 − x − 4, contrary to the requirement of sharing no roots with
polynomials in part (i). Similarly for any two distinct roots, it is not possible for them to be
exchanged by f because then they would be roots of x2 + x − 3 from part (i). Now starting
with any root r, one must have f (r) = s distinct from r, then f (s) = t distinct from r and
s, and finally f (t) = r (because f cannot fix t, nor can it exchange t and s). So r, s, t satisfy
f (f (f (x))) = x, i.e., they are roots of ((x2 − 4)2 − 4)2 − 4 − x. Again this polynomial MUST
have x2 − x − 4 as a factor and dividing by it leaves a degree six polynomial, which MUST
factor into two cubics satisfying r → s → t → r. Justify these statements for yourself.
(Note: The missing condition in part (i) has no bearing on the answer to part (ii), but part
(ii) was still removed from the exam because its statement referred to the answer in part (i).
The few students who did valid work in part (ii) were unaffected by this decision.)
More complete picture for part (ii): In general (i.e. for condition (†) but now involving

6

a quadratic polynomial other than x2 − 4) the two cubics may have non-real roots but in
the given situation one can check that both cubics have real, in fact integer coefficients, e.g.
use an online tool such as www.wolframalpha.com/calculators/factoring-calculator to get

((x2 − 4)2 − 4)2 − 4 − x = (x2 − x − 4)(x3 − x2 − 6x + 7)(x3 + 2x2 − 3x − 5).

Since each cubic has at least one real root (by intermediate value theorem), all roots must be
real because the r → r2 − 4 condition cycles through all three roots. For a given polynomial
with, say, integer coefficients, which permutations of its roots are “valid” and which are not?
Such questions are properly formulated and studied in the famous Galois theory.
B6. [12 points] For sets S and T , a relation from S to T is just a subset R of S × T . If
(x, y) is in R, we say that x is related to y. Answer the following.
(i) A relation R from S to S is called antisymmetric if it satisfies the following condition: if
(a, b) is in R, then (b, a) must NOT be in R. For S = {1, 2, . . . , k}, how many antisymmetric
relations are there from S to S? (Parts (ii) and (iii) are independent of this part.)
Answer: (i) For antisymmetry,
the k elements (i, i) of S × S are ruled out. The remaining
k(k − 1) elements divide into k2 pairs of the form (i, j) and (j, i). For each such pair, one
k
can choose (i, j) OR (j, i) OR neither to include in the relation. So the answer is 3(2) .
(ii) Write a recurrence equation for f (k, n) = the number of non-crossing relations from
{1, 2, . . . k} to {1, 2, . . . n} that have no isolated elements in either set. (See below for the
definitions of the two underlined terms and their visual meaning. Drawing pictures may be
useful.) Your recurrence should have only a fixed number of terms on the RHS.
(iii) Using your recurrence in (ii) or otherwise, find a formula for f (3, n).
Definition 1: We say that a relation from S to T has no isolated elements if each s in S is
related to some t in T and if for each t in T , some s in S is related to t.
Definition 2: We say that a relation R from {1, 2, . . . k} to {1, 2, . . . n} is non-crossing if
the following never happens: (i, x) and (j, y) are both in R with i < j but x > y.
Visual meaning: one can visualise a relation R very similarly to a function. List 1 to k as
dots arranged vertically in increasing order on the left and similarly list 1 to n on the right.
For each (s, t) in R, draw a straight line segment from s on the left to t on the right. In
the situation one wants to avoid for non-crossing relations, the segments connecting i with x
and j with y would cross. Having no isolated elements also has an obvious visual meaning.
Answer: (ii) The element 1 in each set has to be connected with 1 in the other. Now exactly
one of three things happens: 1 in S is connected to 2 in T , 2 in S is connected to 1 in T or 1
in neither set is connected to anything other than 1 in the other set. We get the recurrence
f (k, n) = f (k, n − 1) + f (k − 1, n) + f (k − 1, n − 1) with f (k, 1) = f (1, n) = 1. Draw a
picture to see how the non-crossing condition makes this work.
(iii) By the recurrence, get f (2, n) = 2n − 1 and then f (3, n) = 2n2 − 2n + 1, both for n ≥ 1.

7