39

04 − 09 2022
Note of Confidentiality

The shortlisted problems should be kept

strictly confidential until BMO 2023

Contributing countries

The Organising Committee and the Problem Selection Committee of the BMO 2022 wish
to thank the following countries for contributing problem proposals:

• Greece
• North Macedonia
• Romania
• Serbia
• United Kingdom

Problem Selection Committee

Chairman: Demetres Christofides

Members: Demetris Karantanos
Theoklitos Parayiou
Contents

PROBLEMS 3
Algebra 3

Combinatorics 4

Geometry 5

Number Theory 6

SOLUTIONS 7
Algebra 7
A1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
A2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
A3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
A4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
A5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
A6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Combinatorics 16
C1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
C2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
C3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
C4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
C5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Geometry 24
G1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
G2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
G3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
G4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
G5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
G6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Number Theory 34
N1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
N2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
N3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
N4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Shortlisted Problems with Solutions 3

PROBLEMS
ALGEBRA

A1. Find all functions f : R → R such that

f (x(x + f (y))) = (x + y)f (x)

for all x, y ∈ R.

A2. Let k > 1 be a real number, n ! 3 be an integer, and x1 ! x2 ! x3 ! · · · ! xn > 0 be real

numbers. Prove the inequality:

x1 + kx2 x2 + kx3 xn−1 + kxn xn + kx1 n(k + 1)

+ + ··· + + ! .
x2 + x3 x3 + x4 xn + x1 x1 + x2 2

A3. Let a, b, c, d be non-negative real numbers such that

1 1 1 1
+ + + = 3.
a+1 b+1 c+1 d+1
Prove that
4
3(ab + ac + ad + bc + bd + cd) + " 5.
a+b+c+d

A4. Find all functions f : R → R such that f (0) ∕= 0 and

f (f (x)) + f (f (y)) = f (x + y)f (xy)

for all x, y ∈ R.

A5. Find all functions f : (0, ∞) → (0, ∞) such that

f (yf (x)3 + x) = x3 f (y) + f (x)

for all x, y > 0.

A6. Let f : R2 → R be a function satisfying the following property:

If A, B, C, D ∈ R2 are the vertices of a square with sides of length 1, then

f (A) + f (B) + f (C) + f (D) = 0 .

Show that f (x) = 0 for all x ∈ R2 .

4 BMO 2022, Cyprus

COMBINATORICS

C1. There are 100 positive integer numbers written on a board. At each step, Alex composes 50
fractions using each number written on the board exactly once, brings these fractions to their
irreducible form, and then replaces the 100 numbers on the board with the new numerators
and denominators to create 100 new numbers. Find the smallest positive integer n such that
regardless of the values of the initial 100 numbers, after n steps Alex can arrange to have on
the board only pairwise coprime numbers.

C2. Alice is drawing a shape on a piece of paper. She starts by placing her pencil at the origin,
and then draws line segments of length 1, alternating between vertical and horizontal segments.
Eventually, her pencil returns to the origin, forming a closed, non-self-intersecting shape. Show
that the area of this shape is even if and only if its perimeter is a multiple of eight.

C3. Find the largest positive integer k for which there exists a convex polyhedron P with the
following properties:
(a) P has exactly 2022 edges.
(b) The degrees of the vertices of P don’t differ by more than 1.
(c) It is possible to colour the edges of P with k colours such that for every colour c, and
every pair of vertices (v1 , v2 ) of P , there is a monochromatic path between v1 and v2 in
the colour c.

C4. Let n ! 3 be an odd positive integer, and consider an n × n grid containing n2 cells.
Dionysus colours each cell either red or blue. A frog can hop directly between two cells if they
have the same colour and share at least one vertex. Xanthias views the colouring, and wants
to place frogs on k of the cells so that any cell can be reached by a frog in a finite number of
hops. Find the least value of k such that Xanthias can always be successful regardless of the
colouring chosen by Dionysus.

C5. A cube of side length 2021 is given. In how many ways we can place a 1 × 1 × 1 cubelet
on the border of this cube in such a way that the newly formed solid can be completely filled
using k × 1 × 1, 1 × k × 1 and 1 × 1 × k cuboids, for some k ∈ N \ {1}?
Shortlisted Problems with Solutions 5

GEOMETRY

G1. Let ABC be an acute triangle such that CA ∕= CB with circumcircle ω and circumcentre
O. Let τA , τB be the tangents to ω at A and B, which meet at X. Now, let Y be the foot of
the perpendicular from O onto CX, and let the line through C parallel to AB meet τA at Z.
Prove that Y Z bisects AC.

G2. Let ABC be a triangle with AB > AC with incenter I. The internal bisector of angle
BAC intersects the BC at the point D. Let M the midpoint of the segment AD, and let F be
the second intersection point of M B with the circumcircle of the triangle BIC. Prove that AF
is perpendicular to F C.

G3. Let ABC a triangle and let ω be its circumcircle. Let E be the midpoint of the minor arc
BC of ω, and M the midpoint of (BC). Let V be the other point of intersection of AM with ω,
F the point of intersection of AE with BC, X the other point of intersection of the circumcircle
of F EM with ω, X ′ the reflection of V with respect to M , A′ the foot of the perpendicular
from A to BC and S the other point of intrsection of XA′ with ω. If Z ∈ ω with Z ∕= X is
such that AX = AZ, then prove that S, X ′ and Z are collinear.

G4. Let ABC be a triangle and let the tangent at B to its circumcircle meet the internal
bisector of angle A at P . The line through P parallel to AC meets AB at Q. Assume that Q
lies in the interior of segment AB and let the line through Q parallel to BC meet AC at X and
P C at Y . Prove that P X is tangent to the circumcircle of triangle XY C.

G5. Let ABC be a triangle with circumcircle ω, circumcenter O, and orthocenter H. Let K
be the midpoint of AH. The perpendicular to OK at K intersects AB and AC at P and Q,
respectively. The lines BK and CK intersect ω again at X and Y , respectively. Prove that the
second intersection of the circumcircles of triangles KP Y and KQX lies on ω.

G6. Let ABC be a triangle with AB < AC and let D be the other intersection point of the
angle bisector of A with the circumcircle of triangle ABC. Let E and F be points on the sides
AB and AC respectively, such that AE = AF and let P be the point of intersection of AD and
EF . Let M be the midpoint of BC. Prove that AM and the circumcircles of triangles AEF
and P M D pass through a common point.
6 BMO 2022, Cyprus

NUMBER THEORY

N1. Let n be a positive integer. What is the smallest sum of digits of 5n + 6n + 2022n ?

N2. Let a, b, n be positive integers such that:

(i) a2021 | n and b2021 | n
(ii) 2022 | a − b and a > b.
Prove that there is a subset of the divisors of the number n having sum of elements divisible by
2022 but not by 20222 .

N3. For every natural number x, let P (x) be the product of the digits of the number x. Is
there a natural number n such that the numbers P (n) and P (n2 ) are non-zero squares of natural
numbers, where the number of digits of the number n is equal to
(a) 2021
(b) 2022

N4. A hare and a tortoise run in the same direction, at constant but different speeds, around
the base of a tall square tower. They start together at the same vertex, and the run ends when
both return to the initial vertex simultaneously for the first time. Suppose the hare runs with
speed 1, and the tortoise with speed less than 1. For what rational numbers x is it true that, if
the tortoise runs with speed x, the fraction of the entire run for which the tortoise can see the
hare is also x?
Shortlisted Problems with Solutions 7

SOLUTIONS
ALGEBRA

A1. Find all functions f : R → R such that

f (x(x + f (y))) = (x + y)f (x)

for all x, y ∈ R.
Proposed by ................................

Solution 1. By putting x = y = 0, we get f (0) = 0. Also, by putting x ∈ R and y = 0, we get

f (x2 ) = xf (x) for all x, and therefore xf (x) = −xf (−x) for all x, which implies that f is an
odd function.
Obviously, the constant function f (x) = 0 for all x ∈ R, is a solution.
Assume that f is not identically zero. So there is some a ∈ R such that f (a) ∕= 0. Thus, a ∕= 0.
Suppose that there is another 0 ∕= b ∈ R, such that f (b) = 0. For x = a, y = b we get

af (a) = f (a2 ) = f (a(a + f (b))) = (a + b)f (a) = af (a) + bf (a) .

Since f (a) ∕= 0 we get b = 0.

Finally, by putting x ∈ R and y = −x, we get f (x2 +xf (−x)) = f (x2 −xf (x)) = 0, for all x ∈ R.
Thus, x2 −xf (x) = 0, i.e. x2 = xf (x) = f (x2 ), for all x ∈ R. Hence f (x) = x for all x ∈ R+ and
since f is odd we have f (x) = x for all x ∈ R. This last function obviously satisfies the equation.

Solution 2. As in Solution 1 we have that f (x2 ) = xf (x) for all x ∈ R and that if f is not
identically zero then f (x) = 0 =⇒ x = 0.
Now for x = −f (y) we get
(y − f (y))f (−f (y)) = f (0) = 0
and therefore y = f (y) or f (−f (y)) = 0 for each y ∈ R. I.e. f (y) = y or f (y) = 0 for each
y ∈ R. Since f (y) = 0 =⇒ y = 0 then f (y) = y for each y ∈ R.
8 BMO 2022, Cyprus

A2. Let k > 1 be a real number, n ! 3 be an integer, and x1 ! x2 ! x3 ! · · · ! xn > 0 be real

numbers. Prove the inequality:

x1 + kx2 x2 + kx3 xn−1 + kxn xn + kx1 n(k + 1)

+ + ··· + + ! .
x2 + x3 x3 + x4 xn + x1 x1 + x2 2

Proposed by ................................

Solution 1. Writing xn+1 = x1 , by AM-GM we have

!
" n
x1 + x2 x2 + x3 xn−1 + xn xn + x1 "$ xi + xi+1
+ + ··· + + ! n# = n.
x2 + x3 x3 + x4 xn + x1 x1 + x2 xi+1 + xi+1
i=1

So it is enough to prove that

x1 x2 xn n
+ + ··· + ! .
x1 + x2 x2 + x3 xn + x1 2
Letting ai = xi+1 /xi for i = 1, 2, . . . , n, it is enough to prove that
1 1 n
+ ··· + ! .
1 + a1 1 + an 2
Note that a1 , . . . , an−1 " 1 and a1 a2 · · · an = 1.
Equivalently, it is enough to prove that if m ! 2 is an integer and a1 , . . . , am " 1 are real
numbers then
1 1 m+1 a1 a2 · · · am
+ ··· + ! − .
1 + a1 1 + am 2 1 + a1 a2 · · · am
We proceed by induction on m. In fact the statement is true even for m = 1 so we assume that
it is true for m = k and proceed with the inductive step. Letting a = a1 · · · ak and b = ak+1 it
is enough to prove that
1 a 1 ab
− ! − .
1+b 1+a 2 1 + ab
We have
a ab a(1 − b) 1−b 1 1
− = " = −
1 + a 1 + ab (1 + a)(1 + ab) 1+b 1+b 2
so the result follows.

1 1
Solution 2. Since 1+x = 2 + 12 · 1−x
1+x , with the notation of Solution 1 it is enough to prove that

1 − a1 1 − an
+ ··· + ! 0.
1 + a1 1 + an
1−x
Letting f (x) = 1+x one can check that

(1 − x)(1 − y)(1 − xy)

f (x) + f (y) − f (xy) = .
(1 + x)(1 + y)(1 + xy)
Thus f (x) + f (y) ! f (xy) for x, y " 1. So inductively
1 − a1 1 − an−1 1 − a1 · · · an−1 1 − 1/an 1 − an
+ ··· + ! = =−
1 + a1 1 + an−1 1 + a1 · · · an−1 1 + 1/an 1 + an
and the result follows.
Shortlisted Problems with Solutions 9

A3. Let a, b, c, d be non-negative real numbers such that

1 1 1 1
+ + + = 3.
a+1 b+1 c+1 d+1
Prove that
4
3(ab + ac + ad + bc + bd + cd) + " 5.
a+b+c+d

Proposed by ................................

Solution. Let S = a + b + c + d. By AM-HM (or Cauchy-Schwarz) we have

16 16
S + 4 = (a + 1) + (b + 1) + (c + 1) + (d + 1) ! 1 1 1 1 =
a+1 + b+1 + c+1 + d+1
3

giving S ! 43 .
Multiplying the given equality by (a + 1)(b + 1)(c + 1)(d + 1) we get
% % & % % '
abc + 2 ab + 3S + 4 = 3 abcd + abc + ab + S + 1

giving % %
3abcd + 2 abc + ab = 1 .
In particular ab + ac + ad + bc + bd + cd " 1. So we may assume that S < 2 as otherwise the
inequality is immediate.
The given equality transforms to
a b c d
+ + + = 1,
a+1 b+1 c+1 d+1
and so by Cauchy-Schwarz % % a
a(a + 1) ! S2 .
a+1
Thus %
S 2 " a 2 + b2 + c 2 + d 2 + S = S 2 − 2 ab + S .
(
So ab " S/2 and it is enough to prove that

3S 4
+ " 5.
2 S
This is equivalent to 3S 2 − 10S + 8 " 0 which in turn is equivalent to (S − 2)(3S − 4) " 0.
Since S ! 4/3 and we are also assuming that S < 2, then the inequality is true and the result
follows.

Remark. From the above Solution it follows that we have equality in the cases that a = b =
c = d = 43 and in the case that two of the variables are equal to 1 and the other two are equal
to 0.
10 BMO 2022, Cyprus

A4. Find all functions f : R → R such that f (0) ∕= 0 and

f (f (x)) + f (f (y)) = f (x + y)f (xy)

for all x, y ∈ R.
Proposed by ................................

Solution 1. We show that f (x) = 2 for every x ∈ R.

c2
Let f (0) = c ∕= 0. Then for x = y = 0 we get f (c) = 2. Now for y = 0 we get

c2
f (f (x)) = cf (x) − . (1)
2
The given equation can now be rewritten as

c(f (x) + f (y)) = c2 + f (x + y)f (xy) . (2)

For x = 1, y = −1 in (2) we obtain

cf (1) + cf (−1) = c2 + cf (−1) .

Since c ∕= 0, then f (1) = c. For y = 1 in (2) we have

cf (x) = f (x)f (x + 1) (3)

for all x ∈ R. Now if f (x) ∕= 0 for all x, then f (x + 1) = c for all x, so f is constant. Plugging
into the given equation we get f (x) = 2 for all x ∈ R.
On the other hand, if there exists x0 such that f (x0 ) = 0, then f (f (x0 )) = f (0) = c, so for
x = x0 in (1) we get

c2 c2
cf (x0 ) − = f (f (x0 )) = c =⇒ − = c =⇒ c = −2 .
2 2
c2
From here we get f (−2) = f (c) = 2 = 2, hence f (f (−2)) = f (2). For x = −2 in (1) we get

c2
f (2) = f (f (−2)) = cf (−2) − = −2f (−2) − 2 = −6 .
2
We also have, for x = 1 in (3), that f (2) = c = −2, a contradiction. So there are no more
functions.

Solution 2.
For x = −1, y = t and for x = −1, y = 1 − t we get

f (f (−1)) + f (f (t)) = f (t − 1)f (−t) = f (−t)f (t − 1) = f (f (−1)) + f (f (1 − t)) .

It follows that f (f (t)) = f (f (1 − t)) for every t ∈ R. Now for x = t, y = 1 − t we get

2f (f (t)) = f (f (t)) + f (f (1 − t)) = f (1)f (t − t2 )

and therefore
f (1) ) *
f (x − x2 ) + f (y − y 2 ) = f (x + y)f (xy) . (1)
2
Shortlisted Problems with Solutions 11

For x = y = 0 in (1) we get f (1) = f (0). Now for y = 0 in (1) we get

f (x − x2 ) + f (0) = 2f (x)
for every x ∈ R. Now (1) gives
f (0)
[2f (x) + 2f (y) − 2f (0)] = f (x + y)f (xy)
2
thus
f (x + y)f (xy)
f (x) + f (y) = f (0) + (2)
f (0)
for every x, y ∈ R.
For x = y = 1 in (2), and since f (1) = f (0) we get f (2) = f (0) as well.
We claim that f (x) ∕= 0 for each x so assume for contradiction that f (a) = 0 for some a ∈ R.
For x = y = a/2 in (2) we get f (a/2) = f (0)/2. Now for x = a/2, y = 2 in (2) we get
3f (0)/2 = f (0), a contradiction as f (0) ∕= 0.
Now for y = 1 in (2), since f (1) = f (0) and f (x) ∕= 0 we get f (x + 1) = f (0). Thus f is constant
and from the original equation we get f (x) = 2 for each x ∈ R.

Alternative Formulation 1. Same problem but without the restriction f (0) ∕= 0.

√ √
Solution. Pick an α ∈ (0, 4) and a set A ⊆ [α, 2 α] not containing both of α and 2 α. Then
any function satisfying f (x) = 0 for x ∈
/ A and f (x) ∈
/ A for x ∈ A is a solution.
To see this, note that f (f (x)) = 0 for every x ∈ R. Furthermore, given x, y ∈ R we must
have s = x + y ∈/ A or p = xy ∈ / A. If this is not the case then the quadratic t2 − st + p has
√ 2
discriminant s − 4p " (2 α) − 4α = 0 where the equality is not possible as A does not contain
2
√
both of α and 2 α. This is a contradiction as the quadratic has the real numbers x and y as
roots. From these it follows that any such function is indeed a solution.
We now show that every additional solution of the functional equation is of the above form.
Assuming f (0) = 0 and putting y = 0 in the original equation we get f (f (x)) = 0 for each
x ∈ R. Therefore f (x + y) = 0 or f (xy) = 0 for each x, y ∈ R.
Let A = {x ∈ R : f (x) ∕= 0} and suppose that it is non-empty. Given b ∈ / (0, 4), the discrim-
inant of the quadratic x2 − bx + b is ∆ = b2 − 4b > 0. So there are real numbers x1 , x2 with
x1 + x2 = b = x1 x2 giving f (b) = 0 and so b ∈ / A. Now let α = inf A. If α ∈ A, then for
√
any b ! 2 α the quadratic t2 − bt + α has discriminant b2 − 4α > 0 so it has real roots. This
√
/ A, then for any b > 2 α we can find α′ ∈ A with
f (α)f (b) = 0 and so f (b) = 0. If α ∈
gives √
b ! 2 α′ . A similar argument as before shows b ∈ / A concluding the proof.

Alternative Formulation 2. Same problem as in Alternative Formulation 1 but in the case

of f (0) = 0 instead of asking for all of the solutions ask for the determination of infinitely many
solutions.

Alternative Formulation 3. Same problem, without the restriction that f (0) ∕= 0 but with
the restriction that f is monotonic.
Solution. If f (0) = 0 then as in the Solution of the Alternative Formulation 1 we have
f (a) = 0 for a ∈
/ (0, 4). Since f is monotonic it must then be identically equal to 0 which is a
valid solution.
Note: The monotonicity can be used to give slightly shorter solutions in the case f (0) ∕= 0.
12 BMO 2022, Cyprus

A5. Find all functions f : (0, ∞) → (0, ∞) such that

f (yf (x)3 + x) = x3 f (y) + f (x)

for all x, y > 0.

Proposed by ................................

t
Solution. Setting y = f (x)3
we get
+ ,
t
f (x + t) = x3 f + f (x) (1)
f (x)3
for every x, t > 0.
From (1) it is immediate that f is increasing.
Claim. f (1) = 1
1 3
Proof of Claim. Let c = f (1). If c < 1, taking x = 1 and y = 1−c 3 we have y − yc = 1, so
3 3 3
yf (1) + 1 = y and f (yf (1) + 1) = f (y) = 1 f (y). Thus f (1) = 0, a contradiction. Assume
now for contradiction that c > 1. We claim that

f (1 + c3 + · · · + c3n ) = (n + 1)c

for every n ∈ N. We proceed by induction, the case n = 0 being trivial. The inductive step
follows easily by taking x = 1, t = c3 + c6 + · · · + c3(k+1) in (1).
Now taking x = 1 + c3 + · · · + c3n−3 , t = c3n in (1) we get
+ ,
3 3n 3 3n−3 c3n
(n + 1)c = f (1 + c + · · · + c ) = (1 + c + · · · + c )f + nc
(n + 1)3
giving + ,
c3n c c3n
f = < c = f (1) =⇒ < 1.
(n + 1)3 (1 + c3 + · · · + c3n )3 (n + 1)3
But this leads to a contradiction if n is large enough. □
Now for x = 1 we get f (y + 1) = f (y) + 1 and since f (1) = 1 inductively we get f (n) = n for
every n ∈ N. For m, n ∈ N, setting x = n, y = q = m/n we get
- .
mn2 + n = f qn3 + n = f (yf (x)3 + x) = x3 f (y) + f (x) = n3 f (q) + n =⇒ f (q) = q .

Since f is strictly increasing with f (q) = q for every q ∈ Q>0 we deduce that f (x) = x for every
x > 0. It is easily checked that this satisfies the functional equation.

Alternative Formulation. Find all functions f : R → R such that

f (yf (x)3 + x) = x3 f (y) + f (x)

Solution. For x = y = 0 we get f (0) = 0. Let a = ∕ 0 and assume f (a) = 0. For x = a we

get a f (y) = 0 for every y ∈ R and therefore f (x) = 0 for every x ∈ R which is obviously a
3

solution.
So we may assume that f (x) ∕= 0 for every x ∕= 0. Let c = f (1). If c ∕= 1, taking x = 1 and
1 3 3 3 3
y = 1−c 3 we have y − yc = 1, so yf (1) + 1 = y and f (yf (1) + 1) = f (y) = 1 f (y). Thus
f (1) = 0, a contradiction.
Shortlisted Problems with Solutions 13

Thus f (1) = 1 which for x = 1 gives f (y + 1) = f (y) + 1 for every y ∈ R. From here we easily
get f (n) = n for every n ∈ Z.
For x = −1 in the original equation we get

f (−y − 1) = −f (y) − 1 = −(f (y) + 1) = −f (y + 1)

for every y ∈ R and therefore f is an odd function.

t
For x ∕= 0 and y = ± f (x) 3 we have

+ ,
t
f (t + x) = x3 f + f (x)
f (x)3
+ ,
3 t
f (−t + x) = −x f + f (x)
f (x)3

for every x ∕= 0 and every t ∈ R. Adding those two we get

2f (x) = f (x + t) + f (x − t)

for every x ∕= 0 and every t ∈ R. Since f is odd the above also holds for every x, t ∈ R. Given
a, b ∈ R and putting x = a, t = b and then x = b, t = a in the above we have

f (a + b) = 2f (a) − f (a − b) = 2f (a) + f (b − a) = 2f (a) + 2f (a) − f (a + b)

giving f (a + b) = f (a) + f (b) for every a, b ∈ R. I.e. f is Cauchy. In particular from the original
equation we get f (yf (x)3 ) = x3 f (y) for every x, y ∈ R. For y = 1 we get f (f (x)3 ) = x3 for
every x ∈ R. In particular f is surjective.
Putting y = f (x)3 in the last equation we get f (f (x)6 ) = x3 f (f (x)3 ) = x6 . By surjectivity we
get that f (a) ! 0 for every a ! 0. So for x ! y we have f (x) − f (y) = f (x − y) ! 0. I.e. f is
monotone and since it is Cauchy it is also linear which gives f (x) = x for every x ∈ R. This
clearly satisfies the functional equation.
14 BMO 2022, Cyprus

A6. Let f : R2 → R be a function satisfying the following property:

If A, B, C, D ∈ R2 are the vertices of a square with sides of length 1, then

f (A) + f (B) + f (C) + f (D) = 0 .

Show that f (x) = 0 for all x ∈ R2 .

Proposed by ................................

Solution. Let V be the set of all such functions. It is obvious that if f, g ∈ V then f + g ∈ V .
It is also obvious that if f ∈ V and a ∈ R2 then for g : R2 → R defined by g(x) = f (x + a) we
have g ∈ V .
Clearly, we can consider the elements of R2 as vectors. We denote the inner product of two
vectors a = (a1 , a2 ) and b = (b1 , b2 ) by a · b = a1 b1 + a2 b2 . A vector a is unit vector if a · a = 1.
Two vectors a, b are orthogonal if and only if a · b = 0. So a square ABCD whose vertices are
given by the vectors a, b, c, d is a unit square if and only if the vectors b − a, c − b, d − c, a − d
are unit vectors with consecutive pairs of them being orthogonal.
We say that f ∈ V is good for a unit vector v if either f (x + v) = −f (x) for every x ∈ R2 or
f (x + v ⊥ ) = −f (x) for some unit vector v ⊥ orthogonal to v and every x ∈ R2 . We also say that
f is good for a set of unit vectors if it is good for every vector in the set.
Note that if f, g ∈ V are good for S then so is f + g. Furthermore, if f ∈ V is good for S and
a ∈ R2 then g(x) = f (x + a) is also good for S.
Claim 1. If V ∕= {0}, then given any finite set S of unit vectors, there is a g ∈ V \ {0} which
is good for S.
Proof of Claim 1. We proceed by induction on |S|. So assume that f ∈ V \ {0} is good for S
and that we are trying to find a g ∈ V \ {0} which is good for S ∪ {v} for some unit vector v.
Let v ⊥ be a unit vector orthogonal to v. If f (x + v ⊥ ) = −f (x) for all x ∈ R2 , we are done.
Otherwise, define g : R2 → R by

g(x) = f (x) + f (x + v ⊥ ) .

From the observations above g is good for S. Furthermore, since x, x + v, x + v + v ⊥ , x + v ⊥

form the vertices of a unit square we have

g(x) + g(x + v) = f (x) + f (x + v ⊥ ) + f (x + v) + f (x + v + v ⊥ ) = 0 .

Hence g is good for v as well and therefore it is good for S ∪ {v}. □.

We now say that f ∈ V is excellent for a unit vector v if f (x + 12v) = f (x) for every x ∈ R. We
also say that f is excellent for a set of unit vectors if it is excellent for every vector in the set.
Note that if f, g ∈ V are excellent for S then so is f + g. Furthermore, if f ∈ V is excellent for
S and a ∈ R2 then g(x) = f (x + a) is also excellent for S.
Claim 2: If V ∕= {0}, then given any finite set S of unit vectors, there is a g ∈ V \ {0} which
is excellent for S.
Proof of Claim 2. We proceed by induction on |S|. So assume that f ∈ V \ {0} is excellent
for S and that we are trying to find a g ∈ V \ {0} which is excellent for S ∪ {v} for some unit
vector v.
Shortlisted Problems with Solutions 15

The proof of Claim 1 shows that we may assume that f is good for v. (The construction in
the proof of the Claim preserves the excellence.) If f (x + v) = −f (x) for every x ∈ R2 , then
f (x+12v) = f (x) for every x ∈ R2 and we are done. So we may suppose that f (x+v ⊥ ) = −f (x)
for every x ∈ R2 where v ⊥ is a unit vector orthogonal to v.
⊥ ⊥
Let u = 3v+4v
5 and let u⊥ = 4v−3v
5 . Then u and u⊥ are unit vectors. The proof of Claim 1
shows that we may assum that f is good for u.
If f (x + u) = −f (x) for every x ∈ R2 , then

f (x) = −f (x + 5u) = −f (x + 3v + 4v ⊥ ) = −f (x + 3v) .

So f (x + 12v) = f (x) for every x ∈ R2 and we are done.

If f (x + u⊥ ) = −f (x) for every x ∈ R2 , then

f (x) = −f (x + 5u⊥ ) = −f (x + 4v − 3v ⊥ ) = f (x + 4v) .

So again f (x + 12v) = f (x) for every x ∈ R2 and we are done. □

From Claim 1 we have a unit vector v and an f ∈ V \ {0} such that f (x + v) = −f (x) for every
x ∈ R2 . Pick unit vectors u, w such that 12u, 12w, v form a triangle. I.e. 12u + 12w + v = 0.
From the proof of Claim 2 we may also assume that f is excellent for u, w. (While preserving
the property f (x + v) = −f (x) for every x ∈ R2 .)
Now given any x ∈ R2 we have

f (x) = f (x + 12u + 12w + v) = f (x + 12w + v) = f (x + v) = −f (x)

thus f (x) = 0. Since this holds for every x ∈ R2 , this contradicts the fact that f ∈ V \ {0} and
therefore our assumption that V ∕= {0}.
16 BMO 2022, Cyprus

COMBINATORICS

C1. There are 100 positive integer numbers written on a board. At each step, Alex composes 50
fractions using each number written on the board exactly once, brings these fractions to their
irreducible form, and then replaces the 100 numbers on the board with the new numerators
and denominators to create 100 new numbers. Find the smallest positive integer n such that
regardless of the values of the initial 100 numbers, after n steps Alex can arrange to have on
the board only pairwise coprime numbers.
Proposed by ................................

Solution. Equivalently, we have a graph on 100 vertices and a positive integer written on each
vertex. At each step we pick a perfect matching (i.e. a set of disjoint edges covering all vertices)
and for each edge of the matching we divide the numbers in its endpoints with their highest
common divisor.
If initially the numbers on the vertices are p1 , p2 , . . . , p99 and p1 p2 · · · p99 , where p1 , . . . , p99 are
distinct prime numbers, then we need at least 99 steps. This is because the vertex having the
number p1 p2 · · · p99 needs to be matched with every other vertex and we need 99 steps for this.
We show that 99 steps are enough. For this it is enough to show that K100 has a 1-factorisation.
I.e. we can decompose the edges of the complete graph on 100 vertices into 99 perfect matchings.
In general it is a known fact that K2n has a 1-factorisation. For one way to achieve this, write
x, x1 , . . . , x2n−1 for the vertices, and for the i-th matching (1 " i " 2n − 1) consider all edges
of the form xr xs with 1 " r < s " 2n − 1 and r + s ≡ i mod 2n − 1 together with the edge xxt
where 2t ≡ i mod 2n − 1.
Shortlisted Problems with Solutions 17

C2. Alice is drawing a shape on a piece of paper. She starts by placing her pencil at the origin,
and then draws line segments of length 1, alternating between vertical and horizontal segments.
Eventually, her pencil returns to the origin, forming a closed, non-self-intersecting shape. Show
that the area of this shape is even if and only if its perimeter is a multiple of eight.
Proposed by ................................

Solution 1. Colour the horizontal segments in every other line of the grid alternately red and
blue as shown below:

Let there be r red segments on the perimeter and s red segments in the interior of the shape.
By considering the possibilities starting from a red segment, we see that every fourth segment
on the perimeter of the shape will be red, therefore we have P = 4r. Also, every square has
exactly one red edge, thus A = r + 2s. So A ≡ r mod 2 from which the result follows.

Solution 2. Colour the square in the grid with a chessboard colouring. The alternation of
vertical and horizontal segments means that all squares with an edge on the perimeter and lying
within the shape are of the same colour, say black.

Any internal edge within the shape lies between a white and black square, so if the number of
white squares within the shape is W , the number of edges of the chessboard lying inside the
shape is 4W . If the total number of squares in the shape is A, then 4A counts every edge on
the perimeter once, and every internal edge twice, so the perimeter has length P = 4A − 8W ,
which is a multiple of 8 if and only if A is even.
18 BMO 2022, Cyprus

Solution 3. We have as many horizontal perimeter edges as vertical, so it is enough to show

that the area is even if and only if the number of vertical perimeter edges is a multiple of 4. In
each horizontal strip oof height 1, pair the vertical perimeter edges in order from left to right.
(We can do so because there must be an even number of vertical perimeter edges in every such
strip.) Let us assume that we have P such pairs. So we need to show that the area is even if
and only if P is even.
As in Solution 2, every such pair of perimeter edges encloses a consecutive set of squares of the
shape with the first and last of these squares being, without loss of generality, black. So each
such pair accounts for an odd number of squares inside the shape and therefore the area is even
if and only if P is even as required.

Solution 4. By Green’s Theorem the area of the shape is equal to

/
x dy
C

where C is the boundary of the shape traversed anticlockwise. We partition C into its line
segments of length 1. Each line segment contributes 0 to the integral if it is horizontal and ±a
to the integral if it is on the vertical line x = a. Every two consecutive vertical line segments
contribute ±a ± (a ± 1) ≡ 1 mod 2.
So the area is even if and only if the number of vertical line segments is 0 mod 4 which happens
if and only if the perimeter is 0 mod 8. (Since there is an equal even number of horizontal and
vertical line segments.)
Shortlisted Problems with Solutions 19

C3. Find the largest positive integer k for which there exists a convex polyhedron P with the
following properties:
(a) P has exactly 2022 edges.
(b) The degrees of the vertices of P don’t differ by more than 1.
(c) It is possible to colour the edges of P with k colours such that for every colour c, and
every pair of vertices (v1 , v2 ) of P , there is a monochromatic path between v1 and v2 in
the colour c.

Proposed by ................................

Solution 1. We divide the solution in two steps, first we prove that k < 3, and then give an
inductive construction of P for k = 2.
Let P have V vertices, E edges and F faces. Suppose the contrary, that k > 2. We have k
disjoint trees on V vertices, so E ! 3(V − 1). This is a contradiction as for every polyhedron
we have E " 3V − 6.
Now we take k = 2 and prove that for every positive integer n, we can find a convex polyhedron
P6n with exactly 6n edges that satisfies the condition of the problem.
For n = 1, let’s consider the tetrahedron ABCD. One colouring that works is: AB, AD and
CD are in one colour, and AC, BC and BD are in the other colour.
Suppose we have constructed P6n , here is how to construct P6n+6 : Consider the triangular
face T = xyz most recently added to P6n , glue on top of T a truncated pyramid whose larger
base is T . We are effectively adding 3 new vertices, say x′ , y ′ , z ′ , 3 faces, and 6 edges, say
xx′ , yy ′ , zz ′ , x′ y ′ , y ′ z ′ , z ′ x′ . We colour x′ y ′ , x′ z ′ , yy ′ with the first colour, and all other new edges
with the second colour. It is now easy to see that in any one of the colours, a tree on the vertices
of P6n in that colour, together with the newly added edges of that colour give a tree on the
vertices of P6n+6 in that colour.
Note that x′ y ′ z ′ is the most recently added triangular face, so the construction can proceed
inductively by glueing another truncated pyramid on top of it. It’s easy to see (and prove
inductively) that every vertex has degree 3 or 4, so condition (b) is satisfied and we are done.

Solution 2. For the construction we can also use Steinitz’s Theorem on the characterization
of convex polyhedra: A planar graph is the graph of a convex polyhedron if and only if it
is 3-vertex connected. So we can take for example the graph on {v1 , v2 , . . . , v2n } with edges
v1 v2 , v2 v3 , . . . , v2n−1 v2n in one colour and v1 v3 , v2 v4 , . . . , v2n−2 v2n and v2n v1 in the other colour.
It is easy to get a planar embedding of this graph as for example in the following figure for the
case n = 4.
20 BMO 2022, Cyprus

This graph is 3-connected: Suppose we remove the vertices vi and vj with i < j. If i = 1, j = 2
or i = 2n − 1, j = 2n the remaining graph is obviously connnected. If 1 < i and j = i + 1 < 2n
the remaining graph is also connected having the spanning path vi−1 vi−2 · · · v1 v2n v2n−1 · · · vi+1 .
Otherwise j > i + 1 and we have the spanning path v1 · · · vi−1 vi+1 · · · vj−1 vj+1 · · · v2n .
This graph has 2n − 2 edges so for n = 1012 it has the required number of edges. Furthermore
it satisfies (b) as every vertex has degree 3 or 4.
Comments.
1. One can consider a slightly simplified version of the problem in which we specify that
k = 2, i.e. we only consider colourings with 2 colours.
2. The goal of condition (b) (vertex degrees not differing by more than 1) is to avoid a simple
solution with a pyramid with 1012 vertices. There can be other ways to introduce this
type of constraint, for example requiring that there is pair of edges with distance at least
300 (in terms of edges between them). Another way could be that no vertex has a degree
higher than 4. Another way can be that for every vertex (face) we can find another vertex
(face) with same number of edges.
Shortlisted Problems with Solutions 21

C4. Let n ! 3 be an odd positive integer, and consider an n × n grid containing n2 cells.
Dionysus colours each cell either red or blue. A frog can hop directly between two cells if they
have the same colour and share at least one vertex. Xanthias views the colouring, and wants
to place frogs on k of the cells so that any cell can be reached by a frog in a finite number of
hops. Find the least value of k such that Xanthias can always be successful regardless of the
colouring chosen by Dionysus.
Proposed by ................................

Solution. Let G be the graph whose vertices are all (n + 1)2 vertices of the grid and where two
vertices are adjacent if and only if they are adjacent in the grid and moreover the two cells in
either side of the corresponding edge have different colours.
The connnected components of G, excluding the isolated vertices, are precisely the boundaries
between pairs of monochromatic regions each of which can be covered by a single frog. Each
time we add one of these components in the grid, it creates exactly one new monochromatic
region. So the number of frogs required is one more than the number of such components of G.
It is easy to check that every corner vertex of the grid has degree 0, every boundary vertex of
the grid has degree 0 or 1 and every ‘internal’ vertex of the grid has degree 0, 2 or 4. It is also
easy to see that every component of G which is not an isolated vertex must contain at least
four vertices unless it is the boundary of a single corner of the grid, in which case it contains
only three vertices.
Writing N for the number of components which are not isolated vertices, we see that in total
they contain at least 4N − 4 vertices. (As at most four of them contain 3 vertices and all others
contain 4 vertices.) Since we also have at least 4 components which are isolated vertices, then
2
4N = (4N − 4) + 4 " (n + 1)2 . Thus N " (n+1) 4 and therefore the minimal number of frogs
(n+1)2
required is 4 + 1.
This bound for n = 2m + 1 is achieved by putting coordinates (x, y) with x, y ∈ {0, 1, . . . , 2m}
in the cells and colouring red all cells both of whose coordinates are even, and blue all other
cells. An example for n = 9 is shown below.
22 BMO 2022, Cyprus

C5. A cube of side length 2021 is given. In how many ways we can place a 1 × 1 × 1 cubelet
on the border of this cube in such a way that the newly formed solid can be completely filled
using k × 1 × 1, 1 × k × 1 and 1 × 1 × k cuboids, for some k ∈ N \ {1}?
Proposed by ................................

Solution 1. Suppose that for some k > 1 and some placed cubelet there is a valid filling. In
each unit cubelet (of the original cube) with coordinates (x, y, z) where 0 " x, y, z " 2020, we
2πi
assign the complex number ω x+y+z where ω = e k . We also assign the number ω a+b+c in the
additional cubelet in position (a, b, c).
k
−1
Since 1 + ω + ω 2 + · · · + ω k−1 = ωω−1 = 0, then the sum of numbers in any 1 × 1 × k cuboid is
equal to zero. So the sum of all assigned numbers is equal to

0 = (1 + ω + · · · + ω 2020 )3 + ω a+b+c . (1)

This gives
0 0
0 0 0 1 − ω 2021 03
1=|−ω a+b+c 0
| = (1 + ω + · · · + ω 2020 3 0
) =0 0 0 .
1−ω 0
Thus |1 − ω| = |1 − ω 2021 | which means that 1 is equidistant from the numbers ω and ω 2021 .
Since |ω 2021 | = 1, this happens if and only if ω 2021 = ω or ω 2021 = ω −1 . Then ω 2020 = 1 or
ω 2022 = 1 which gives k|2020 or k|2022. However k|20213 + 1. Since 20213 + 1 ≡ 2 mod 2020, if
k|2020 then k|2. So in any case we have k|2022. Now (1) gives

ω a+b+c = −(1 + ω + · · · + ω 2020 )3 = −(−ω 2021 )3 = ω 6063 = ω −3 .

So a + b + c ≡ −3 mod k.
If we have a valid filling for k, then we have a valid filling for every prime factor of k. So we
may assume that k is prime and therefore k ∈ {2, 3, 337}.
Assume without loss of generality that the additional cubelet is at the bottom of the cube, i.e.
c = −1. Then a + b ≡ −2 mod k. By symmetry, if we have a valid filling for (a, b, −1), then we
have a valid filling for (2022 − a, b, −1). So we must also have 2022 − a + b ≡ −2 mod k and
so b − a ≡ −2 mod k. Since also a + b ≡ −2 mod k we get a ≡ b ≡ −1 mod k for k ∕= 2 and
a ≡ b mod 2 for k = 2. We will now show that the above necessary conditions are also sufficient
to have a valid filling.
We claim first that a square defined by coordinates (x, y) where 0 " x, y " 2020, with a removed
cell (a, b) satisfying the above restrictions can be covered by 1 × k rectangles. This is because
such a square can be covered by four rectangles of sizes (a + 1) × b, (2020 − a) × (b + 1), (2021 −
a) × (2020 − b) and a × (2021 − b), where each of these rectangles can be covered by 1 × k
rectangles. This follows since k | a + 1, b + 1, 2021 − a, 2021 − b if a ≡ b ≡ −1 mod k and since
2|b, 2020 − a, 2020 − b, a if a ≡ b ≡ 0 mod 2.
Now we fill the cube with the added cubelet as follows: The lowest k − 1 “layers” of the original
cube of side 2021 are filled using the previous method together with a 1 × 1 × k cuboid covering
the holes in these layers and the additional cubelet. The remainder is the 2021×2021×(2022−k)
cuboid which can be easily filled by 1 × 1 × k cuboids because k | 2022 − k.
To complete the solution, we need to count the number of ordered pairs (a, b) with 0 " a, b "
2020, such that a ≡ b mod 2, or a ≡ b ≡ −1 mod 3 or a ≡ b ≡ −1 mod 337. There are 10112
choices with a ≡ b ≡ 0 mod 2 and 10102 choices with a ≡ b ≡ 1 mod 2. If a ≡ b ≡ −1 mod 3
but a ∕≡ b mod 2 then one of a, b must be congruent to 2 mod 6 and the other to 5 mod 6. There
are 2 × 337 × 336 such choices. Finally, if a ≡ b ≡ −1 mod 337 but is not yet accounted for,
Shortlisted Problems with Solutions 23

then one of them is equal to {336, 1010, 1684} and the other to {673, 1347}. (Note that in this
case the second one is definitely not congruent to −1 mod 3.) There are 2 × 3 × 2 such choices.
In total we have 2268697 choices for the pair (a, b). Therefore, because of symmetry, the total
number of ways is 6 × 2268697 = 13612182.

Solution 2. Since there are a total of 20213 + 1 cubelets and each cuboid covers k of them, we
must have k|20213 + 1. We have

20213 = 2022 · (20212 − 2021 + 1) = 2 · 3 · 337 · 3 · 7 · 31 · 6271

as a product of prime factors.

If we have a valid filling for k, then we have a valid filling for every prime factor of k. So we
may assume that k is prime and therefore k ∈ {2, 3, 7, 31, 337}. (The case k = 6271 is easily
seen to be impossible.)
We colour the cubelet at position (x, y, z) for 0 " x, y, z " 2020 by the colour x + y + z mod k.
So every 1 × 1 × k cuboid covers 1 cubelet of each colour.
If k = 2 then it is easy to see that we have one more cubelet of the form 0 mod 2 than of the
form 1 mod 2. So assuming that the additional cubelet is in position (a, b, −1), we must have
a + b ≡ 0 mod 2 as in Solution 1.
If k = 3 then, since it is each to cover all cubelets with 1 × 1 × k cuboids except those of the form
(x, y, z) with 0 " x, y, z " 2, we see that there is one less cubelet of the form 0 mod 3 than of
the form 1, 2 mod 3. So assuming that the additional cubelet is in position (a, b, −1), we must
have a + b ≡ −2 mod 3. Exploiting the symmetry as in Solution 1 we get a ≡ b ≡ −1 mod 3.
If k = 7 then note that (since 7|2016) it is easy to cover all cubelets with 1 × 1 × k cuboids
except those of the form (x, y, z) with 0 " x, y, z " 4. Note that exactly 19 of these cubicles
have the colour 0 mod 7. (3 when z = 0, 3 when z = 1, 4 when z = 2, 5 when z = 3 and 4
3
when z = 4.) These are more than 5 7+1 = 18 so one of these will remain uncovered. So k = 7
is impossible.
If k = 31 then note that (since 31|2015) it is easy to cover all cubelets with 1 × 1 × k cuboids
except those of the form (x, y, z) with 0 " x, y, z " 5. Note that only one of those cubelets has
the colour 0 mod 31. So even if the additional cubelet has the same colour it is still less than
3
the 6 31+1 = 7 which are expected in a proper covering. So k = 31 is impossible.
If k = 337 then note that the square containing all cells of the form (x, y) with 0 " x " 2020
and 0 " y " 2021 can be covered with 1 × k rectangles and so contains equal number of cells
of each colour (thinking of z = 0). In the column with y = 2021, the cells have in order the
colours −1, 0, 1 . . . , −3 mod k. So the colour −2 mod k appears one time less in that column
and therefore one time more in the square of the form (x, y) with 0 " x, y " 2020. In the ‘layer’
above the extra colour is −1 mod k, then 0 mod k and so on until 2020 − 2 ≡ −4 mod k. So in
the original cube all colours appear an equal number of times except −3 mod k which appear
one time less and must be the colour of the additional cubelet (a, b, −1). Thus a+b ≡ −2 mod k.
Exploiting the symmetry as in Solution 1 we get a ≡ b ≡ −1 mod 337.
So we get the same necessary conditions as in Solution 1. The sufficiency of these conditions is
proved in a similar way as in Solution 1.
24 BMO 2022, Cyprus

GEOMETRY

G1. Let ABC be an acute triangle such that CA ∕= CB with circumcircle ω and circumcentre
O. Let τA , τB be the tangents to ω at A and B, which meet at X. Now, let Y be the foot of
the perpendicular from O onto CX, and let the line through C parallel to AB meet τA at Z.
Prove that Y Z bisects AC.
Proposed by ................................

Solution 1. Firstly observe that OAXB is cyclic, with diameter OX, and Y also lies on this
circle since OY ⊥ XC. Hence:
∠AZC = ∠XAB = ∠ABX = ∠AY X
and so CY AZ is cyclic.

Let M be the intersection of Y Z and AC and let CY intersect ω again at W . Using the
new cyclic relation we get ∠CY Z = ∠CAZ and then using that ZA is tangent to ω we get
∠CAZ = ∠CW A, so ∠CY M = ∠CW A. Therefore the triangles CW A and CY M are similar.
But CW is a chord of ω, and Y is the foot of the perpendicular from O, hence Y is the midpoint
of CW . It follows from the similarity relation that M is the midpoint of AC, as required.

Solution 2. Let M be the midpoint of AC. We have ∠CAZ = ∠CBA and ∠ZCA = ∠BAC so
the triangles CAZ and ABC are similar. The line CY X is the C-symmedian of triangle ABC,
and ZM is the corresponding median in triangle CAZ, hence by isogonality ∠AZM = ∠ACY .
So
∠ZM A = 180◦ − ∠AZM − ∠M AZ = 180◦ − ∠ACY − ∠CBA (1)
Shortlisted Problems with Solutions 25

Now observe ∠OM C = ∠OY C = 90◦ , so CM Y O is cyclic. Thus:

1
∠CY M = ∠COM = ∠COA = ∠CBA.
2
This shows that

∠Y M C = 180◦ − ∠M CY − ∠CY M = 180◦ − ∠ACY − ∠CBA

Combining this with (1) we get that ∠Y M C = ∠ZM A and as A, C, M are collinear, it follows
that Z, M, Y are collinear as required.

Solution 3. As in Solution 2 we have that CX is the A-symmedian of triangle ABC and that
triangle ABC is similar to triangle CAZ.
Let f be the spiral similarity which maps AC onto AB and let g be the reflection on the
perpendicular bisector of AB. Note that f is a rotation about A by an angle of ∠CAB (clockwise
in our figure) followed by a homothety centered at A by a factor of AB/AC. By the similarity
of triangles ABC and CAZ we have that g(f (Z)) = C, so actually f (Z) is the other point of
intersection, say C ′ , of CZ with ω.
As in Solution 1 we have that CY AZ is cyclic. Therefore, letting W be the other point of
intersection of CY with ω, we have ∠W AB = ∠W CB = ∠CAY . We also have ∠ACY =
∠ABW . It follows that f (Y ) = W .
Let W ′ = g(W ). Then W ′ ∈ ω and since CW is the A-symmedian, then CW ′ passes through
the midpoint N of AB. Now CW ′ and C ′ W intersect on the perpendicular bisector of AB and
therefore they intersect on N . It follows that N = AB ∩ C ′ W = Af (C) ∩ f (Z)f (Y ) is the image
of M = AC ∩ ZY under f . Since N is the midpoint of AB, then M is the midpoint of AC.
26 BMO 2022, Cyprus

G2. Let ABC be a triangle with AB > AC with incenter I. The internal bisector of angle
BAC intersects the BC at the point D. Let M the midpoint of the segment AD, and let F be
the second intersection point of M B with the circumcircle of the triangle BIC. Prove that AF
is perpendicular to F C.
Proposed by ................................

Solution 1. Let r be the inradius and rA the exradius of triangle ABC. Let also IA be the
A-excenter of triangle ABC. It is well-known that
r DI AI
= = .
rA DIA AIA
Since M is the midpoint of AD we then have
DI AI AM − M I AM + M I
= =⇒ = =⇒ M A2 = M I · M IA .
DIA AIA M IA − AM M IA + AM
It is well-known that the A-excenter IA belongs to the circumcircle of BIC. So by the power
of the point M we also have M I · M IA = M F · M B, therefore M A2 = M F · M B which gives
that M A is tangent to the circumcircle of triangle AF B. Therefore ∠AF M = ∠BAM = Â/2
and so
1 1
∠AF C = ∠AF M + ∠M F C = Â + 180◦ − ∠BF C = Â + 180◦ − ∠BIC
+ 2 , 2
1 1 1 1 & '
= Â + 180◦ − 180◦ − B̂ − Ĉ = Â + B̂ + Ĉ = 90◦ .
2 2 2 2

Therefore AF ⊥ F C as required.

Solution 2. In the triangle CDA the lines CI and CIA are the internal and external angle
bisectors, therefore the quadruple (A, D; I, IA ) is harmonic. Since M is the midpoint of AD it
follows (by Newton’s relation for harmonic quadrilaterals) that M A2 = M I · M IA . The result
now follows as in Solution 1.
Shortlisted Problems with Solutions 27

G3. Let ABC a triangle and let ω be its circumcircle. Let E be the midpoint of the minor arc
BC of ω, and M the midpoint of (BC). Let V be the other point of intersection of AM with ω,
F the point of intersection of AE with BC, X the other point of intersection of the circumcircle
of F EM with ω, X ′ the reflection of V with respect to M , A′ the foot of the perpendicular
from A to BC and S the other point of intrsection of XA′ with ω. If Z ∈ ω with Z ∕= X is
such that AX = AZ, then prove that S, X ′ and Z are collinear.
Proposed by ................................

Solution.
Claim 1. AX is the A-symmedian of △ABC.
Prooof of Claim 1. Let Y ∈ ω such that AY is the A-symmedian of triangle ABC. We want
to prove that Y = X.

We have that ∠BAY = ∠CAM and ∠BY A = ∠BCA = ∠M CA, therefore the triangles ABY
and AM C are similar. It follows that (AY )(AM ) = (AB)(AC).
Since AE is the bisector of ∠BAC, then ∠BAF = ∠CAE. We also have ∠ABF = ∠ABC =
∠AEC, therefore the triangles BAF and EAC are similar. It follows that (AE)(AF ) =
(AB)(AC).
We get (AY )(AM ) = (AE)(AF ) and since also ∠Y AF = ∠EAM , then the triangles Y AF and
EAM are similar. So ∠AF Y = ∠AM E and ∠Y F E = ∠EM V . But as E is the midpoint of
the arc Y V , it follows that ∠EM V = ∠Y M E. So ∠Y F E = ∠Y M E from which it follows that
the quadrilateral Y F M E is cyclic. But since Y ∈ ω, we finally get that Y = X. □
From Claim 1 we conclude that the triangles XBC and V CB are equal. Thus M X = M V =
M X ′ . So the triangle X ′ XV is a right-angled triangle and X ′ X is perpendicular to XV and
therefore also to BC. Thus X ′ is the reflection of X on BC.
Claim 2. The quadrilateral ASA′ M is cyclic.
Proof of Claim 2. We have ∠ASA′ = ∠ASX = ∠ABX But from Claim 1 we also have
∠ABX = ∠AM C. So ∠ASA′ = ∠AM C and the result follows. □
Claim 3. The quadrilateral XSX ′ M is cyclic.
Proof of Claim 3. From Claim 2 we have ∠XSM = ∠A′ SM = ∠A′ AM . Since XX ′ is
parallel to AA′ we have ∠A′ AM = ∠XX ′ M . So ∠XSM = ∠XX ′ M and the result follows. □
28 BMO 2022, Cyprus

Now from Claim 3 we have

∠XSX ′ = ∠XM V = ∠XX ′ M + ∠X ′ XM = 2∠XX ′ M = 2∠AA′ M .

So to conclude the proof it is enough to also show that ∠XSZ = 2∠AA′ M . From Claim 1 we
have ∠ACX = ∠M AB and therefore

∠AZX = ∠ACX = ∠AM B = 90◦ − ∠A′ AM .

Since the triangle XAZ is isosceles, we deduce that

∠XSZ = ∠XAZ = 180◦ − 2∠AZX = 2∠A′ AM

thus completing the proof.

Notes.
1. Claim 1 is Problem 9.2/10.2 from the All Russian Mathematical Olympiad of 2009. There
are various ways to prove this but we only added one proof here.
2. There are various other results which can be helpful towards a proof. These include the
following:
(a) If H is the orthocenter of the triangle ABC, then the quadrilateral A′ M X ′ H is
cyclic.
(b) The points H, M, S are collinear.
(c) The quadrilateral AX ′ HS is inscribed in a circle with diameter AH.
(d) If P is the intersection of AS with BC and K is the intersection of AA′ with SM
then the quadrilateral P SKA′ is cyclic. (In fact K is the orthocenter of the triangle
ABC.)
(e) The quadrilateral P X ′ M X is cyclic.
Shortlisted Problems with Solutions 29

G4. Let ABC be a triangle and let the tangent at B to its circumcircle meet the internal
bisector of angle A at P . The line through P parallel to AC meets AB at Q. Assume that Q
lies in the interior of segment AB and let the line through Q parallel to BC meet AC at X and
P C at Y . Prove that P X is tangent to the circumcircle of triangle XY C.

Proposed by ................................

Solution. Let R be the point on AP such that BR is parallel to AC. Let D, Z, L be the
projections of P on AB, BC, AC respectively and let T, E, M be the analogous projections of
R.

Since BP is tangent to the circumcircle and BR / AC, we have ∠P BZ = ∠BAC = ∠T BR. It

follows that the right-angled triangles RT B and P ZB are similar and therefore PRTZ = PRB
B
.
PD PB
Analogously the triangles REB and P DB are also similar and therefore RE = RB .

Since P, R belong on the bisector of A, we have that P D = P L and RT = RM so from the

PL PZ
results of the previous two paragraphs we get that RE = RM .
The quadrilaterals ZP LC and ERM C are cyclic, therefore ∠ZP L = 180◦ − ∠ECL = ∠ERM .
Together with the previous result we get that the triangles ZP L and M RE are similar. Using
this together with properties of cyclic qudrilaterals and the fact that BC / XY we get that
∠XY C = ∠ZCP = ∠ZLP = ∠M ER = ∠M CR
Since BR / AC / QP and QX / BC we get
AP AQ AX
= =
PR QB XC
which implies that XP / CR. Thus ∠P XC = ∠RCM = ∠XY C. So the result follows.

Comment. Since R belongs on AP , BP is tangent to the circumcircle of ABC, and BR is

parallel to AC, then R is the isogonal conjugate of P . This gives the equality ∠ZCP = ∠M CR
providing a shorter proof of the result.
30 BMO 2022, Cyprus

G5. Let ABC be a triangle with circumcircle ω, circumcenter O, and orthocenter H. Let K
be the midpoint of AH. The perpendicular to OK at K intersects AB and AC at P and Q,
respectively. The lines BK and CK intersect ω again at X and Y , respectively. Prove that the
second intersection of the circumcircles of triangles KP Y and KQX lies on ω.
Proposed by ................................

Solution.
Claim 1. P K = KQ.
Proof of Claim 1. Let L and N be the midpoints of AB and AC, respectively. Since L and
K are midpoints of AB and AH, then LK / BH and so LK ⊥ AC. Since also LO ⊥ AB, then
∠KLO = ∠BAC = α. Also, ∠OLP = 90◦ = ∠OKP , so the quadrilateral OKLP is cyclic
and therefore ∠KP O = ∠KLO = α. Similarly, ∠KQO = α. Therefore, the triangle OP Q is
isosceles, and since OK ⊥ P Q then K is the midpoint of P Q. □

Claim 2. The intersection of Y P and AK lies on ω.

Proof of Claim 2. Let D be the other point of intersection of AK with ω. Since OK ⊥ P Q,
then K is the midpoint of the chord ℓ of ω through P, Q. Since AD and Y C intersect at K, by
the Butterfly theorem the points P ′ = Y D ∩ ℓ and Q = AC ∩ ℓ are equidistant from K. Thus
P ′ = P and Y P ∩ AK = D ∈ ω. □
Now let A′ be the other point of intersection of AO with ω and let S be the other point of
intersection of A′ H with ω.
Claim 3. P Q is the perpendicular bisector of HS.
Proof of Claim 3. We have ∠HSA = ∠A′ SA = 90◦ so S lies on the circle ω ′ with diameter AH
centered at K. So KS = KH. Since O and K are the circumcenters of ω and ω ′ respectively,
and AS is their common chord, then OK ⊥ AS. But we also have HS ⊥ AS and P Q ⊥ OK,
thus HS ⊥ P Q. Since KS = KH, then K belongs on the perpendicular bisector of HS and
the result follows. □
From Claim 3 we have ∠KSP = ∠KHP . From Claim 1 and the fact that KP = KQ we have
that AQP H is a parallelogram and so (using Claim 2 as well)

∠KHP = ∠KAC = ∠DAC = ∠DY C = ∠P Y K .

Shortlisted Problems with Solutions 31

Since ∠KSP = ∠KY P we get that S belongs on the circumcircle of triangle KP Y . Similarly
it belongs to the circumcircle of triangle KQX and therefore the result follows.
Note. We can also define S to be the reflection of H on P Q. Now Claim 3 is immediate. Then
AS / P Q and so OK ⊥ AS and OK / HS. Since K is the midpoint of AH, then OK is the
perpendicular bisector of AS and therefore S ∈ ω.
32 BMO 2022, Cyprus

G6. Let ABC be a triangle with AB < AC and let D be the other intersection point of the
angle bisector of A with the circumcircle of triangle ABC. Let E and F be points on the sides
AB and AC respectively, such that AE = AF and let P be the point of intersection of AD and
EF . Let M be the midpoint of BC. Prove that AM and the circumcircles of triangles AEF
and P M D pass through a common point.
Proposed by ................................

Solution 1. Let X the other point of intersection of the circumcircles of the triangles AEF
and ABC. We have
∠EXF = ∠EAF = ∠BAC = ∠BXC
and
∠XF E = ∠XAB = ∠XCB ,
so the triangles BXC and EXF are similar. Since P is the midpoint of the segment EF , and
M is the the midpoint of the segment BC, we conclude that and the triangles EXP and BXM
are also similar. Therefore, ∠XP E = ∠XM B and so
∠XP D = ∠XP E + 90◦ = ∠XM B + 90◦ = ∠XM D .
Thus the points X, P, M, D are concyclic.

Let Y be the second intersection point of the circumcircle of the triangle AEF and the circle
passing through the points X, P, M, D. We will prove that AM passes through Y . Since
∠AY X = ∠AF X, it is enough to prove that ∠XY M = ∠XF C.
We have
∠XY M = ∠XP M = 180◦ − ∠XDM = 180◦ − (∠BDM − ∠BDX)
1 1
= 180◦ − ∠BDC + ∠BAX = 180◦ − (180◦ − ∠BAC) + ∠EF X
2 2
= 90 + ∠P AF + ∠EF X = 180 − ∠AF X = ∠XF C .
◦ ◦
Shortlisted Problems with Solutions 33

Solution 2. Let Q be the intersection of EF and BC. We have

∠DM Q = ∠DM B = 90◦ = ∠DP E = ∠DP Q

so the quadrrilateral DM P Q is cyclic.

Let X the other point of intersection of the circumcircles of the triangles AEF and ABC.
Consider the spiral similarity f1 which maps BC to EF . Since A = BE ∩ CF , then the center
of f1 is the second intersection point of the circumcircles of triangles ABC and AEF , i.e. it is
the point X. Since M and P are the midpoints of BC and EF , then f1 maps BM to EP . Since
Q = BM ∩ EP , then the center X of f1 is the second intersection point of the circumcircles of
triangles QBE and QM P . Therefore, we conclude that X, P, M, D, Q are concyclic.

Let Y be the second intersection point of the circumcircles of the quadrilaterals (AEF X) and
(P M DX). We will prove that AM passes through Y .
Since spiral similarities come in pairs and f1 maps M C to P F , there exists another spiral
similarity f2 , with the same center X, mapping M P to CF . Therefore, the triangles XM P
and XCF are similar and so ∠XP M = ∠XF C. We now have

∠AY M = ∠AY X + ∠XY M = ∠AF X + ∠XP M = ∠AF X + ∠F XC = 180◦ .

So Y ∈ AM as required.
34 BMO 2022, Cyprus

NUMBER THEORY

N1. Let n be a positive integer. What is the smallest sum of digits of 5n + 6n + 2022n ?
Proposed by ................................

Solution 1. We will prove that the smallest sum is equal to 8. One case when it is achieved is
for n = 1. Suppose that for some n > 1 it is possible to obtain a smaller sum of 8. Observing
the last digit of the number 5n + 6n + 2022n , we can easily conclude that
1
2
2 7 mod 10, if n ≡ 0 mod 4
2
2
33 mod 10, if n ≡ 1 mod 4
5n + 6n + 2022n ≡
2
2 5 mod 10, if n ≡ 2 mod 4
2
2
49 mod 10, if n ≡ 3 mod 4

It follows that n ≡ 1, 2 mod 4. We now consider these two cases.

Case 1: If n = 4k + 1, then
1
2
35 mod 9, if k ≡ 0 mod 3
n n n
5 + 6 + 2022 ≡ 2 mod 9, if k ≡ 1 mod 3
2
4
8 mod 9, if k ≡ 2 mod 3

From here, due to the last digit being equal to 3, it is only possible for the sum of the digits to
be equal to 5. Since 5n + 6n + 2022n ≡ 1 mod 4, the penultimate digit must be equal to 1, and
all other digits (except the first) are equal to 0. So the last digits of 5n + 6n + 2022n are 0013
and therefore 5n + 6n + 2022n ≡ 13 mod 16. On the other hand, since n > 1 and n ≡ 1 mod 4
we have 5n + 6n + 2022n ≡ 5 · 54k ≡ 5 mod 16, a contradiction.
Case 2: If n = 4k + 2, then
1
2
37 mod 9, if k ≡ 0 mod 3
5n + 6n + 2022n ≡ 1 mod 9, if k ≡ 1 mod 3
2
4
4 mod 9, if k ≡ 2 mod 3

Due to the last digit, the only possibility is k ≡ 0 mod 3 so n = 12s+2 for some s ∈ N0 . Now the
sum of the digits is 7, and the last digit is 5. Let’s use the divisibility criterion with 37. (A number
when divided by 37 gives the same remainder as the sum of its three-digit blocks that are formed
from right to left.) Since 6n + 5n + 2022n must be equal to one of 20 · · · 05 or 10 · · · 010 · · · 05,
according to othe above criterion 6n +5n +2022n ≡ 205, 25, 7, 115, 106, 16 mod 37. I.e. congruent
to 20, 25, 7, 4, 32, 16 mod 37.
On the other hand, since it is easy to check that 612 ≡ 1 mod 37, 512 ≡ 10 mod 37 and 202212 ≡
2412 ≡ 10 mod 37 we have that
1
2
38 mod 37, if s ≡ 0 mod 3
n n n 2 2 2 s
5 + 6 + 2022 ≡ 25 · 10 + 36 + 24 · 10 ≡ 36 + 9 · 10 ≡ 15 mod 37, if s ≡ 1 mod 3
2
4
11 mod 37, if s ≡ 2 mod 3

This is a contradiction.
Shortlisted Problems with Solutions 35

Solution 2. Let An = 5n + 6n + 2022n . We have An ≡ 1 mod 4. For n ≡ 1, 2, . . . , 5 mod 5 we

have 6n ≡ 6, 11, 16, 21, 1 mod 25 and for n ≡ 1, 2, . . . , 20 mod 20 we have

2022n ≡ −3, 9, −2, 6, 7, 4, 13, 11, 17, −1, 3, −9, 2, −6, −7, −4, −13, −11, −17, 1 mod 25

Thus for n > 1 and n ≡ 1, 2, . . . , 20 mod 20 we have

An ≡ 3, 20, 14, 27, 8, 10, 24, 27, 38, 0, 9, 2, 18, 15, −6, 2, −2, 5, 4, 2 mod 25

So for n > 1 and n ≡ 1, 2, . . . , 20 mod 20 we have

An ≡ 53, 45, 89, 77, 33, 85, 49, 77, 13, 25, 9, 77, 93, 65, 69, 77, 73, 5, 29, 77 mod 100

The only possibilities for the sum of the digits of An to be less than 8 are n ≡ 5, 9, 18 mod 20
where the last two digits of An are 33, 13, 05 respectively. (The case n ≡ 10 mod 20 is rejected
since then we must have An = 25 which is impossible.)
Now for n > 1 and n ≡ 1, 2, . . . , 6 mod 6 we have An ≡ 5, 7, 8, 4, 2, 1 mod 9. Looking modulo
60, the only possibilities are n ≡ 5, 9, 18, 25, 29, 38, 45, 49, 58 mod 60 and in those cases the the
last two digits of An are 33, 13, 05, 33, 13, 05, 33, 13, 05 respectively and the sum of digits of An
are 2, 8, 1, 5, 2, 7, 8, 5, 4 mod 9 respectively.
So the only possibilites are n ≡ 38, 49 mod 60 where the last two digits of An are 05 and 13
respectively, and the sum of digits of An are 7 and 5 respectively.
The only possibilities are therefore for An to be equal to a number of the form 20 · · · 05 or
10 · · · 010 · · · 05 or 10 · · · 013. In particular, using the alterrnating sum of digits criterion for
divisibility by 11 we have that the first number is congruent to 3, 7 mod 11, the second congruent
to 3, 5, 7 mod 11 and the third congruent to 1, 3 mod 11.
We now look at An mod 11. It can be easily checked that for n ≡ 8 mod 10 we have

An ≡ 4 + 4 + 3 ≡ 0 mod 11

and for n ≡ 9 mod 10 we have

An ≡ 9 + 2 + 5 ≡ 5 mod 11

So all three cases lead to a contradiction.

36 BMO 2022, Cyprus

N2. Let a, b, n be positive integers such that:

(i) a2021 | n and b2021 | n
(ii) 2022 | a − b and a > b.
Prove that there is a subset of the divisors of the number n having sum of elements divisible by
2022 but not by 20222 .
Proposed by ................................

Solution 1. Write a = dr and b = ds where d = gcd(a, b) and (r, s) = 1. Then d2021 r2021 s2021
divides n. Furthermore 2 · 3 · 337 | d(r − s).
Case 1: Assume 337|d. Since (r, s) = 1, we may assume that r is odd. Then

{337r2 , 337r4 , . . . , 337r10 , 337r12 }

works. Indeed each of these six divisors of n is congruent to 1 mod 4 so their sum is a multiple
of 2 but not of 4. If 3 | r then the sum is 0 mod 3 while if 3 ∤ r then each of these divisors is
1 mod 3 so the sum is again 0 mod 3. Therefore the sum is a multiple of 2022 but not of 20222 .
Case 2: Assume 337 ∤ d. Then 337|r − s and since (r, s) = 1 then 337 ∤ rs. Consider the
20222 divisors of n of the form rk sℓ where k, ℓ ∈ {0, 1, 2, . . . , 2021}. Since none of them is a
multiple of 337, they have at most 2 · 3 · 336 distinct remainders modulo 2022. Therefore at
20222
least 2·3·336 > 2022 of them have the same remainder modulo 2022.
Pick 2023 out of those, say d1 , d2 , . . . , d2023 . Let S be their sum. We claim that there is a subset
of 2022 of them that will work. Note that the sum of any such subset is a multiple of 2022. It
is enough to show that there is such a subset whose sum is not divisible by 3372 . If this is not
the case then S − di ≡ 0 mod 3372 for each i = 1, 2, . . . , 2023. In particular, all di are congruent
mod 3372 . Say that di ≡ k mod 3372 for each i. Then 337 ∤ k and so the sum of any 2022 of
them is congruent to 2022k ∕≡ 0 mod 3372 .

Solution 2. We start with the following claim:

Claim. If k is a positive integer, then ak b2021−k | n.
Proof of the Claim. We have that n2021 = nk · n2021−k is divisible by a2021k · b2021(2021−k) and
taking the 2021-root we get the desired result. □
Back to the problem, we will prove that the set T = {ak b2021−k , k ! 0} consisting of 2022
divisors of n, has the desired property. The sum of its elements is equal to
2021
% 2021
%
S= ak b2021−k ≡ a2021 ≡ 0 mod 2022 .
k=0 k=0

−b 2022 2022
On the other hand, the last sum is equal to a a−b . We will prove that this is not divisible
t 1
by 9. Indeed, if 3 || a − b then, since 3 || 2022, by the Lifting the Exponent Lemma, we have
that 3t+1 || a2022 − b2022 . This implies that S is not divisible by 9, therefore, 20222 doesn’t
divide S.
Shortlisted Problems with Solutions 37

N3. For every natural number x, let P (x) be the product of the digits of the number x. Is
there a natural number n such that the numbers P (n) and P (n2 ) are non-zero squares of natural
numbers, where the number of digits of the number n is equal to
(a) 2021
(b) 2022
Proposed by ................................

Solution. The answers are affirmative in both cases.

(a) Take n = 33 · · · 38 68. Then P (n) = (4 · 31010 )2 . Also,
5 67
2019

+ ,2 - .2
2 102021 − 1 102021 + 104
n = + 35 =
3 9
104042 + 208 · 102021 + 10816
=
9
10 4042 − 102021 102021 − 1
= + 209 · + 1225
9 9
= 15 ·67
· · 18 0
5 ·67
· · 08 + 25 ·67
· · 28 00 + 95 ·67
· · 98 + 1225
2021 2021 2021 2021
2021
= 15 ·67
· · 18 33 25 ·67
· · 28 00 + 10 + 1224
2019 2019

= 15 ·67
· · 18 34 25 ·67
· · 28 3424 .
2019 2017

Thus P (n2 ) = (3 · 22012 )2 .

(b) Take n = 11 33 · · · 38. Then P (n) = (31010 )2 . Also,
5 67
2020
- .2
2 34 · 102020 − 1 1156 · 104040 − 68 · 102020 + 1
n = =
9 9
4(10 4040 − 10 2020 ) 102020 − 1
= 128 · 104040 + − 7 · 102020 −
9 9
= 128 05 ·67
· · 08 + 45 ·67 · · 08 − 7 · 102020 − 15 ·67
· · 48 05 ·67 · · 18
4040 2020 2020 2020

= 128 4...4
5678 36 8...8
5678 9 .
2018 2019

Thus P (n2 ) = (9 · 25049 )2 .

5 ·67
Remark. In part (a) we can also take n = 66 · · 668 1 or n = 1 33
5 ·67
· · 338 28.
2020 2018
38 BMO 2022, Cyprus

N4. A hare and a tortoise run in the same direction, at constant but different speeds, around
the base of a tall square tower. They start together at the same vertex, and the run ends when
both return to the initial vertex simultaneously for the first time. Suppose the hare runs with
speed 1, and the tortoise with speed less than 1. For what rational numbers x is it true that, if
the tortoise runs with speed x, the fraction of the entire run for which the tortoise can see the
hare is also x?
Proposed by ................................

Solution. Suppose that x = pq where p, q are positive integers with p < q and gcd(p, q) = 1.
Suppose that the hare takes p minutes for a full turn about the tower. Then the tortoise takes q
minutes for a full turn. They will meet again at the same vertex pq minutes when the hare will
make q full turns and the tortoise will make p full turns. In particular, the hare will overtake
the tortoise exactly k = q − p times taking into account the start of the race but not the end of
the race as an overtake.
(k−1)pq
The overtakes should occur at minutes 0, pq 2pq
k , k ,..., k . In those minutes the tortoise
p 2p (k−1)p
would have made 0, k , k , . . . , k full turns about the tower. Since (p, q) = 1, then (p, k) = 1
and therefore at these meeting points the tortoise would have in some order made some full
turns about the tower plus another 0, k1 , k2 , . . . , k−1
k fraction of a full turn.

Case 1: Suppose k is odd. We claim that the 0, k1 , k2 , . . . , k−1

k fractions of a full turn correspond,
1 2 k−1
in some order to 0, k , k , . . . , k fractions of a side. To see this, given i = 0, 1, . . . , k − 1, note
4 "'
that&if j−1 i j
k < 4 for some j = 1, 2, 3, 4 then the meeting point is on the j-th side at a fraction
i j−1 4i−k(j−1)
of 4 k − 4 = k of the side. No two such fractions can be equal. Indeed if

4i − k(j − 1) 4i′ − k(j ′ − 1)

=
k k

then 4(i′ − i) = k(j ′ − j) and since (for i′ > i say) j ′ − j ∈ {1, 2, 3}, then 2|k, a contradiction.
Now if the hare meets the tortoise at a fraction of ki of the side, then the tortoise can see
p
the hare for k−i
k · 4 minutes. I.e. the time it takes the hare to reach the endpoint of the side.
Furthermore, if i is large enough, it is possible for the tortoise to also reach the endpoint before
the hare reaches the next endpoint and thus see the hare for a little bit more. The tortoise
q 2k−i p
takes k−i
k · 4 minutes to reach the endpoint. The hare takes k · 4 minutes in total to reach
the next endpoint. So the tortoise can see the hare for another

(2k − i)p − q(k − i) p (p − q)(k − i) p+i−k

= + =
4k 4 4k 4
minutes, provided that this is non-negative. So the total meeting time is
+ ,
p 1 2 k 1 p(k + 1) (p − 1)p pq
+ + ··· + + (1 + 2 + · · · + (p − 1)) = + =
4 k k k 4 8 8 8
1
minutes. So we need x = 8 which is accepted as k = 7 is odd in this case.

Case 2: Suppose k = 2r where r is odd. We claim that the 0, k1 , k2 , . . . , k−1 k fractions of a full
turn correspond, in some order to 0, 0, 1r , 1r , . . . , r−1
r , r−1
r fractions of a side. The proof is similar
4i−k(j−i) 2i−r(j−i)
to Case 1 with the meeting points being at fractions k = r of the sides. Two of
′ ′ ′
these fractions are equal if and only if 4(i − i) = k(j − j) which (for i > i say) can occur when
j ′ = j + 2 and i′ = i + r.
Shortlisted Problems with Solutions 39

i r−i p
If they meet at a fraction of r of the side, the tortoise meets that hare for r · 4 minutes plus
possibly another
(2r − i)p − q(r − i) p (p − q)(r − i) p + 2i − 2r
= + =
4r 4 4r 4
minutes provided this is non-negative. So (noting that p is odd in this case) the tortoise can
see the hare for
+ ,
2p 1 2 r 2 p(r + 1) (p − 1)2
+ + ··· + + (1 + 3 + · · · + (p − 2)) = +
4 r r r 4 4 8
minutes. This is equal to

p(2r + 2) + (p − 1)2 p(q − p + 2) + (p − 1)2 pq + 1

= =
8 8 8
minutes. So we need
p 1 1
=x= + =⇒ 8p2 = pq + 1 =⇒ p = 1, q = 7 .
q 8 8pq
1
Thus x = 7 which is accepted since k = 6 ≡ 2 mod 4.
Case 3: Suppose k = 4s. Similarly to Cases 1 and 2, the 0, k1 , k2 , . . . , k−1 k fractions of a full turn
correspond, in some order to 0, 0, 0, 0, 1s , 1s , 1s , 1s , . . . , s−1
s , s−1 s−1 s−1
s , s , s fractions of a side.
i s−i p
If they meet at a fraction of s of the side, the tortoise meets that hare for s · 4 minutes plus
possibly another
(2s − i)p − q(s − i) p (p − q)(s − i) p + 4i − 4r
= + =
4r 4 4s 4
minutes provided this is non-negative. Noting that p is odd in this case, if p ≡ 1 mod 4 this is
equal to
+ ,
1 2 s p(s + 1) (p − 3)(p − 1)
p + + ··· + + (1 + 5 + · · · + (p − 4)) = +
s s s 2 8
p(q − p + 4) + (p − 3)(p − 1) pq + 3
= =
8 8
minutes, while if p ≡ 3 mod 4 this is equal to
+ ,
1 2 s p(s + 1) (p − 1)(p − 3) pq + 3
p + + ··· + + (3 + 7 + · · · + (p − 4)) = + =
s s s 2 8 8
minutes as well. So we need
p 1 3
=x= + =⇒ 8p2 = pq + 3 =⇒ p|3
q 8 8pq
1 3
This gives the solutions p = 1, q = 5 and p = 3, q = 23 giving x = 5 and x = 23 which are both
accepted.

Solution 2. If we run the process in reverse, the dynamics are the same except that the toirtoise
can see the hare at some time in the reversed process precisely if the hare could see the tortoise
at the same time in the original process. From this observation, the proportion of the race for
which the tortoise can see the hare is precisely half the proportion of the race for which the two
runners are on the same side of the square. It suffices to show that this proportion is:
40 BMO 2022, Cyprus

1
(a) 4, when p − q is odd;
1 1
(b) 4 + 4pq when p − q is even but not divisible by 4;
1 3
(c) 4 + 4pq when 4 | p − q.

The proof can then be completed exactly as in Solution 1 to get that x = 18 , 17 , 15 , 23

3
.
To streamline the argument, we assume that the square (always meaning the boundary) has
side length pq units, and that in a time-step, the tortoise moves p units, and the hare moves
q units. Note that a runner can only be at the vertex of the square at the start or end of a
step. We say that a vertex of the square is on the side of the square that lies clockwise from
the vertex, and we refer to that as the side’s associated vertex. So every point on the square is
on exactly one ‘side’.
Now, we index all points on the square by their distance from the vertex associated to the side
containing that point. So each label occurs exactly four times. So, after n steps of the process,
we study the indices of T and H’s current locations, which must have the form (ap, bq) for
a ∈ {0, 1, . . . , q − 1} and b ∈ {0, 1, . . . , p − 1}. Thus the total distances travelled by T and H
have the forms
ap + mpq, bq + m′ pq, respectively, m, m′ ∈ N
which means that the number of steps n satisfies

n = a + mq = b + m′ p . (1)

T and H are on the same side of the square precisely when 4 | m′ − m and are on the same side
or on opposite sides of the square precisely when 2 | m′ − m, equivalently when 2 | m′ + m.
Now, after pq steps, both runners are again at a vertex of the square. We return to the case
distinction introduced earlier.
(a) Here, the two vertices are adjacent. Therefore, for any time 0 " t < pq, T and H are
on the same side of the square at exactly one of the times {t, t + pq, t + 2pq, t + 3pq}. It
follows that across the entire run, T and H will be on the same side exactly 14 of the time.
(c) Here, the two vertices are the same. It then suffices to study the proportion of times the
runners are on the same side before timestep pq. Note that by the Chinese Remainder
Theorem, every (a, b) ∈ [0, q − 1] × [0, p − 1] occurs exactly once as the indexing of the
runners’ locations (ap, bq) for n = 0, . . . , pq − 1. But, from (1),

a − b = m′ p − mq ≡ (m′ − m)p mod 4.

Since p is odd, 4 | m′ − m precisely if 4 | a − b. So it suffices to enumerate

09 :0
0 0
K(p, q) := 0 (a, b) ∈ [0, q − 1] × [0, p − 1] : 4 | a − b 0 .

By considering the number of times each congruence class appears for a and for b, we find,
for p ≡ q ≡ 1: + ,
p+3 q+3 p−1 q−1
K(p, q) = × +3 × ,
4 4 4 4
and for p ≡ 1, q ≡ 3,
+ ,
p+3 q+1 p−1 q+1 p−1 q−3
K(p, q) = × +2 × + × .
4 4 4 4 4 4

K(p,q) 1 3
In both cases, a calculation shows pq = 4 + 4pq , with an obvious symmetric argument
for p ≡ 3, q ≡ 1.
Shortlisted Problems with Solutions 41

(b) We combine aspects of the two previous cases. Here, the two vertices are opposite. There-
fore, for any time 0 " t < pq, T and H are on the same side or on opposite sides of the
square at time t iff they are on the same side or on opposite sides of the square at time
t + pq. Furthermore, on this event, they are on the same side at precisely one of times
{t, t + pq}.
So we calculate the proportion of times the runners are on the same side or opposite sides
before timestep pq. Again from (1), using p ≡ −q modulo 4,

a − b ≡ m′ p − mq ≡ (m′ + m)p mod 4 .

Since p is odd, 2 | m′ + m precisely if 2 | a − b. We enumerate

09 :0
0 0
L(p, q) : = 0 (a, b) ∈ [0, q − 1] × [0, p − 1] : 2 | a − b 0
p+1 q+1 p−1 q−1
= × + × .
2 2 2 2
L(p,q) 1 1
So 2pq = 4 + 4pq as required.
36 102
2003
+357 − 22378101 +357 − 22379122