MODSMO

Round Two Solutions

October 2023
Question 1
Let n be a positive integer. A sequence a1 , a2 , . . . , an is called good if the following
conditions hold:

• For each i ∈ {1, 2, . . . , n}, 1 ≤ ai ≤ n

• For all positive integers i, j with 1 ≤ i ≤ j ≤ n, the expression

ai + ai+1 + · · · + aj

is not divisible by n + 1.

Find the number of good sequences (in terms of n).

Solution. The answer is n!. Let bi = a1 + · · · + ai . The condition reduces to the

bi being distinct and nonzero mod n + 1. This is because if bi ≡ bj mod n + 1 where
i < j, then bj − bi = ai+1 + · · · + aj ≡ 0 mod n + 1, violating the second condition of
the problem statement. Likewise, bi cannot be 0 mod n + 1. Furthermore, given the
values of bi mod n + 1, we can uniquely reconstruct the ai by taking it to be the unique
integer congruent to bi − bi−1 mod n + 1. Hence, the number of good sequences is the
number of valid sequences of b1 , . . . , bn , which is the number ways to choose n distinct
things (the values of bi ) in order from a set of n things (the nonzero remainders modulo
n + 1), i.e. n!.
Question 2
Let a, b, c, d be positive reals with a − c = b − d > 0. Show that
√ √ !4
ab a+ b
≥ √ √ .
cd c+ d

Solution. WLOG a ≥ b. Let t = a − b = c − d ≥ 0, and define

√ √
4
x+ x+t
f (x) = .
x(x + t)

The question is equivalent to showing that if b > d, then

√ √
4 √ √
4
a+ b c+ d
f (b) = ≤ = f (d).
ab cd
Now observe that
√ √
4
x+ x+t
f (x) =
x(x + t)
√ √ !4
x+ x+t
= √ √
4
x4x+t
r r !4
4
x 4 x + t
= + .
x+t x

Finally,
t t
d < b =⇒ ≥
d b
d+t b+t
=⇒ ≥ ≥1
rd br
4 d + t 4 b + t
=⇒ ≥ ≥1
d b
r r r r
4 d 4 d + t 4 b 4 b + t
=⇒ + ≥ + (*)
d+t d b+t b
=⇒ f (d) ≥ f (b),

thus the problem is solved.

(Note: (*) is true because
x + x1 is a non-decreasing function for x ≥ 1, which is true

1 1 1



because y + y − x + x = (y − x) 1 − xy ≥ 0 if y ≥ x ≥ 1.)
Question 3
Let △ABC be a triangle with orthocenter H, and let M and N be the midpoints of
BC and AH respectively. Suppose Q is a point on the circumcircle of ABC such that
∠AQH = 90◦ . Show that M N , the circumcircle of QN H, and the A-symmedian concur.
Note: the A-symmedian is the reflection of line AM in the bisector of angle ∠BAC.

Solution 1. Define E, F to be the feet of the altitudes from B and C. Let Y be the
midpoint of EF , we claim that Y is the desired concurrency point. We need to prove
the following:

1. Y lies on M N .
Since N is the center of the circle with diameter AH, which passes through E, F ,
N E = N F . Similarly, M is the center of the circle with diameter BC, which
passes through E, F , M E = M F .
So M N is the perpendicular bisector of EF , implying that the midpoint Y of EF
lies on M N .

2. Y lies on the circumcircle of QN H.

First, we show that M, H, Q are collinear. Let A′ be the antipode of A in the
circumcircle of ABC. It is easy to show by parallel lines that BHCA′ is a par-
allelogram, so HA′ passes through the midpoint M of BC. And since ∠AQH =
∠AQA′ = 90◦ , H, Q, A′ are collinear. This shows that M, H, A′ , Q are collinear.
We also need to show that M F is tangent to the circle with diameter AH. ∠M F H =
90◦ − ∠M F B = 90◦ − ∠ABC = ∠BAH = ∠F AH so M F is tangent to (AF H).
Now, by power of a point from M , M Y · M N = M F 2 = M Q · M H, so Y N QH is
cyclic.

3. Y lies on the A-symmedian. This is true because AE · AC = ∠AB · AF by power

of a point, so after reflecting △ABC over the angle bisector of ∠BAC and scaling
AF
by a factor of AC , it becomes △AEF . The midpoint M of BC gets mapped to the
midpoint Y of EF , so the lines AM and AY are reflections over the angle bisector
of ∠BAC, i.e. AY is the A-symmedian.

Solution 2. Let X be the second intersection of AM with the circle of diameter

AH, which we denote by (AH), and note that Q is on that circle since ∠AQH = 90◦ .
Furthermore let Y be the second intersection of N M with the circumcircle of QN H.
Now we observe that if A′ is the second intersection of QH with the circumcircle of
ABC, again since ∠AQH = 90◦ , we must have that A′ is the antipodal point of A. But
it is well known that H, M and A′ are collinear, hence Q, H, M are collinear. Trivially
we also know that Y , N and M are collinear, as are A, X and M , and that Y N QH and
QHAX are cyclic, but this means that by radical axes Y N AX must be cyclic too.
This means ∠XAY = ∠XN Y , and since N is the center of (AH), if we mark by Z
the second intersection of ray N Y with (AH) we have ∠XAY = ∠XN Z = 12 ∠XAZ.
Hence line AZ is the bisector of angle ∠XAY and it remains to show that it’s also the
angle bisector of ∠BAC.
For that purpose, let E, F be the second intersections of (AH) with AC and AB
respectively: it is well known that E and F are feet of the heights of B and C on their
opposite sides respectively, and that M is the center of the cyclic quadrilateral BEF C.
Hence line N M intersects (AH) at the midpoints of the two (minor and major) arcs EF
on (AH). But line M N is the same as line N Q, so one of those intersections must be
Z. This means that AZ is indeed one of the bisectors of ∠EAF , but obviously that’s
the same angle as ∠BAC, which finishes the proof.
Question 4
Let k be a positive integer. An arrangement of finitely many open intervals in R is called
good if for any of the intervals the number of other intervals which intersect with it is
a nonzero multiple of k. Find the maximum positive integer n (as a function of k) for
which there is no good arrangement with n intervals.

Proof. The answer is 2k, for k ≥ 2, and 1, for k = 1. The case k = 1 is trivial and
we do not consider it further. Henceforth assume k ≥ 2. First, we provide a construc-
tion for all n ≥ 2k + 1. Note that it would suffice to show it for 2k + 1 ≤ n ≤ 3k + 1,
since for any valid construction, we can add another k + 1 copies of the same interval,
disjoint from the other intervals. In what follows, let ε > 0 be a sufficiently small real
number, and let n = 2k + 1 + a, where 1 ≤ a ≤ k − 1. We split into 4 groups of intervals.

Group 1 contains the intervals (0, 2k + ε), (1, 2k + ε), . . . (k − a, 2k + ε)

Group 2 contains the intervals (k − a + 1, k + ε), . . . (k, k + ε)

Group 3 contains the intervals (k + 1, 2k + a + ε), . . . (2k, 2k + a + ε)

Group 4 contains the intervals (2k+1, 2k+1+ε), (2k+2, 2k+2+ε), . . . (2k+a, 2k+a+ε)

We now see that each interval in group 1 and 3 intersects 2k other intervals, while
each interval in groups 2 and 4 intersects k other intervals. Finally, for n = 2k + 1 and
n = 3k + 1, simply use 2k and 3k copies of the same interval respectively.

To finish, we prove that n = 2k fails. Note that in this case, we cannot have any
interval intersecting 2k or more intervals, so all intervals must intersect exactly k other
intervals. Consider the interval with the leftmost left endpoint, call it I.

I claim that any two intervals that intersect I must also intersect each other. Sup-
pose otherwise, and let us say intervals I1 , I2 intersect I but are disjoint. Notice that
any interval that intersects I must either contain its right endpoint, or it is a subset of
I. If both I1 and I2 contain the right endpoint of I, then they intersect. Therefore,one
of I1 , I2 is a subset of I. WLOG let it be I1 , then all k − 1 intervals (excluding I)
which intersect I1 must also intersect I. But I also intersects I1 and I2 , leading to I
intersecting at least k + 1 intervals, a contradiction.

Hence, all k intervals which intersect I also intersect each other, and thus in this group
of k + 1 intervals, all intervals already intersect k other intervals. This means that none
of them can intersect any of the remaining k − 1 intervals. But this is impossible, as
each interval intersects k others, so the other k − 1 intervals are forced to intersect one
of the k + 1, contradiction.
Question 5
Let n ≥ 3 be a positive integer. Consider two convex polygons with n vertices: A =
A1 A2 . . . An and B = B1 B2 . . . Bn . A triple (i, j, k) of pairwise distinct integers with
1 ≤ i, j, k ≤ n and i < k is said to be common if ∠Ai Aj Ak = ∠Bi Bj Bk . A and B are
said to be similar if all triples (i, j, k) of pairwise distinct integers with 1 ≤ i, j, k ≤ n
and i < k are common.
Determine in terms of n the least positive integer m such that, if there exist at least m
pairwise-distinct common triplets (i, j, k), then A and B are necessarily similar.
2
Solution. The answer is (n−1)(n−2)
2 . This is achieved by fixing n − 1 vertices on a
circle and moving the last vertex on the circle by a sufficiently small amount.
(n−1)(n−2)2
For the bound, we note that if we have more than 2 angles then by pigeon-
hole, at least 1 sub (n − 1)-gon of A has more than

n − 1 (n − 1)(n − 2)2 (n − 2)(n − 3)2

· >
n 2 2
angles in common with B, which is enough to make those sub n − 1-gons similar by
induction. Hence, let X be the remaining vertex of A, and Y the remaining vertex of
B. Let X ′ be the point such that X ′ along with the rest of B form a polygon similar to
A. Note that even after counting all (n−1)(n−2)(n−3)
2 angles in the sub-n − 1-gon, there
(n−1)(n−2)
are more than 2 common angles that involve Y .
Now, in any triangle △Y B1 B2 , if △Y B1 B2 shares 2 common angles with △XA1 A2 ,
then they are similar and hence Y = X ′ which would make the whole polygons similar.
Thus, for each pair of vertices of B, at most 1 common angle involving Y is produced.
This contradicts the fact that there are more than (n−1)(n−2)
2 common angles that involve
Y . Hence, we are done.
Question 6
Let p be a prime such that p−1
2 is also prime. A pair of integers (x, y) with 1 ≤ x, y ≤ p−1
is called a commuter if at least one of xy − y x or xy + y x is divisible by p. Show that the
√
number of commuters is at most 4.2p p.

Proof. Let q = p−12 . We first ignore the cases where one of x, y is 1, q, 2q mod p.
Consider a primitive root of p, call it g. Let x = g a , y = g b . The condition rewrites as
x2y ≡ y 2x mod p, and hence

{g a } {g b }
g 2ay = g 2bx mod p =⇒ 2ay ≡ 2bx mod p−1 =⇒ ay ≡ bx mod q =⇒ ≡ mod q
a b
where {g a } denotes the unique integer 1 ≤ x ≤ p − 1 such that g a ≡ x mod p. Because
x, y ̸= 1, −1, q, none of a, b, {g a }, {g b } are divisible by q, so our equation above is valid.
a
But note that x, y commute if and only if their value of {ga } is the same mod q. Hence,
a
we can split the residues mod p into classes based on their value of {ga } , and two
numbers will commute if and only if they are in the same class. The second idea is to
bound the size of each equivalence class. Consider one such class S, and let n = |S|.
Now, we look at a fixed number d and bound the number of pairs x, x + d ∈ S. Pick an
arbitrary a ∈ S. In what follows, all equalities are taken mod p. We have that:

ax+d (x + d)a x+d a

 
ad = x = ± = ±
a xa x

Since the maximum possible value of gcd(a, p − 1) is 2, we can find a k such that ak ≡ 2
mod p − 1. Raising both sides of the above equation to the power of k, we obtain that
 2
x+d
akd = ± =⇒ ak d · x2 = ±(x + d)2
x

However, since d, a, k are fixed, this is a quadratic in x and thus, each + or − version of
the equation can have at most 2 solutions for x mod p. Thus, there are overall at most
4 pairs x, x + d ∈ S. But there are n(n − 1) differences of two elements in S. Hence,
1 p
n(n − 1) < 4p =⇒ n ≤ + 4p
2
All that is left is to bound the number of commuters. Let there be k equivalence classes
with sizes s1 , . . . sk . Then the number of commuters (exluding 1, q, 2q) is
k k
"  #  
X
2
X 1 p 1 √
si ≤ si · + 4p ≤ +2 p ·p
2 2
i=1 i=1

Finally, observe (1, 1), (2q, a), (a, 2q), (q, q) are commuters, where a can be any integer
from 1 to p − 1. Hence the total number of commuters is at most
 
1 √ √ √
+ 2 p · p + 2p = 2.5p + 2p p ≤ 4.2p p
2

for any p ≥ 2.