CMI Entrance Exam 2025 Question Paper Solution B.Sc

Draft solutions for CMI BSc entrance exam on May 24, 2025

Send any comments to [email protected] by June 8, 2025

Part A draft solutions (answer key after the solutions)

Information for questions (2) to (5) (Question numbering deliberately starts at 2.)

Let S = {1, 2, . . . , 100}. Randomly pick an element x from S, every element being equally
probable. Let S1 be the set of all elements in S less than or equal to x and let S2 be the set
of all remaining elements of S, i.e., elements strictly bigger than x. Answer questions (2) to
(5) as per the given instruction.

Instruction for (2) to (5)

If the probability is p%, then your answer should be the integer closest to p. E.g., for
probability 13 = 33.33 . . . %, you should type 33 as your answer. For probability 32 you should
type 67 as your answer.

Questions

(2) What is the probability that 50 belongs to a set of size exactly 60? [1 point]

(3) What is the probability that 20 belongs to S1 and 60 belongs to S2 ? [1 point]

(4) What is the probability that 20 and 60 are both in S1 or they are both in S2 ? [1 point]

(5) What is the probability that the product of sizes |S1 ||S2 | > 900? [2 points]

Answers

(2) 2% because x must be 60 or 41.
(3) 40% because the condition is equivalent to 20 ≤ x ≤ 59.
(4) 60% because this is complementary to (2).
(5) 79% because x ≤ 10 and x ≥ 90 are the undesired cases. E.g., see the graph of x(100−x).

(6) Let P = (a, b, c) be the point on the plane 3x + 5y − 7z = 9 that is closest to the point
(8, 12, −13). Write the integer that is closest to a2 + b2 + c2 . [3 points]

Answer: (2,2,1) is the closest point so the answer is 9. To get the answer one solves for
(a, b, c) and a scalar λ using two equations: (i) 3a + 5b − 7c = 0 because P is on the plane,
and (ii) (a−8, b−12, c+13) = λ(3, 5, −7) because the plane by its definition is perpendicular
to (3, 5, −7) (to 3î + 5ĵ − 7k̂ if you wish) and also perpendicular to (a − 8, b − 12, c + 13) by
virtue of P being closest to (8, 12, −13), thus forcing the proportionalilty.

(7) Write the value of the following number correct to two decimal places. E.g., for e type
2.72 and for 3 type 3.00. If the limit does not exist, type DNE as your answer. [4 points]
!
ln(1 + tx)
lim lim R x p
t→0+ x→0+
0
ex − cos(t) cos(x) dx
√
Answer: 2. The outer limit is as t → 0+ , so fix a positive value for t in order to first study
the inner limit. By substituting x = 0, the inner limit is “of type 0/0”, so to calculate it we
may try to use L’Hôpital’s rule*. Rushing headlong into it, the derivative (with respect to x)
′
of the numerator is (ln(1+tx))
p = t/(1+tx) and that of the denominator, by the fundamental
theorem of calculus,pis e − cos(t) cos(x). As x → 0+ , the limits of these
x
p derivatives are,
respectively, t and 1p− cos(t). Sop √ L = limt→0 (t/ 1 − cos(t)).
we need to examine + By
2 2
algebra L = limt→0+ (t 1 + cos(t))/
2
√ 1 − cos (t)) = 2. Or use 1 − cos(t) = 2 sin (t/2). Or
limt→0 (t /(1 − cos(t)) = 2, so L = 2. R(Why is “taking the square root” valid?) To test the
xp x
answer numerically, plot (ln(1 + tx))/( 0 e − cos(t) cos(x) dx) for t = 0.01, 0.001, 0.0001
in a suitable window, e.g. on desmos. Is the L’Hôpital recipe logically valid here? Read on.

*Note: The useful L’Hôpital’s rule, popular in high school calculus, deserves more care in its
application than is often accorded to it. For example, consider limx→0 ((x2 sin(x−1 ))/ sin x).
First see that this limit is 0. (How?) Next, as x → 0, we have sin x → 0 and x2 sin(x−1 ) → 0
because sin(x−1 ) is bounded. Here is what happens if you “apply” L’Hôpital’s rule:
!
2 −1 −1 −1
x sin(x ) ? 2x sin(x ) cos(x )
lim = lim − .
x→0 sin x x→0 cos x cos x
The RHS is not defined: as x → 0, both sin(x−1 ) and cos(x−1 ) oscillate in [−1, 1]. The first
term has limit 0 due to the factor 2x but the second has no limit. What went wrong? Nothing.
There are other conditions to check before applying the rule. See, e.g., the wikipedia entry
for details and more counterexamples. A particular case suffices for question (7): Suppose
(i)-(iii) hold: (i) limx→a N (x) = 0 = limx→a D(x). (ii) For some open interval I containing a
and for all x ∈ I except possibly x = a, N (x) and D(x) are differentiable with D′ (x) nonzero.
(iii) limx→a (N ′ (x)/D′ (x)) exists. Call it L. Then the rule assures limx→a (N (x)/D(x)) = L.

Here is a more careful treatment of question (7), showing additionally that the inner limit
may be taken to be two sided. Fix t ∈ (0, 2π). First, (1 + tx) is positive for all x > (−1/t),
so the numerator N (x) = ln(1 + tx) is defined for x ∈ (−1/t, ∞). Next, ex − cos(t) cos(x) is
p of x and (because 0 < t < 2π), at x = 0, its value 1 − cos(t) is positive.
a continuous function
So the integrand ex − cos(t) cos(x) is defined and > 0 for all x in some open interval
IR =p(−ϵ, ϵ) containing 0. (Technically, a variable other than x should have been used, e.g.,
x
0
eu − cos(t) cos(u) du, but u is dummy anyway.)
Rx The integrand is a continuous function
of x (or u) on I, so its Riemann integral 0 exists. Thus the numerator N (x) and the
denominator D(x) are both defined on I, so it is valid to consider the inner limit as x → 0.

Next, N (x) and D(x) are continuous (in fact differentiable) on I, so their limits as x → 0
can be obtained by evaluation at x = 0. Both limits are 0, so condition
p (i) for L’Hôpital’s
′ ′ x
rule holds. For x ∈ I, we have N (x) = t/(1 + tx) and D (x) = e − cos(t) cos(x) > 0,
so
p condition (ii) holds. Condition (iii) holds pbecause, as x → 0, N ′ (x) → t and D′ (x) →
1 − cos(t) > 0. So limx→0 (N (x)/D(x)) = t/ 1 − cos(t) by L’Hôpital’s rule. Now one can
continue as in the answer. (Can the outer limit be taken to be
√ two sided? Extend the entire
analysis to t < 0 to show limt→0− (limx→0 (N (x)/D(x))) = − 2. So the answer is No.)

Information for questions (8) and (9)

A and B are points on a paper with AB = 10. A fly walks on the paper from A to B in such
a way that for any third point P on the path, ∠AP B = α, where α = the angle opposite to
side 4 in a triangle with sides 3, 4, 5.

Questions

(8) The path traced out by the fly is part of . Fill in the blank with the number of
one of the following options. [1 point]

1. a straight line

2. a circle

3. an ellipse

4. a parabola

5. a hyperbola

6. none of the options numbered 1 to 5

(9) For each point P along the path, consider △AP B. Write the maximum possible area of
such a triangle. [3 points]

Answers

(8) Circle by high school geometry.

(9) 50. Every such triangle has base 10. Area is maximized when the height h is maximum.
This happens when the triangle is isosceles. Then tan(α/2) = 5/h. So area = 25/ tan(α/2).
From the 3-4-5 right triangle, we have sin(α) = 4/5 and cos(α) = 3/5. The half angle
formula gives tan(α/2) = (4/5)/(1 + (3/5)) = 1/2.

Information for questions (10) and (11)

Let C be the curve defined by y = x2 where 0 ≤ x ≤ 2. Let P = (9, −3).

Questions

(10) The x-coordinate of a point on C closest to P satisfies ax3 + bx = c where a, b, c are
integers with gcd(a, b, c) = 1. Write the values of a, b, c separated by commas with no gaps.
E.g., for x3 + 2x = 3, the answer would be 1,2,3. [2 points]

(11) Let d = the minimum distance of P from a point on C. Let D = the maximum distance
of P from a point on C. Write two integers separated by only a comma: the integer closest
to d2 , the integer closest to D2 . E.g., 20,25 is an answer in the correct format. [3 points]

Answers

(10) 2x3 + 7x = 9. For distance to be minimum, the line joining (9, −3) with point (x, x2 )
must be normal to C, sopmust have slope (x2 + 3)/(x − 9) = −1/2x. We get 2x3 + 7x = 9.
Alternatively, minimize (x − 9)2 + (x2 + 3)2 over [0, 2], which is easier done by throwing
away the square root. One gets the same equation for a critical point, but then more is
needed to argue that the minimum satisfies this equation. See below.

(11) d2 = 80, D2 = 98. Squared distance of a point (x, x2 ) on C from P is (x − 9)2 + (x2 + 3)2 .
An extremum of a differentiable function of x over a closed interval occurs at either a critical
point or at an endpoint. Critical points are solutions of 2x3 + 7x = 9. Clearly x = 1 is a
solution and one can visually deduce (how?) that this is the only solution and that it gives
the minimum∗ (so for the maximum we just need to check the values at the two endpoints).
Or algebraically, 2x3 + 7x − 9 = (x − 1)(2x2 + 2x + 9) and 2x2 + 2x + 9 has no real root. At
x = 0, 1, 2 the values of the objective function are, respectively, 90, 80, 98.
∗
Note: As x = 1 gives the minimum, anything of the form ax3 + bx = c with a + b = c and
gcd(a, b, c) = 1 is a valid (if cheeky) answer to (10). If you did this consciously, write to us.

(12) Count the number of ordered tuples of integers (a, n1 , n2 , n3 , n4 ) such that all three
conditions below are satisfied. [4 points]
• a > 0.
• ni ≥ −1 for each i.
• a2 + n1 + n2 + n3 + n4 = 5.

Answer: 222 = 165 + 56 + 1
There are three cases: a = 1, 2, 3. They yield, respectively, 165, 56 and 1 possibilities. In
each case add 1 to each ni and use the “stars and bars” method. For a = 1 we have
n1 + n2 + n3 + n
4 = 4, so the sum of the four non-negative integers ni + 1 is 8, which can be
achieved in 8+3
3
= 165 ways. For a = 2 we have n1 + n2 + n3 + n
4 = 1, so the sum of the
four non-negative integers ni + 1 is 5, which can be achieved in 5+3
3
= 56 ways. Finally, for
a = 3, we have n1 + n2 + n3 + n4 = −4, forcing each ni = −1.

Information for question (13)

Claim: Suppose a, b are distinct roots of a polynomial p(x). Then p(x) is a multiple of
(x − a)(x − b).

Proof from first principles: Use long division to get p(x) = (x − a)q(x) + r where 1
is some constant. Substituting x = 2 , we get r = 3 , so 4 is a multiple of
(x − a). Now substituting x = 5 we get that 6 is a root of 7 . Finally, again
apply the logic in the first two sentences, now to q(x). This shows that 8 is a multiple
of 9 , completing the proof.

Options for the blanks

A. a B. b C. r

D. 0 E. q(a) F. q(b)

G. q(r) H. p(x) I. q(x)

J. (x − a) K. (x − b) L. (x − r)

(13) Complete the given proof by writing a sequence of nine letters indicating the correct
options to fill in the numbered blanks 1 to 9. Do not use any spaces, full stop or any other
punctuation. E.g., ABACDIJKB is in the correct format. [3 points]

Answer

Proof from first principles: By using long division, p(x) = (x − a)q(x) + r for some
constant r. Substituting x = a, we get r = 0, so p(x) is a multiple of (x − a). Now
substituting x = b we get that b is a root of q(x). Finally, again apply the logic in the first
two sentences, now to q(x). This shows that q(x) is a multiple of x − b, completing the proof.

Information for question (14)

Logic similar to Question (13) works for a polynomial P (x, y) in two variables: if after
substituting x = f (y) one gets P (f (y), y) = 0, then P (x, y) = (x − f (y))Q(x, y). Similarly
if P (g(y), y) = 0 as well, then an analogous conclusion holds. Assume this.

Now let A(x, y) be a symmetric polynomial, meaning A(x, y) = A(y, x). Let ω = e2πi/3 .
Suppose that substituting x = ωy gives A(ωy, y) = 0. Then A(x, y) is a multiple of 1 .
Therefore it is a multiple of 2 too. Therefore A(x, y) must be a multiple of the following
polynomial with integer coefficients: 3 .

Options for the blanks

A. (x − ωy) B. (y − ωx)

C. (x + ωy) D. (y + ωx)

E. (x + y) F. x2 − 2xy + y 2

G. x2 − xy + y 2 H. x2 + y 2

I. x2 + xy + y 2 J. x2 + 2xy + y 2

(14) Complete the reasoning about A(x, y) by writing a sequence of three letters indicating
the correct options to fill in the numbered blanks 1 to 3. E.g., ABC is in the correct format.
[2 points]

Answer

Let A(x, y) be a symmetric polynomial, meaning A(x, y) = A(y, x). Let ω = e2πi/3 . Suppose
that substituting x = ωy gives A(ωy, y) = 0. Then A(x, y) is a multiple of (x−ωy). Therefore
(by symmetry) it is a multiple of (y − ωx) too. Therefore A(x, y) must be a multiple of the
following polynomial with integer coefficients: x2 + xy + y 2 = (x − ωy)(y − ωx)/(−ω).

Information for question (15)

Claim: x = y = z = 0 is the only integer solution to x2 + y 2 = 105z 2 .

Proof: Consider an integer solution (x, y, z) with the 1 possible value of |x| + |y| + |z|.
When any perfect square is divided by 3 the possible remainders are 0 and 1. Therefore,
when each term on the left hand side x2 + y 2 is divided by 3, the possible combinations of
remainders are 0 + 0, 0 + 1, 1 + 0, and 1 + 1.
It follows that 2 must be divisible by 3 . Therefore x2 + y 2 is divisible by 4 .
Therefore 5 is divisible by 6 because 105 is divisible by 7 but not by 8 .
Now observe that 9 x, y and z by 10 still gives a solution of the given equation.
Unless x = y = z = 0, this contradicts the first sentence of the proof.

Options for the blanks

A. largest B. smallest

C. x D. y

E. z F. x or y

G. both x and y H. x or y or z

I. all of x, y, z J. dividing

K. multiplying An integer from 0 to 9

(15) Fill each blank with the letter of an option OR an integer between 0 to 9. For example
K9AC6JK1BB is an answer in the correct format. [4 points]

Answer

Consider an integer solution (x, y, z) with the smallest possible value of |x| + |y| + |z|. When
any perfect square is divided by 3 the possible remainders are 0 and 1. Therefore, when each
term on the left hand side is divided by 3, the possible combinations of remainders are 0 +
0, 0 + 1, 1 + 0, and 1 + 1.
It follows that both x and y must be divisible by 3. Therefore the left hand side is divisible by
9. Therefore z is divisible by 3 because 105 is divisible by 3 but not by 9. Now observe that
dividing x, y and z by 3 still gives a solution of the given equation. Unless x = y = z = 0,
this contradicts the first sentence of the proof.

Information for question (16)

Can the argument in Question (15) work with the exact same logic to prove the same claim
for the same integer equation x2 + y 2 = 105z 2 , if we divide by a number other than 3? You
are asked to test this for 5 and 7 and answer as explained in the question.

(16) Write your answer as a single letter from options A,B,C,D followed by listing in increas-
ing order the letter of every equality that is NOT encountered while deciding the correct
option from A to D. For example, AGI is an answer in the correct format. [2 points]

Options for (16)

A. Same argument works for 5 as well as 7
B. Same argument works for 5 but not 7
C. Same argument works for 7 but not 5
D. Same argument works for neither 5 nor 7
E. 0 + 1 = 1 F. 1 + 1 = 2
G. 1 + 2 = 3 H. 1 + 4 = 5
I. 2 + 2 = 4 J. 3 + 3 = 6
K. 4 + 4 = 8

Answer

CJ. It works for 7 but not 5. Only 3 + 3 = 6 is not enountered as no square leaves remainder
3 when divided by 5 or by 7. All others equalities are encountered as 0, 1, 4, 2 are remainders
of squares modulo 7. Note that 1 + 4 = 5 causes the method to fail for 5. (Reason: because
then LHS is divisible by 5 without x and y being divisible by 5, so the proof cannot proceed.
The proof works when dividing by 7 because the only way to get a multiple of 7 by adding
two numbers from the list 0, 1, 4, 9 = 2 mod 7 is 0 + 0, allowing us to proceed exactly as was
done using division by 3 in the previous question.)

Information for questions (17) and (18)

Suppose a function f (x) has domain R and satisfies the following three conditions.
(A) f is differentiable. (B) f is increasing. (C) 0 < f (x) ≤ 1 for each x.
Suppose limx→∞ f ′ (x) = a real number L. Complete the following proof showing L = 0.
Proof: By the given condition 1 , the value of L must be 2 3 . If L is nonzero,
we can choose a large enough N such that for x 4 N , the value of f ′ (x) is ≥ 5 .
Therefore by the following theorem 6 , for any x ≥ 7 , given condition 8 will
be violated, giving a contradiction.

Options for the blanks

A. (A) B. (B) C. (C)

D. = E. ≥ F. ≤

G. 0 H. 1/2 I. 1

J. L/2 K. 2L L. L

M. N + L2 N. N + L O. N + 2L

P. N + L2 Q. N + L1 1
R. N + 2L

S. Mean value theorem

T. Extreme value theorem

U. Intermediate value theorem

V. Fundamental theorem of calculus

Questions

(17) Write a sequence of 5 letters indicating the correct options to fill in the numbered blanks
1 to 5. For example, BACDE is in the correct format. [2 points]

(18) Write a sequence of 3 letters indicating the correct options to fill in the numbered blanks
6 to 8. E.g., WJE is in the correct format. [2 points]

Answers

By the given condition (B), the value of L must be ≥ 0. If L is nonzero, we can choose a large
enough N such that for each x ≥ N , the value of f ′ (x) is ≥ L/2. Therefore by the mean value
theorem, for x ≥ N + 2/L, condition (C) will be violated, giving a contradiction. Reasoning:
(1) For x ≥ (N +2/L), by MVT, f (x)−f (N ) = f ′ (a number > N )(x−N ) ≥ (L/2)(2/L) = 1,
forcing f (x) > 1 as f (N ) > 0. OR (2) If f ′ (x) is known to be Riemann integrable (which is
true, e.g., if f ′ is known to be continuous), then instead of MVTR one can also argue using
x
the fundamental theorem of calculus as follows. f (x) − f (N ) = N f ′ (x) dx ≥ (L/2)(2/L),
since the integrand is at least L/2 over an interval of length at least 2/L.
Note: this question is a small prelude to problem B5. See the answer to B5 for more.

Draft answer key to part A

(2) 2

(3) 40

(4) 60

(5) 79

(6) 9

(7) 1.41

(8) 2

(9) 50

(10) 2,7,9

(11) 80,98

(12) 222

(13) CADHBBIIK

(14) ABI

(15) BG39E339J3

(16) CJ

(17) BEGEJ

(18) SPC (VPC also accepted)

Part B draft solutions

B1. [12 points] Suppose five complex numbers z1 , z2 , z3 , z4 , z5 form the vertices of a regular
pentagon that is inscribed in a circle of radius 2 with center at c = 6 + 8i.
(a) Find all possible values of S = z12 + z22 + z32 + z42 + z52 . State a value of z1 maximizing |S|.
(b) Find all possible values of P = z1 z2 z3 z4 z5 . State a value of z1 minimizing |P |.

Solution

All five zj − c are on the circle with radius 2 and center at the origin. Let z1 − c = 2eiθ . So
we have {zj − c | j = 1, 2, 3, 4, 5} = {2ei(θ+(2πj/5)) | j = 1, 2, 3, 4, 5}. Thus the five zj are the
five complex roots of the degree 5 polynomial (z − c)5 − 32e5iθ . So

(z − c)5 − 32e5iθ = (z − z1 )(z − z2 )(z − z3 )(z − z4 )(z − z5 ).

Use Vieta’s formulas (i.e., expand both sides and compare coefficients of powers of z) to get
X
z1 + z2 + z3 + z4 + z5 = 5c zj zk = 10c2 and z1 z2 z3 z4 z5 = c5 + 32e5iθ .
1≤j<k≤5

(a) S = z12 + z22 + z32 + z42 + z52 = ( 1≤j≤5 zj )2 − 2 1≤j<k≤5 zj zk = 25c2 − 20c2 = 5c2 is
P P
independent of θ, i.e., constant regardless of the placement of the inscribed pentagon. So
any z1 on the given circle will work, e.g., z1 = 8 + 8i or 6 + 10i, etc. |S| = 5|c|2 = 500.

(b) We have P = c5 +32e5iθ . As θ varies, the resulting set of points forms a circle of radius 32
with center at c5 = (6+8i)5 . The minimum value of |P | is achieved when P is the intersection
point of this circle with the segment joining the origin with c5 , giving |P | = |c5 |−32 = 99968.

To describe a value for z1 (i.e., a value for θ) minimizing |P |, let c = 10eiα , so c5 = 105 e5iα .
Then maximum/minimum value of |P | is attained precisely when c5 and 32e5iθ are, respec-
tively, along the same/opposite rays from the origin. This in turn is equivalent to 5(α − θ)
being an even/odd multiple of π. For example, taking θ = α + (π/5), i.e., z1 = c + 2ei(α+(π/5))
will give |P | = 99968.

This can also be seen algebraically. We have |a| − |b| ≤ |a + b| ≤ |a| + |b| by the triangle
inequality for complex numbers a, b. Let b ̸= 0. The upper/lower bound for |a+b| is achieved
when a/b is a real number. So we have |c5 | − |32e5iθ | ≤ |c5 + 32e5iθ | ≤ |c5 | + |32e5iθ |, giving
99968 ≤ |P | ≤ 100032. The upper/lower bound is achieved when c5 /(32e5iθ ) = 55 e5i(α−θ) is
real, which happens precisely when 5(α − θ) is a multiple of π.

B2. [12 points] Consider the following functions from R2 = {(a, b) | a, b ∈ R} to itself. Let
Rα be counterclockwise rotation by angle α and let Fα = reflection in the line that makes
counterclockwise angle α with the X-axis. E.g., R90◦ (1, 0) = (0, 1) and F90◦ (1, 0) = (−1, 0).
(a) Evaluate Rα (r cos θ, r sin θ) and Fα (r cos θ, r sin θ), where r ≥ 0 and θ is any angle.
(b) Geometrically describe the composition of functions Fα ◦ F0 . (Note that F0 = reflection
in the X-axis.) You may use any valid method as long as you explain clearly.
(c) For any angles α and β, geometrically describe Fα ◦ Fβ in one crisp sentence. You may
appeal to (b) if you justify why and how your work in (b) can be used here. Find G(P ) for
G = (F20◦ ◦ F25◦ )9 = (F20◦ ◦ F25◦ ) composed with itself 9 times and P = the point (20, 25).

Solution

Let the origin be O and the point Q = (r cos θ, r sin θ). Both Rα and Fα preserve the distance
r from the origin, so one just has to find out the angle from the positive X-axis of the new
ray after rotating/reflecting the ray OQ.
(a) The ray OQ is obtained by rotating the positive X-axis counterclockwise by angle θ. The
rotation Rα rotates ray OQ further by angle α, taking it to the ray making counterclockwise
angle α + θ from the positive X-axis. So Rα (r cos θ, r sin θ) = (r cos(α + θ), r sin(α + θ)).
For the reflection Fα , draw a picture to see the following. Reflection of Q = (r cos θ, r sin θ)
in the described line sends ray OQ to a ray OQ′ that makes counterclockwise angle 2α − θ
from the positive X-axis. Reason: Ray OQ makes counterclockwise angle θ − α from (one
half of) the reflecting line. So after reflection, the clockwise angle from the (same half of the)
reflecting line to OQ′ must also be θ − α. Altogether the counterclockwise angle of ray OQ′
from the positive X-axis is α − (θ − α) = 2α − θ. (Convince yourself that the reasoning is
valid for all angles α, θ regardless of their signs and magnitudes.) Therefore
Fα (r cos θ, r sin θ) = (r cos(2α − θ), r sin(2α − θ)).
(b) By (a), Fα ◦ F0 (r cos θ, r sin θ) = (r cos(2α + θ), r sin(2α + θ)) = R2α (r cos θ, r sin θ), so
Fα ◦F0 = R2α . It is fun and worthwhile to do this by pure geometry without using coordinates.

(c) Fα ◦Fβ = R2(α−β) again by (a) or by the exact same geometric argument you were exhorted
to do in (b): the composition of two reflections is a rotation by an angle determined solely by
the angle between the two lines of reflection. Therefore (F20◦ ◦ F25◦ ) = R−10◦ , so G = R−90◦
and G(20, 25) = (25, −20).

Remarks: The calculations in this problem are fundamental. Such considerations underlie
mathematical study of symmetry. Here are some further easy questions in a similar vein.
(d) How do Fα ◦ Fβ and Fβ ◦ Fα compare? Observe that they are inverse functions of each
other. Does Fα have an inverse? If so, what is it? With this information, again relate Fα ◦Fβ
and Fβ ◦ Fα . Can you quickly calculate the composition Fα ◦ Rγ where α, γ are arbitrary
angles? Try to do something to the equation from (c): Fα ◦ Fβ = Rγ where γ = 2(α − β).
(e) Start with {F0 , F60◦ }. Compose functions from this set with each other. Add the resulting
functions to the set. Keep repeating. Show that this process stops with a finite set S after
which you get no new functions. What is |S|? Write down an |S| × |S| “composition table”.
Now replace F60◦ by some Fα and play the same game. Do you always end with a finite set?
This is a beginning towards group theory. See Hermann Weyl’s book Symmetry for more.

B3. [12 points] A particle starts at (0,0) and travels in the first quadrant along a straight
line. It maintains the slope AND stays in the square bounded by the lines x = 0, x = 1, y = 0
and y = 1 as follows. Whenever it reaches the boundary of this square it magically jumps
1 unit to the left or down or both as applicable. In other words, for a < 1, it jumps to
(a, 0) upon reaching (a, 1), it jumps to (0, a) upon reaching (1, a), and it jumps to (0,0) if it
reaches (1,1). If the particle ever reaches a previously visited point, it stops.
jump jump
For example, (0, 0) → (1/2, 1) −−−→ (1/2, 0) → (1, 1) −−−→ (0, 0) is a trajectory of length
√
5. (Jumps don’t count for length.) Another way to visualize this trajectory is to let the
particle continue across the boundary y = 1 and interpret what happens.
(a) What are all the possible stopping points for finite trajectories?
(b) If the particle starts at the angle 30◦ with respect to the X-axis, show that it never stops.
(c) Find the two smallest possible integer lengths among all finite trajectories.

Solution

(a) Only the starting point (i.e., the origin) can be the stopping point. Because the slope
stays constant, once the slope is known, any point in a trajectory has a uniquely determined
past (determined solely by its position). So if any position other than the starting point
were to repeat, there would be previous points that also repeated. (This is true not just for
interior points, but those on the boundary too, because the magic jump rule allows one to
trace back.) But then we have a contradiction to the stopping rule.
√
(b) After starting,
√ the trajectory first meets the boundary at (1, 1/ 3) and then the particle
jumps to (0, 1/ 3). Any time the trajectory meets the boundary, the coordinate other than
1 or 0 of the meeting point will be always be irrational because the slope is irrational. So
the particle can never return to the origin.

(c) Use the other suggested way to visualize a trajectory: let the particle continue in the
starting straight line without being confined to the square. The prescribed path is easily
deduced from the resulting magicless ray in the plane, say L. Crucial observation: the particle
repeats a position if and only if L meets an integer point, which it will do precisely when the
slope is rational, and in that case the first nonzero integer point (a, b) the particle reaches
must satisfy gcd(a, b) = 1. The answer is 5 and 13 because these are the smallest hypotenuse
lengths of integer right triangles with coprime sides, namely triangles with sides 3-4-5 and
5-12-13. (Note: 1 is not an answer because under the rule as worded, the particle cannot
travel along either axis. It cannot step off the origin in those directions.)

Remarks: Suppose an ant starts walking in some direction at a point on the surface of a
donut and continues in the same direction. Will it return to a previously visited point? The
exam problem formulates and analyzes this question in terms of plane geometry. There are
two steps. (1) The surface of a donut can be thought of as obtained by taking a (stretchable)
square sheet of paper, first rolling it to make a cylinder by gluing two parallel edges, and
then gluing together the two end circles of this cylinder to make “hollow donut”. This is
what the “magic jumps” in the problem are doing. Note that at the end, the four corners of
the square are glued together, every other point of the border is glued to exactly one other
point on the parallel edge, and no point in the interior is glued to any other point. (2) Now
go a step further by starting with the entire XY plane with a grid of lines dividing the plane
into squares. Define a function from the plane onto the donut so that each point on the

donut is represented by infinitely many points in the plane. All points on the grid lines are
appropriately mapped to the edges of the single square in the first step, which are themselves
glued with the opposite edges as explained in the first step. In particular all integer points
are mapped to the origin. This second step is very useful to visualize the ant’s path on the
torus by means of an ordinary straight line in the plane. Having multiple points in the plane
represent the same point on the donut helped in translating a problem about the donut to
a more tractable one about the plane.

The strategy of allowing the same object to be represented by different representatives is
very useful and employed frequently in mathematics. You have already encountered this
in arithmetic, e.g., when we say that the pairs (1,2) and (5,10) represent the same rational
number and in modular arithmetic when we say that 7 and 37 are the same modulo 10. This
problem is just one example of how the idea can be useful in geometry as well.

B4. [12 points] The domain of f is the set of positive integers and f (xy) = f (x) + f (y) for
all x, y. Answer the independent questions below. (Data from (a) are not valid for the rest.)
(a) Suppose f (2025) = 0, f (20) = 10 and f (25) = 20. What is the smallest n for which f (n)
is not uniquely determined? Write values of f (x) for each positive integer x < n.
(b) Is there such a function f for which f (x) = 0 for all positive integers x < 20252025 but f
is not identically 0? Show how to define such f or show that it is not possible.
(c) The domain of a function g is the set of positive rational numbers, codomain the set
of integers and g(xy) = g(x) + g(y) for all positive rational x, y. Suppose g(a) = 24,
g(b) = 2025, g(c) = 102025 for some rational numbers a, b, c. Show that there are infinitely
many rational numbers r such that g(r) = 1. (Note: “codomain the set of integers” was
missing in the exam, so part (c) will be graded by taking this into account. Details below.)

Solution

Such f is uniquely defined Q
by assigning
Pfor each prime p an arbitrary value in the codomain,
kp
say λp , to f (p). Then f ( p p ) = p kp λp and unique factorization of positive integers
shows that the function is well defined. The required property is easily checked for all
positive integers x, y.

(a) f (1) = f (1) + f (1) so f (1) = 0. Now f (25) = 2f (5) = 20 gives f (5) = 10. Then
f (20) = f (22 × 5) = 10 forces f (2) = 0 = f (4) and f (2025) = f (34 × 25) = 0 forces
f (3) = −5. Then f (6) = f (3) + f (2) = −5 as well. The first undetermined value is f (7),
which can be arbitrary by the previous paragraph.

(b) Yes. Define f (p) = 0 for all primes p < 20252025 and f (p) ̸= 0 for at least one prime
p > 20252025 , which is possible to do because there are infinitely many primes.

(c) g(ax by cz ) = 24x + 2025y + 102025 z for any integers x, y, z (including negative ones). This
is easy to see using g(1/a) + g(a) = g((1/a)a) = g(1) = 0. Now gcd(24, 2025, 102025 ) = 1
by looking at prime factorizations 24 = 23 × 3, 2025 = 34 × 52 and 102025 = 22025 × 52025 .
So by the Bézout descripton of gcd as a linear combination, there is an integer combination
24x + 2025y + 102025 z = 1. For such integers x, y, z, take r = ax by cz to get g(r) = 1.

The following portion of (c) about showing infinitely many r is taken off the exam. Only
existence of one r shown in the previous paragraph is enough for full credit. To find infinitely
many r with g(r) = 1 is equivalent to finding a positive rational s ̸= 1 such that g(s) = 0.
Reason: g(s) = 0 gives g(rsk ) = 1 and rsk are all distinct as k ranges over Z. Conversely
g(r1 ) = g(r2 ) gives g(r1 /r2 ) = 0. How to get such s? If g(p) = 0 for some prime p, take
s = p. Otherwise take primes p ̸= q. Then s = pg(q) /q g(p) works. This s is rational because
g(p) and g(q) are integers and it is not 1 unless g(p), g(q) are both 0.

Remark: In fact without some restriction on the codomain, s ̸= 1 with g(s) = 0 need
not exist, so the “infinitely many” part of the question is erroneous without additional
hypothesis. Here is a counterexample by taking the codomain to be R (consistent with
the overall convention in the exam). We want a function g suchQthat g(s) = 0 only for
s = 1 while satisfying other given conditions in (c). For s = p pkp with kp integers,
g(s) = g( p pkp ) = p kp λp . The first paragraph of the solution stays valid for g because
Q P
unique factorization is valid for positive rational numbers too (by allowing negative P powers
of primes). So we need to find a family of numbers λp in the codomain such that p kp λp = 0
only when all integers kp are 0. This amounts to saying that all λp are linearly independent
when R is regarded as a vector space over Q. By linear algebra, R has a Q-basis, which
must be uncountable. (Reason: The Q-span of a finite/countable set of real numbers is
countable, while R is not.) So the numbers λp can be taken to be part of any such basis. As
2025
a concrete example let λ2 = 1 (with a = 224 , b = 22025 , c = 210 so as to satisfy the part (c)
√
hypothesis), and let λp = p for odd primes p. It needs proof that this works but it does.

B5. [16 points] Solve the following. Part (b) can be done independently and may be easier.

(a) Construct a function f with domain R such that f is differentiable, weakly increasing,
bounded, and limx→∞ f ′ (x) does not exist. (Weakly increasing means f (a) ≤ f (b) for a < b.
Bounded means there are constants m, M such that for every real x, we have m < f (x) < M .)
Possible hints: What kind of function should f ′ (x) be to satisfy the requirements? Thinking
in terms of pictures may help. Is there a way to construct a function whose derivative is a
desired function? If needed, you may take the domain of f to be [0, ∞) instead.
(b) Construct a function g with domain R such that g is differentiable, strictly increasing,
bounded, limx→ −∞ g(x) = 0 , limx→∞ g ′ (x) does not exist, and limx→ −∞ g ′ (x) does not exist.
(Strictly increasing means g(a) < g(b) for a < b.)
Possible hint: You may use your answer to part (a) and adjust as necessary. Even if you did
not do part (a), you may take as given a function f with domain [0, ∞) and the required
properties in (a). Then show with clear explanation how to build g in terms of f .

Solution

(a) To meet all requirements it is enough to arrange all of the following.

1. f ′ (x) is always ≥ 0. This ensures that f (x) is weakly increasing everywhere.

2. f ′ (x) is continuous, Rso the fundamental theorem of calculus applies and for any x we
x
have f (x) = f (0) + 0 f ′ (t) dt.

R∞
3. −∞ R
f ′ (t) dt = A is finite. This ensures that f is bounded. Proof: A = B + C, where
0 R∞
B = −∞ f ′ (t) dt and C = 0 f ′ (t) dt. Because the integrand f ′ (x) ≥ 0 everywhere, we
Rr
have the following bounds. For r > 0, f (r) = f (0) + 0 f ′ (t) dt ≤ f (0) + C. For s < 0,
R0 ′
s
f (t) dt = f (0) − f (s) ≤ B, giving f (0) − B ≤ f (s). Combining with f (s) ≤ f (r)
(because f is increasing) we deduce that the range of f is contained in the window
[f (0) − B, f (0) + C] of width A. (We’re just using 0 as a helper point.)

4. f ′ (x) does not have a limit at ∞. One way to arrange this is to pick two distinct
nonnegative numbers, say 0 and 1, and ensure that for any N , f ′ (x) attains each of
the two values for some x > N .

Here is an example putting all of this together. (Other schemes are possible.) Define a
continuous nonnegative function h as follows. For each nonzero integer n, on the segment
[n − 1/2|n| , n + 1/2|n| ] on the X-axis, define h(x) so that its graph is two sides of the triangle
with vertices at the points (n ± (1/2|n| ), 0) and (n, 1). Note that the area of this triangle is
1/2|n| . For
R x all (x, 0) not on the base of any of these triangles, define h(x) = 0. Then define
f (x) = 0 h(t) dt. See that f ′ (x) = h(x) meets conditions 1 to 4. Here B = C = 1 = total
area of triangles on either side of the Y -axis. (Note that limx→−∞ h(x) also fails to exist.
This was done anticipating the added requirement in part (b). For part (a) alone we could
just as well have put the triangles only on the positive side and defined h(x) = 0 for x ≤ 12 .)

(b) Take f constructed in part (a) and add to it a strictly increasing bounded differentiable
function k(x) such that k ′ (x) does have a limit at ∞ and at −∞, e.g., k(x) = arctan(x), or
k(x) = 1 − e−x for positive x and ex − 1 (reflection in the origin) for negative x. Finally,
arrange the limit at −∞ to be 0 via a vertical shift by subtracting L = limx→−∞ (f (x)+k(x)).
(Why does this limit exist?) Altogether g(x) = f (x) + k(x) − L.
If one uses (a) as a black box, then more work is required. Take a function f with domain
[0, ∞) meeting the requirements in part (a). (If f it is defined for negative x, just discard
that part.) Now shift vertically to ensure f (0) = 0. Then define the function for x < 0 so as
to make it odd: f (x) = −f (−x). Note that f is has right hand derivative at 0 by the black
box, so the new function is still differentiable at 0 and hence everywhere. Reflection has
ensured that limx→−∞ f ′ (x) also fails to exist. Now continue as in the previous paragaph.
Remark: This problem is based on the following question raised by a student at CMI.
For an increasing, differentiable and bounded function f : R → R, must it be true that
limx→∞ f ′ (x) = 0? As seen in questions 17-18 in part A, if this limit exists, it must be 0,
bringing us to the situation in this problem.

B6. [16 points] a1 , a2 , a3 , . . . , an is a sequence of distinct numbers, each written on a card.
Take the cards one by one in order. Place them into stacks subject to this rule: one can only
place a smaller number on top of a larger number or one can start a new stack with a card.
Here is a simple greedy strategy. Make stacks along a line and place the incoming card on
top of the leftmost stack possible. So if the incoming card cannot be placed on any existing
stack, then we use that card to start a new stack to the right of all current stacks.
4
For example, with the sequence 3 7 2 5 6 4 9 8 we get the four stacks: 2 5 8
3 7 6 9

(a) Show that under the greedy strategy, the top numbers on the stacks increase from left
to right, e.g., 2 4 6 8 in the example above.
(b) Show that under the greedy strategy, the number of stacks is the length of a longest
possible increasing subsequence of a1 , a2 , a3 , . . . , an . A subsequence means ai1 , ai2 , . . . , aik
with 1 ≤ i1 < i2 < . . . < ik ≤ n. The example given above has an increasing subsequence of
length 4 (e.g., 3 5 6 8 among others) but none of length 5. It also gives 4 stacks as claimed.
Possible hint: for an entry x in the given sequence, let ℓ(x) = the length of a longest
increasing subsequence whose last entry is x. What are the values of ℓ(x) in the example?
(c) Show that the greedy strategy gives the minimum possible number of stacks.
(d) Find two sequences that give the same end result of stacks after using the greedy strategy.
(e) Show that not every sequence of legal stacks is obtainable by using the greedy strategy.
(Legal stack means numbers increase from top to bottom.) Given a sequence of legal stacks
along a line, how will you decide if it arises as the result of using the greedy strategy on
some sequence of numbers?

Solution

Use induction to prove (a) to (c). Note that by the very nature of these statements, in order
to be true, they have to be true at every stage of the described procedure.

(a) An incoming number x will skip stacks whose top numbers are less than x and go on top
of the first y (if any) bigger than x. Top entries of stacks to the right of y (if any) are bigger
than y by induction on the length of the sequence, so bigger than x.
(b) Claim: ℓ(x) = the number, say n(x), of the stack in which x is placed.
Proof: We prove ℓ(x) ≥ n(x) by induction on the length of the sequence. If n(x) = 1 then x
is smaller than all previous entries by (a). Otherwise let y = the top entry in stack n(x) − 1
at this point. We know y < x by (a). By induction there is an increasing subsequence of
length n(x) − 1 ending in y. Append x to this.
For n(x) ≥ ℓ(x), do induction on ℓ(x). (Or use the more basic argument in (c) below.)
Suppose ℓ(x) = k with increasing subsequence c1 < . . . < ck = x. If k = 1, then x is smaller
than all previous entries so must enter the first stack. Else by induction ck−1 must have
entered stack k − 1 or greater. Every subsequent change in any stack will only make the top
entry smaller. So x = ck , being bigger than ck−1 , must enter a stack to the right of ck−1 .
(c) If c1 < c2 < . . . < ck is an increasing subsequence then all ci must be in different stacks no
matter how the game is played. Prove this by induction on k. When ck comes the previous
k − 1 entries ci are in k − 1 different stacks (by induction), so the top numbers of those stacks
are all less than ck , which must therefore go to a different stack.
Therefore the number of stacks must be at least as much as the length of a longest increasing
subsequence. But by (b) the greedy strategy produces exactly these many stacks.
(d) 2 1 3 and 2 3 1 both yield the same result. (Generally if three consecutive entries yxz in
a sequence satisfy x < y < z then see that switching yxz to yzx leaves the result unaltered.)
(e) By part (a), for an attainable configuration the top entries of the stacks have to be
increasing from left to right. E.g., 2 followed by stack 1 3 cannot be attained. Even simpler,
a sequence of stacks of height 1 is attainable only if the numbers increase from left to right.

The condition in part (a) is also sufficient by induction on the length. Construct the sequence
backwards: remove the top entry of the rightmost stack and use it as the last entry in the
sequence. The stated condition stays valid for the remaining configuration. Iterate.

Remark: This problem is based on patience sorting. It is also related to the Robinson-
Schensted-Knuth correspondence, a beautiful and important chapter in combinatorics.