CHENNAI MATHEMATICAL INSTITUTE

Solutions of M.Sc. Data Science Entrance Examination 2023

Multiple-choice questions

1. Six children — Abhay, Bhavna, Charanjit, Divya, Enakshi and Farid — are
sitting, in that order, around a circular table at a birthday party, as shown on
the right. Each of them may be seated or standing.
They play a game, as follows. The birthday girl’s father calls out the initials
of a pair of children seated next to each other. The children whose initials are
called out then change their position from sitting to standing or vice versa.
Initially, all children are seated. Which of the following announcements will
result in an arrangement where Abhay and Enakshi are standing and the other
four children are seated?
(a) F A, DE, BC, CD, AB, F A
(b) AB, BC, DE, EF, EF, DE
(c) AB, CD, BC, EF, DE, EF
(d) AB, CD, F A, BC, AB, DE

Solution: (a) F A, DE, BC, CD, AB, F A and (c) AB, CD, BC, EF, DE, EF .
If a child’s name is called out an even number of times, the final position is the same as the initial position.
If it is called out an odd number of times, the final position is different from the initial position. We need
the parity of A and E to be odd and the rest to be even.

2. Consider the following single variable, real valued functions:

x4 + 1 x3 − x
f (x) = ; g(x) = .
x3 − 1 x3 + x
Which of the following is/are true?

(a) The function f has a removable discontinuity at 1 and g has it at 0.

(b) Only g is continuous everywhere.
(c) As x tends to ∞ f (x) also tends to ∞.
(d) The range of g is bounded.

Solution: FFTT.

(a) limx→1− f (x) = −∞ and limx→1+ f (x) = ∞, so f does not have a removable discontinuity at 1. So:
False.
(b) f is not continuous at x = 1. The function g is not defined at x = 0, so g is continuous at x = 0. So:
False.
(c) True, since x4 has a higher degree than x3 − 1.
(d) True, the range is between −1 and 1. Both g(x) < −1 and g(x) > 1 yield contradictions.

3. Let n be a positive integer such that

1 1 1 1
+ + +
2 3 7 n
is an integer. Which of the following is/are true?

1
 (a) n has to be even.
(b) 3 does not divide n
(c) 7 divides n
(d) 5 does not divide n
41
Solution: TFTT. The sum is 42 + n1 . Since this has to be an integer, n can only be 42.

4. Let a1 < a2 < a3 < a4 < . . . < . . . be a sequence of infinitely many positive integers which are in arithmetic
progression. Furthermore, suppose a2 , a4 , a8 are in geometric progression. Which of the following is/are
true?

(a) For every positive integer n, there is a triple of numbers ai < aj < ak which are in geometric progression
with ratio n, i.e. aj = ai n, ak = aj n.
(b) If i < j then ai divides aj .
(c) There are only finitely many n for which there are infinitely many triples i < j < k with ai , aj , ak in
arithmetic progression with common difference n.
(d) a10 , a30 , a90 are in geometric progression.

Solution: We have a, a + r, a + 2r, a + 3r and (a + 3r)2 = (a + r)(a + 7r). Therefore r = a and an = na. So
TFFT.

5. Let A be a 20 × 11 matrix with real entries. After performing some row operations on A, we get a matrix
B which has 12 nonzero rows. Which of the following is/are always true?

(a) The rank of A is 12.

(b) The ranks of A and B are not related.
(c) If v is a vector such that Av = 0 then Bv is also 0.
(d) The rank of B is at most 11.

Solution: FFTT

(a) False. E.g.: Suppose A had 12 identical nonzero rows (and the rest all zeroes) to start with, and we
swapped two rows to get B, which also has exactly 12 nonzero rows. The rank of A is 1.
(b) False. Follows from the definition; “row or column operations do not change the rank”.
(c) True. Same reason as above; the null space is unchanged.
(d) True. B has 11 columns so its rank cannot be more.

6. Let f be a single-variable, real-valued function such that all its derivatives exist. We say that f changes sign
at some point x0 in the domain if f (x0 + ) · f (x0 − ) < 0 holds for small enough, positive .

• A point x0 in the domain is called a turning point of f , if the first derivative f 0 changes sign at x0 .
• A point x0 in the domain is called flex point of f , if the second derivative f 00 changes sign at x0 .

Which of the following statements is/are true?

(a) If x0 is a flex point of f then f 00 (x0 ) = 0.

(b) If f 0 (x0 ) = 0 then x0 is a turning point of f .
(c) If f 00 (x0 ) = 0 then x0 is a flex point of f .
(d) If x0 is a flex point of f then f 0 (x0 ) 6= 0.

2
 Solution: TFFF. Truth of (a) follows from the definition. Consider the function x 7→ x3 ; at the only critical
point x = 0 the first derivative does not change sign. The same function works as a counter example for (d);
x = 0 is a flex as well as critical point. For (c) consider x 7→ x4 , the second derivative vanishes at 0 but does
not change its sign.

7. Solitaire Tic-Tac-Toe is a new game on the market. Instead of adding X’s and O’s to an empty 3 × 3 grid,
you start with a 3 × 3 grid in which every position already has an X or an O. In each move, you select a row,
column or diagonal and reverse all the entries along the chosen line: all X’s become O’s and all O’s become
X’s.
For instance, here is a sequence of possible moves.

X O X Bottom X O X SW-to-NE Middle

−−−−−−→ −−−−−−−−→ X O O −−−−−→ X X O
O X O row O X O diagonal O O O column O X O
X O X O X O X X O X O O

Given an arrangement S, we want to explore all arrangements of the grid that we can generate starting with
S. What is the smallest number m such that each such arrangement can be reached using at most m moves,
starting with S?

(a) 8
(b) 16
(c) 64
(d) 256

Solution: (a) 8.
There are 3 rows, 3 columns and 2 diagonals. At most you can select each of the 8 possible moves once. A
second selection undoes the effect of the move.

8. A bug starts walking from the origin of a two dimensional plane. It walks 1 step up, 1/2 step to the left
then 1/4 step down, then 1/8 step to the right, then 1/16 step up and so on, forever. In (x, y)-coordinates,
its final position is given by

(a) (− 32 , 45 )
(b) (− 25 , 43 )
(c) (− 52 , 45 )
(d) (− 23 , 43 )

Solution (c) (− 25 , 45 ): x-coordinate is

−1/2 2
−1/2 + 1/8 − 1/32 + . . . = =−
1 + 1/4 5

y-coordinate is
1 4
1 − 1/4 + 1/16 − . . . = =
1 + 1/4 5

9. Let A, B, C be events such that P (A) = P (B) = P (C) = 0.5, P (A ∩ B) = 0.3, P (A ∩ C) = 0. Which of the
following is/are true?

(a) P (A ∪ B) = 0.75
(b) P (A ∪ C) = 1
(c) P (B ∩ C) = 0.2

3
 (d) P (B ∪ C) = 0.9

Solution: (b), (c) FTTF . (a) is false since P (A ∪ B) = P (A) + P (B) − P (A ∩ B) = 0.7. (b) is true
since P (A ∪ C) = P (A) + P (C) − P (A ∩ C) = 1. (c) is true since, in view of (b) C = Ac and thus
P (B) = P (B ∩ A) + P (B ∩ C). (d) Using (c) it follows that P (B ∪ C) = 0.8.

10. The mean and variance of a data set of size n ≥ 100 are 1.1 and 4.3 respectively. It was then discovered that
one data point was wrongly recorded as -0.9 and should be ignored. Then we can conclude that the mean µ
and variance σ 2 of the n − 1 data points satisfy

(a) σ 2 < 4.3

(b) σ 2 > 4.3
(c) µ > 1.1
(d) µ < 1.1.

Solution: FTTF Since the dropped data point is below the mean, the new mean will only go up. Since the
gap between the mean and the dropped data (2) is less that the standard deviation (sqrare root of 4.3), the
variance will increase also.

11. An n × n matrix A = (aij ) is said to be antisymmetric if aij = −aji for all 1 ≤ i, j ≤ n. Which of the
following is/are true?

(a) If A is antisymmetric then all its principal diagonal entries are zero.
(b) If A, B are antisymmetric matrices then the product AB need not be antisymmetric.
(c) If A is antisymmetric then A2 is symmetric.
(d) Every nonzero 3 × 3 antisymmetric matrix is invertible.

Solution: TTTF. (a) follows from the definition. For (b) even a 2 × 2 example works. (c) also follows from
the definition. For (d) use the fact det(AT ) = det(A). Since AT = −A for the 3 × 3 case we have det(A) is
−det(A).

12. Consider the set S = {0, 1, 2, . . . , n − 1} ; n ≥ 2. Let x be an element sampled uniformly at random from S.
Let y denote (x + 2n ) mod n. Which of the following statements is/are true?
√ √
(a) Pr y = b n − 1c = b n−1c
 
n
(b) Pr[x = a, y = b] = Pr[x = a] · Pr[y = b] for all a, b ∈ S
(c) y is always an element of S
(d) Pr [y = blog2 (n − 1)c] = 1/n

Solution: FFTT.
(a) and (d): Since x is a uniformly random element in S, the value y = (x + t) mod n is also a uniformly
random element in S, for any deterministically chosen t. Hence, the probability that y equals a specific
element in S is 1/n.
(c): Clearly, y belongs to S by definition.
(b): The random variable y depends on x. Hence, (b) is false.

13. A perfect shuffle of a deck of cards divides the deck into two equal parts and then interleaves the cards from
each half, starting with the first card of the first half.
For instance, if we shuffle a deck of cards containing 10 cards arranged [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], we first
create two equal decks with cards [1, 2, 3, 4, 5] and [6, 7, 8, 9, 10] and then interleave them to get a new deck
[1, 6, 2, 7, 3, 8, 4, 9, 5, 10].
We start with the deck [8, 1, 4, 5, 3, 6, 2, 7] and keep shuffling. Which card(s) will never appear next to 5?

4
 (a) 1
(b) 2
(c) 7
(d) 8

Solution: (d) 8
The shuffles cycle through three decks, [8, 1, 4, 5, 3, 6, 2, 7], [8, 3, 1, 6, 4, 2, 5, 7] and [8, 4, 3, 2, 1, 5, 6, 7].

14. Consider the following pseudocodes of two functions, where u % 2 denotes the remainder when u is divided
by 2. The function abs(v) returns the absolute value of an integer v.
function foo1 ( u ):
if u % 2 == 0 AND abs ( u ) > 0:
u = u + foo2 (u -1)
return u

function foo2 ( v ):
if v % 2 == 1 AND abs ( v ) > 1:
v = v + foo1 (v -1)
return v

Which of the following is/are true?

(a) foo1, when called on a positive integer u, returns u(u + 1)/2

(b) foo2, when called on an odd positive integer v, returns v(v + 1)/2
(c) foo2(-13) goes into infinite recursion
(d) foo1(14) returns 105

Solution: FTTT
(a) is false since for an odd integer it returns the odd integer. (b) is true. Starting with an odd integer,
it adds that number to the result of foo1 applied to an even integer. foo2(1)=1. foo1(2)=3. Now we can
proceed by induction to show that foor2 on an odd integer computes u(u+1)/2 and foo1 on an even integer
computes u(u+1)/2.

15. Which of the following statement(s) is/ are true?

(a) (2023!)2 < (2023)2023 .

√ 21
(b) 2 7
>28.
1 √
(c) e e < 2.
1+log10 5
(d) log10 7 < 2 .

Solution: FTFT (a) is False; for √ 3 ≤ k ≤ n, we have

√ large enough n and √ k(n − k + 1) > n implying that
n! · n! > nn . (b) is True; note 63 < 8 implies 3 7 < 8, so 21 < 8 7. (c) is False; use derivatives to
1
show that the function x x is increasing on (−∞, e). (d) is True; since 49 < 50 and log is increasing so
2 log 7 < log 5 + log 10.

16. Let X, Y , Z be sets. Which of the following statement(s) is/are true?

(a) Let f : X → Y , g : Y → Z be functions. such that the composite function g ◦ f : X → Z is onto. Then
both g, f have to be onto.
(b) Assume the cardinality of X, |X|, is less than |Y | and assume |X| ≤ |Z|. There exists a one-one function
f : X → Y and g : Y → Z which is not one-one such that g ◦ f : X → Z is one-one.

5
 (c) Let idX be the identity function, idX : X → X, such that idX (x) = x for all x ∈ X. Let f : X → Y be
a function. There exists a function g : Y → X such that g ◦ f = idX .
(d) Denote by idY the identity function on Y , idY (y) = y for all y ∈ Y . Let f : X → Y be a function.
There exists g : Y → X such that f ◦ g = idY if and only if f is onto.

Solution: FTFT. (a) is false. g has to be onto f need not be. b is true. Y has more cardinality than X. g
can be chosen so that it maps the image of f one-one. What it does to elements outside the image we do
not care. c is false. This is true only when f is one-one since we want identity on X. d. Since we want every
element in Y to be covered, f better be onto. In that case we can find such a g.

17. Consider the following real valued functions defined on appropriate domains:
x
f (x) = , g(x) = x ln(x).
x + sin x
Which of the following is/are true?

(a) Limit as x → 0 of f (x) is 12 .

(b) Limit as x → 0+ of g(x) does not exist.
(c) Limit as x → ∞ of f (x) is finite.
(d) Limit as x → ∞ of g(x) is finite.

Solution: TFTF. For (a) use L’Hopital to get the answer. Again using L’Hopital we see that answer for (b)
is 0. For part (c) L’Hopital is useless, instead sandwich theorem gives the answer 1. Since g is an increasing
function (d) is clearly false.

18. Consider the pseudocode below. Here n % 6 denotes the remainder when n is divided by 6. The notation n
// 2 stands for integer division by 2. For example, 15 // 2 = 7, 36 // 2 = 18, 49 // 2 = 24, . . .
function sixer ( n ):
count = 0
while n > 0:
if n % 6 == 0:
n = n - 1
else :
n = n //2
count = count + 1
return count

Which of the following is true when sixer(n) is invoked with sufficiently large n, say n ≥ 106 ?

(a) The value of count is approximately n/6

(b) The value of count is approximately n/2
(c) The value of count is approximately log2 (n)
(d) The value of count is approximately (log2 (n))2

Solution (c). The key observation is that whenever the code executes the “if” block, in the immediately
following iteration, it executes the “else” block. Clearly, the “else” block can be executed at most dlog2 ne
many times on input n. The statement follows.

19. In a football league, a collection of teams play against each other a number of times. A team gets 3 points
for each match that it wins, 1 point for each match that it draws and 0 points for each match that it loses.
The following table gives the point standings after four teams have played a total of 7 matches. At this
stage, each team has played every other team at least once.

6
 Team Matches Points
Kolkata 4 8
Delhi 4 4
Chennai 3 4
Mumbai 3 1

How many matches have been drawn so far?

(a) 3
(b) 4
(c) 5
(d) 6

Solution: (b) 4
To reach 8 points, Kolkata must have won 2 matches and drawn 2 matches. With only 1 point from 3
matches, Mumbai has drawn 1 match. Delhi and Chennai with 4 points have drawn at least 1 match each.
Across all teams, the number of drawn matches must be even, so either Chennai or Delhi must have drawn
2 matches. But Chennai cannot have drawn 2 (or 3) matches out of 3 and ended up with 4 points. So Delhi
has drawn at least 2 matches. The only way it can then end up with 4 points is to draw all 4 of its matches.
So Chennai has drawn only 1 match, and Delhi has drawn 4, making 4 draws overall.

20. A new game show on TV has 100 boxes numbered 1, 2, . . . , 100, each containing a mystery prize. The
prizes are of different types, a, b, c, . . . , in decreasing order of value, and are distributed randomly among
the boxes. The most expensive item is of type a, a diamond ring, and there is exactly 1 of these. You are
told that the number of items at least doubles as you move to the next category — there are at least twice
as many items of type b as of type a, at least twice as many items of type c as of type b and so on.
You ask for the type of item in box 45. Instead of being given a direct answer, you are told that there are
31 items of the same type as box 45 in boxes 1 to 44 and 43 items of the same type as box 45 in boxes 46
to 100.
Which of the following statements can be true?

(a) There are exactly 3 types of prizes.

(b) There are exactly 4 types of prizes.
(c) There are exactly 5 types of prizes.
(d) There are exactly 6 types of prizes.

Solution: (a), (b) and (c)

There are 31 + 1 + 43 = 75 items of the same type as box 45. This leaves 25 items of other types. If there
were 5 other types, you would have at least 1 item of type a, 2 items of type b, 4 items of type c, 8 items of
type d and 16 items of type e. This adds up to 31 items, but there are only 25 items of type different from
the contents of box 45. So there can be at most 4 types other than the type in box 45, or 5 types in all. We
can have 3 types of prizes with counts [1, 24, 75], 4 types with counts (for example) [1, 2, 22, 75] and 5 types
with counts (for example) [1, 2, 4, 18, 75].

7
 Part (B) - Short-answer questions

For questions in part (B), you have to write your answer with a short explanation in the space provided for the
question in your answer sheet. If you need more space, you may continue on the pages provided for rough work.
Any such overflows must be clearly labeled.

1. There are 5 friends A, B, C, D, E. Because of a heated argument not all of them are on speaking terms
anymore. The array below describes who is talking to whom. A value of 1 indicates that the pair is on
speaking terms, while a 0 indicates that they are not.

A B C D E
A - 1 1 1 1
B 1 - 1 0 1
C 1 1 - 1 0
D 1 0 1 - 1
E 1 1 0 1 1

A gossip route is an ordered sequence of all the five friends such that every person hears the gossip from
exactly one friend (with whom they are on speaking terms) and shares it with exactly one other friend (with
whom they are on speaking terms). The friend who starts the gossip doesn’t hear it from anyone else and
the fifth friend doesn’t pass it on to anybody.
Answer the following questions:

(a) Suppose A starts spreading gossip along a gossip route and E hears it the last. Who is the third person
to hear it?
(b) List all the gossip routes from B to E.
(c) There is another dispute between the friends. As a result, A is now not speaking with B and D. List
all the gossip routes starting from A.

Solution: The given matrix is the adjacency matrix of a graph on 5 vertices. A gossip route is a Hamiltonian
path. It is easy to answer once the graph is drawn.

(a) There are only 2 Hamiltonian paths - ABCDE and ADCBE. In both the cases C is the third person
on the route. Either B or D is the third person to hear it.
(b) The routes are BCADE, BACDE, BCDAE.
(c) ACDEB, ACBED and AEBCD, AEDCB.

2. Two friends A and B are playing a coin flipping game with a fair coin, based on the following rules:

• When A flips the coin

– If it is heads then A wins and the game ends.
– If it is tails then B gets to flip the coin.
• When B flips the coin
– If it is heads then B wins and the game ends.
– If it is tails then A gets to flip the coin.
• The flipping continues till someone gets heads.

Suppose A is the first player to flip the coin. What is the probability that A will win the game.

8
 Solution: Answer 23 . Probability that A will on their first flip is 1/2. If not, then B has to flip and get tails
so A can flip a second time. Probability that A wins on their second flip is (1/2)3 . In general the probability
that A wins on their nth flip is (1/2)2n−1 . So the probablility that A wins is
X 1
P (A wins) = ( )2n−1
2
n≥0
1X 1 n
= ( )
2 4
n≥0
1 1
= × 1
2 1− 4
2
= .
3
3. Consider the following real valued function defined on the entire set of real numbers:
1
f (x) = .
1 + e−x
Show that f 0 (x) = f (x)(1 − f (x)).
Solution:

f 0 (x) = −(1 + e−x )−2 (−e−x )

e−x
=
(1 + e−x )2
e−x 1
= −x
·
1+e 1 + e−x
−1 + 1 + e−x
= · f (x)
1 + e−x
= (1 − f (x))f (x).

4. Let f be the following function defined on integers:

1
f (n) = √
3n + 3
√ h i
Compute 3 f (−5) + f (−4) + f (−3) + · · · + f (4) + f (5) + f (6)
Solution: 6
1
f (−n) = √ ,
3−n + 3
so f (n) is not even. Now we consider 1 − n
1 1 1 3.3n 3n
f (1 − n) = √ = √ = √ = √ = √
3 1−n + 3 3 3 3 9+3.3n 3 3(3 + 3n 3) (3 + 3n 3)
3n + 3 3.3n

Now we can express

√
3
f (n) = √ .
n
3 3+3
Adding f (n) and f (1 − n), we have
√ √
3 + 3n 3n + 3 1
f (n) + f (1 − n) = √ =√ √ =√
n
3 3+3 n
3(3 + 3) 3

9
 1
f (−5) + f (6) = √
3
1
f (−4) + f (5) = √
3
1
f (−3) + f (4) = √
3
1
f (−2) + f (3) = √
3
1
f (−1) + f (2) = √
3
1
f (0) + f (1) = √
3
−−−−−−−−− − −−−−−−−−−−−−−−−−−−
h i 6
f (−5) + f (−4)+ · · · +f (5) + f (6) = √
3

5. Find the determinant of the following 5 × 5 matrix:

 
1 2 0 0 0
2 5 2 0 0
 
0 2 5 2 0
 
0 0 2 5 2
0 0 0 2 5

Solution: The determinant is 1. Easy way to see that is to perform row operations to get an upper triangular
matrix with 1’s on the diagonal.

6. Find the limit !

1
lim x − x cos √
x→∞ x

Solution:

10
 !
1
L = lim x − x cos √
x→∞ x
!
1
= lim x(1 − cos √ )
x→∞ x
(1 − cos √1x )
!
= lim 1 Apply L’Hopital’s Rules
x→∞
x
sin ( √1x )(− 2x13/2 )
!
= lim
x→∞ − x12
√
sin (1/ x) !
1
− 3/2
2x
= lim
x→∞ − x12
!
1 1 1
= lim x 2 sin ( √ )
x→∞ 2 x
1 1
 1 
= lim x 2 sin √
2 x→∞ x
 
1 sin √1x
= lim 1 Apply L’Hopital’s Rules
2 x→∞ x2
  
cos √1 − 1
1 x 2x3/2
= lim 1
2 x→∞ − 2x3/2
1  1  1
= lim cos √ =
2 x→∞ x 2

7. Let N = 2150 . How many bits are required to write N in binary (base 2)? How many digits are required to
write N in decimal (base 10)? You may assume that log10 2 = 0.30103.
Solution: Bits: 151. In decimal, we want k such that
10k−1 ≤ 2150 < 10k
Solving we get k − 1 ≤ 150 ∗ 0.30103 < k. That is k − 1 ≤ 45.15 < k. So we need 46 digits.
8. A domino is a sheet of paper with one number from {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} printed on each half. For example,
a 4−4 domino has 4 printed on both halves. A 0−4 domino has 0 printed on one half and 4 on the other
half. The order is not important, so a 0−4 domino is the same as a 4−0 domino.
A complete set of dominos is a set of dominos containing exactly one copy of each different domino.

(a) How many dominos are there in a complete set of dominos?

(b) In how many ways can you select 2 dominos from a complete set so that at least one of the dominos
has a 0 on it and at least one of the dominos has a 9 on it.

Solution: We have 10 dominos of the kind a−a with the same number on each half. And 10


2 = 45 dominos
with different numbers on the two halves. So a complete set has 10 + 45 = 55 dominos.
For part (b), if one of the selected dominos is 0−9, the other can be any other domino, so we have 54 choices
for the second in this case. Otherwise one domino has a 0 and the other has a 9. The domino with a 0 can
have any of 0, 1, 2, 3, 4, 5, 6, 7, 8 along with it, so 9 choices. If the second has a 9 the other number on it is
one of 1, 2, 3, 4, 5, 6, 7, 8, 9, again 9 choices. So a total of 81 choices for the two, in all. Adding the 54 we have
81 + 54 = 135.

11
 9. There are three classrooms, C1 , C2 , and C3 . In C1 there are 5 boys and 5 girls. C2 has 3 boys and 5 girls.
C3 has 5 boys and 3 girls. We select a classroom and then a student in the classroom. The probability of
3 3 4
selecting classrooms C1 , C2 , and C3 are 10 , 10 , and 10 , respectively. Once a room is selected, a student is
picked uniformly at random from the class.

(a) What is the probability that the selected classroom is C3 and the chosen student is a girl?
(b) What is the probability that the selected classroom is C3 given that the chosen student is a girl?

Solution:
Given information

• C1 has 5 boys and 5 girls

• C2 has 3 boys and 5 girls
• C3 has 5 boys and 3 girls
• P (C1 ) = 3/10, P (C2 ) = 3/10 and P (C3 ) = 4/10.
• Random Experiment: A class is chosen at random and then a student is chosen at random from the
class.

3 4 3
P (C3 and girl) = P (C3 ∩ girl) = P (girl|C3 )P (C3 ) = × =
8 10 20

P (girl|C3 )P (C3 ) 3/20

P (C3 |girl) = =
P (girl) P (girl)

P (girl) = P (girl|C1 )P (C1 ) + P (girl|C2 )P (C2 ) + P (girl|C3 )P (C3 )

5 3 5 3 3 4
= × + × + ×
10 10 8 10 8 10
3 3 3 12 + 15 + 12 39
= + + = = .
20 16 20 80 80
Plugging this we get
P (girl|C3 )P (C3 ) 3/20 3/20 12 4
P (C3 |girl) = = = = = .
P (girl) P (girl) 39/80 39 13

10. How many integers in the set {1, 2, . . . , 1000} are relatively prime to 1000? Recall that two integers are
relatively prime if the only common factor they have is 1.
Solution: 1000 = 23 ∗ 53 , so we need to remove integers which have 2 or 5 as factors. The number of
integers with 2 as a factor are 500, those with 5 as a factor are 200. However their intersection contains
numbers which are divisible by 10, and that is 100 numbers in all. So the number to be weeded out is
500 + 200 − 100 = 600. Remove these and we are left with 400.
11. Is the following inequality true, given that n is a positive integer?
Z n+1
ln x dx ≤ ln n!
1

Justify your answer.

Solution: ln n! = ln 1 + ln 2 + . . . ln n. Take ln(x) from x = 1 to x = n + 1. The expression ln n! can be
thought of as the integral of the step function lnbxc, for x in the given range. But lnbxc ≤ ln x,so the integral
of the step function is less than the integral of ln x in the given range of x. The statement is false.

12
12. Football teams T1 and T2 play two games against each other in the Premier League. It is assumed that the
outcomes of the two games are independent of each other. The probabilities of T1 winning, drawing and
losing against T2 are 12 , 61 and 13 respectively. Each team gets 3 points for a win, 1 point for a draw and 0
points for a loss in a game. Let X and Y denote the total points scored in these two games by team T1 and
T2 , respectively.

(a) Find P (X = Y ).
(b) Find E(X).

Solution: There are 9 possible outcomes. Write down all 9 possible outcomes for T1 and corresponding X
and Y .
1st Match 2nd Match X Y
w w 6 0
w d 4 1
w l 3 3
d w 4 1
d d 2 2
d l 1 4
l w 3 3
l d 1 4
l l 0 6

(a) From the above table we have

P (X = Y ) = P (wl)+P (dd)+p(lw) = P (w)P (l)+P (d)P (d)+P (l)P (w) = 1/2∗1/3+1/6∗1/6+1/3∗1/2 = 13/36

(b) We can calculate the expectation:

E(X) = 6P (ww) + 4P (wd) + 3P (wl)

4P (dw) + 2P (dd) + 1P (dl)
3P (lw) + 1P (ld) + 0P (ll)
= 6P (w)P (w) + 4P (w)P (d) + 3P (w)P (l)
4P (d)P (w) + 2 ∗ P (d)P (d) + 1P (d)P (l)
3P (l)P (w) + 1P (l)P (d)
= 6 ∗ 1/2 ∗ 1/2 + 4 ∗ 1/2 ∗ 1/6 + 3 ∗ 1/2 ∗ 1/3
4 ∗ 1/6 ∗ 1/2 + 2 ∗ 1/6 ∗ 1/6 + 1 ∗ 1/6 ∗ 1/3
3 ∗ 1/3 ∗ 1/2 + 1 ∗ 1/3 ∗ 1/6
120
= ≈ 3.33
36

13. Let A, B and C denote arrays of real numbers, where B has n-1 entries and A, C have n entries each. Consider
the following algorithm involving the three given arrays.
for k from 2 to n :
t = B [k -1]
B [k -1] = t / A [k -1]
A [ k ] = A [ k ] - t * B [k -1]
end for
for k from 2 to n :
C [ k ] = C [ k ] - B [k -1] * B [k -1]
end for

13
 C [ n ] = C [ n ]/ A [ n ]
for k from n -1 to 1 with steps of -1:
C [ k ] = ( b [ k ]/ A [ k ]) - B [ k ] * b [ k +1]
end for

An arithmetic operation involves addition, subtraction, multiplication or division of real numbers. How
many arithmetic operations, in total, are performed in the algorithm above?
Note: Integer subtraction in array indices, like B[k-1], is not to be counted as an arithmetic operation.
Solution: Answer: 8n − 7 or 8(n − 1) + 1. During each pass of the first for loop one division, one subtraction
and one multiplication is performed. So there are 3(n − 1) arithmetic operations. There are 2(n − 1)
operations in the second for loop and 3(n − 1) operations in the last for loop. The total is 8(n − 1) + 1 or
8n − 7.

14. In the following pseudocode, A denotes an array and len(A) denotes the number of elements in that array.
The array is indexed from 1 to len(A). Write down the array A after each iteration of the for loop when the
input array is <20, 3, 9, 12, 70, 6>.
function weirdify ( A ):
for i from 1 to len ( A ):
if i % 2 == 0:
A [ i ] = A [ i /2]* A [ i ]
else if i * i > len ( A ):
A [ i ] = A [i -2] + 4
else :
A[i] = A[i] - 1

Solution: The purpose of the question is simply to test whether they can read and understand a pseudocode.
Iteration 1: <19, 3, 9, 12, 70, 6>
Iteration 2: <19, 57, 9, 12, 70, 6>
Iteration 3: <19, 57, 23, 12, 70, 6>
Iteration 4: <19, 57, 23, 684, 70, 6>
Iteration 5: <19, 57, 23, 684, 27, 6>
Iteration 6: <19, 57, 23, 684, 27, 138>

15. Consider a city with n East-West Streets (EWS) and n North-South Avenues (NSA). The EWS are the line
segments {y = j | 1 ≤ x ≤ n} for all j ∈ {1, 2, . . . , n} and the NSA are the line segments {x = i | 1 ≤ y ≤ n}
for all i ∈ {1, 2, . . . , n}. A junction is a pair (i, j) where avenue i intersects street j. How many junctions
are there in the city?
For increased safety, the city council decides to place cameras at various junctions in the city. The cameras
being super-powerful, can observe the entire street and avenue corresponding to the junction that they are
placed at. For instance, a camera placed at the junction (i, j) can observe both avenue i and street j. Write
down an expression for the minimum number of cameras needed to observe every street and avenue in the
city.
Justify your answers.
Solution: The number of junctions is n2 since each of the n streets intersect with each of the n avenues at
different points.
At least n cameras are needed. A camera can cover a street and an avenue. If fewer than n cameras are
placed, there is at least one street and at least one avenue that is not covered.

14
16. Find the largest value of xy subject to x2 + y 2 = 2.
√ √
Solution: Let (x, y) = ( 2 cos θ, 2 sin θ). We are asking for the maximum of sin(2θ). It is maximized when
θ is π/4 and the answer is 1. Can be done by inspection too. It is zero on positive x axis and positive y
axis. Since it is nonzero along the arc, a maximum is attained at exactly one position, must be the middle
by symmetry.
17. Each lawyer on a certain remote island is either honest or dishonest (but not both).
• Honest lawyers always speak the truth.
• Dishonest lawyers always lie.
Is it possible for a lawyer on this island to claim that he/ she is dishonest? Explain.
A judge asks lawyer A, “are you honest”? Before A could answer, lawyer B says “A will say yes.” “But
then, he’ll be lying”. Which lawyer is honest and which one is dishonest? Explain.
Solution: It is not possible for a lawyer to claim that they are dishonest. Since, honest lawyers will not lie
and dishonest lawyers will not truthfully admit that they are dishonest.
Suppose A is honest. Then he says “Yes”, which is the truth. This makes B’s first statement True, and B’s
second statement False. So B both lied and spoke the truth, a contradiction.
Now suppose A is dishonest. Then he says “Yes” which is a falsehood. This makes both of B’s statements
True, so there is no contradiction in asserting that B is honest. Thus: A is dishonest, B is honest.
18. A new restaurant chain Burger Paradise has recently opened in Chennai. Burger Paradise offers a variety
of burgers, including vegetarian options, as well as sides and drinks. According to the restaurant’s data,
20% of customers order vegetarian burgers. The restaurant’s data also indicates that customers who order
a burger are twice as likely to order a side of fries than a side of salad.

(a) If the restaurant serves 200 customers daily, what is the expected number of vegetarian burgers they
will sell over a week?
(b) If 30% of the customers order a burger and 60% of those who order a burger order a side of fries, what
is the probability that a customer orders a burger along with a side of fries?

Solution: Part (a):

If 20% of Burger Paradise’s customers order the vegetarian burger, and the restaurant serves 200 customers,
the expected number of vegetarian burgers they will sell is:
Expected number of vegetarian burgers sold = 20% of 200 customers = 0.20 × 200 = 40 vegetarian burgers
Therefore, Burger Paradise can expect to sell 40 vegetarian burgers in a day when they serve 200 customers.
Then over the week, they can expect to sell 40 = 280 vegetarian burgers.
Part (b):

(a) 30% of customers order a burger, i.e. P (Order Burger) = 0.3

(b) If customers who order a burger are twice as likely to order a side of fries than a side salad, i.e.,
P (Order Fries | Order Burger) = 0.6

P = P (Customer who orders a burger, will also order a side of fries)

= P (Order Fries and Order Burger)
= P (Order Fries | Order Burger) × P (Order Burger)
= 0.60 × 0.30
= 0.18

Therefore, the probability that a customer who orders a burger will also order a side of fries is 0.18 or 18%.

15
19. Burger Paradise plans to expand to other cities and is considering opening a new branch in Coimbatore. They
have identified three potential locations, A, B and C, and are evaluating the profitability of each location.
Based on their research, they estimate that the fixed cost for opening a new location will be |50, 00, 000,
|70, 00, 000 and |65, 00, 000 at A, B and C, respectively. They also estimate the variable cost per customer
to be |85 and the average revenue per customer to be |150 at all three locations. They expect to serve
100, 000, 150, 000 and 130, 000 customers in the first year at locations A, B and C, respectively
Which location in Coimbatore is expected to be the most profitable in the first year of operation, and what
is the expected profit at this location?
Solution:
To determine the most profitable location and the expected profit for the first year of operation, we need to
calculate the total revenue, total variable cost, and total contribution margin for each location.
Let’s denote the three potential locations as A, B, and C, with fixed costs of |50,00,000, |70,00,000, and
|65,00,000, respectively. The variable cost per customer served is |85, and the average revenue per customer
is |150. The expected number of customers served in the first year is 100,000 for location A, 150,000 for
location B, and 130,000 for location C.
The total revenue for each location is:
Location A: 100, 000 × |150 = |1, 50, 00, 000
Location B: 150, 000 × |150 = |2, 25, 00, 000
Location C: 130, 000 × |150 = |1, 95, 00, 000
The total variable cost for each location is:
Location A: 100, 000 × |85 = |85, 00, 000
Location B: 150, 000 × |85 = |1, 27, 50, 000
Location C: 130, 000 × |85 = |1, 10, 50, 000
The contribution margin for each location is:
Location A: |1, 50, 00, 000 − |85, 00, 000 = |65, 00, 000
Location B: |2, 25, 00, 000 − |1, 27, 50, 000 = |97, 50, 00
Location C: |1, 95, 00, 000 − |1, 10, 50, 000 = |84, 50, 000
The expected profit for each location is:
Location A: |65, 00, 000 − |50, 00, 000 = |15, 00, 000
Location B: |97, 50, 000 − |70, 00, 000 = |27, 50, 000
Location C: |84, 50, 000 − |65, 00, 000 = |19, 50, 000
Therefore, location B is expected to be the most profitable with an expected profit of |27,50,000 in the first
year of operation.

20. Towns A, B and C are connected to each other by several roads, with at least one road connecting each pair.
In going from one town to another, one can take the road that connects them directly or could travel via
the third town. It is given that, in total, there are 33 roads from A to B, including those via C. Similarly,
there are 23 roads from B to C, including those via A. How many routes are there from A to C, including
those via B?
Solution: Let x be the number of direct roads from A to B (not passing through C). Let y be the number
of direct roads from B to C. Let z be the number of direct roads from A to C. The given information is:

x + yz = 33
y + xz = 23

16
Adding and subtracting gives us

(y − x)(z − 1) = 10
(y + x)(z + 1) = 56

Since (z − 1)|10 and (z + 1)|56 we have z = 3 or 6. Substituting the values in the first set of equations rules
out z = 3. So z = 6 implies x = 3 and y = 5. The final answer is z + xy = 21.

17