Algebra Problem shortlist 52nd IMO 2011

Algebra
A1
A1
For any set A = {a1 , a2 , a3 , a4 } of four distinct positive integers with sum sA = a1 + a2 + a3 + a4 ,
let pA denote the number of pairs (i, j) with 1 ≤ i < j ≤ 4 for which ai + aj divides sA . Among
all sets of four distinct positive integers, determine those sets A for which pA is maximal.

A2
A2
Determine all sequences (x1 , x2 , . . . , x2011 ) of positive integers such that for every positive inte-
ger n there is an integer a with

xn1 + 2xn2 +    + 2011xn2011 = an+1 + 1.

A3
A3
Determine all pairs (f, g) of functions from the set of real numbers to itself that satisfy

g(f (x + y)) = f (x) + (2x + y)g(y)

for all real numbers x and y.

A4
A4
Determine all pairs (f, g) of functions from the set of positive integers to itself that satisfy

f g(n)+1 (n) + g f (n) (n) = f (n + 1) − g(n + 1) + 1

for every positive integer n. Here, f k (n) means f (f (. . . f (n) . . .)).

  
k

A5
A5
Prove that for every positive integer n, the set {2, 3, 4, . . . , 3n + 1} can be partitioned into
n triples in such a way that the numbers from each triple are the lengths of the sides of some
obtuse triangle.

4
52nd IMO 2011 Problem shortlist Algebra

A6
A6
Let f be a function from the set of real numbers to itself that satises

f (x + y) ≤ yf (x) + f (f (x))

for all real numbers x and y. Prove that f (x) = 0 for all x ≤ 0.

A7
A7
√
Let a, b, and c be positive real numbers satisfying min(a+b, b+c, c+a) > 2 and a2 +b2 +c2 = 3.
Prove that

a b c 3
2
+ 2
+ 2
≥ .
(b + c − a) (c + a − b) (a + b − c) (abc)2

5
 Combinatorics Problem shortlist 52nd IMO 2011

Combinatorics
C1
C1
Let n > 0 be an integer. We are given a balance and n weights of weight 20 , 21 , . . . , 2n−1 . In a
sequence of n moves we place all weights on the balance. In the rst move we choose a weight
and put it on the left pan. In each of the following moves we choose one of the remaining
weights and we add it either to the left or to the right pan. Compute the number of ways in
which we can perform these n moves in such a way that the right pan is never heavier than the
left pan.

C2
C2
Suppose that 1000 students are standing in a circle. Prove that there exists an integer k with
100 ≤ k ≤ 300 such that in this circle there exists a contiguous group of 2k students, for which
the rst half contains the same number of girls as the second half.

C3
C3
Let S be a nite set of at least two points in the plane. Assume that no three points of S are
collinear. By a windmill we mean a process as follows. Start with a line ℓ going through a
point P ∈ S. Rotate ℓ clockwise around the pivot P until the line contains another point Q
of S. The point Q now takes over as the new pivot. This process continues indenitely, with
the pivot always being a point from S.
Show that for a suitable P ∈ S and a suitable starting line ℓ containing P , the resulting
windmill will visit each point of S as a pivot innitely often.

C4
C4
Determine the greatest positive integer k that satises the following property: The set of positive
integers can be partitioned into k subsets A1 , A2 , . . . , Ak such that for all integers n ≥ 15 and
all i ∈ {1, 2, . . . , k} there exist two distinct elements of Ai whose sum is n.

6
52nd IMO 2011 Problem shortlist Combinatorics

C5
C5
Let m be a positive integer and consider a checkerboard consisting of m by m unit squares.
At the midpoints of some of these unit squares there is an ant. At time 0, each ant starts
moving with speed 1 parallel to some edge of the checkerboard. When two ants moving in
opposite directions meet, they both turn 90◦ clockwise and continue moving with speed 1.
When more than two ants meet, or when two ants moving in perpendicular directions meet,
the ants continue moving in the same direction as before they met. When an ant reaches one
of the edges of the checkerboard, it falls o and will not re-appear.
Considering all possible starting positions, determine the latest possible moment at which the
last ant falls o the checkerboard or prove that such a moment does not necessarily exist.

C6
C6
Let n be a positive integer and let W = . . . x−1 x0 x1 x2 . . . be an innite periodic word consisting
of the letters a and b. Suppose that the minimal period N of W is greater than 2n .
A nite nonempty word U is said to appear in W if there exist indices k ≤ ℓ such that
U = xk xk+1 . . . xℓ . A nite word U is called ubiquitous if the four words U a, U b, aU , and bU
all appear in W . Prove that there are at least n ubiquitous nite nonempty words.

C7
C7
On a square table of 2011 by 2011 cells we place a nite number of napkins that each cover
a square of 52 by 52 cells. In each cell we write the number of napkins covering it, and we
record the maximal number k of cells that all contain the same nonzero number. Considering
all possible napkin congurations, what is the largest value of k?

7
 Geometry Problem shortlist 52nd IMO 2011

Geometry
G1
G1
Let ABC be an acute triangle. Let ω be a circle whose center L lies on the side BC. Suppose
that ω is tangent to AB at B ′ and to AC at C ′ . Suppose also that the circumcenter O of the
triangle ABC lies on the shorter arc B ′ C ′ of ω. Prove that the circumcircle of ABC and ω
meet at two points.

G2
G2
Let A1 A2 A3 A4 be a non-cyclic quadrilateral. Let O1 and r1 be the circumcenter and the
circumradius of the triangle A2 A3 A4 . Dene O2 , O3 , O4 and r2 , r3 , r4 in a similar way. Prove
that
1 1 1 1
+ + + = 0.
O1 A1 − r1 O2 A2 − r2 O3 A3 − r3 O4 A4 − r42
2 2 2 2 2 2 2

G3
G3
Let ABCD be a convex quadrilateral whose sides AD and BC are not parallel. Suppose that the
circles with diameters AB and CD meet at points E and F inside the quadrilateral. Let ωE be
the circle through the feet of the perpendiculars from E to the lines AB, BC, and CD. Let ωF
be the circle through the feet of the perpendiculars from F to the lines CD, DA, and AB.
Prove that the midpoint of the segment EF lies on the line through the two intersection points
of ωE and ωF .

G4
G4
Let ABC be an acute triangle with circumcircle Ω. Let B0 be the midpoint of AC and let C0
be the midpoint of AB. Let D be the foot of the altitude from A, and let G be the centroid
of the triangle ABC. Let ω be a circle through B0 and C0 that is tangent to the circle Ω at a
point X = A. Prove that the points D, G, and X are collinear.

G5
G5
Let ABC be a triangle with incenter I and circumcircle ω. Let D and E be the second
intersection points of ω with the lines AI and BI, respectively. The chord DE meets AC at a
point F , and BC at a point G. Let P be the intersection point of the line through F parallel to
AD and the line through G parallel to BE. Suppose that the tangents to ω at A and at B meet
at a point K. Prove that the three lines AE, BD, and KP are either parallel or concurrent.

8
52nd IMO 2011 Problem shortlist Geometry

G6
G6
Let ABC be a triangle with AB = AC, and let D be the midpoint of AC. The angle bisector
of ∠BAC intersects the circle through D, B, and C in a point E inside the triangle ABC.
The line BD intersects the circle through A, E, and B in two points B and F . The lines AF
and BE meet at a point I, and the lines CI and BD meet at a point K. Show that I is the
incenter of triangle KAB.

G7
G7
Let ABCDEF be a convex hexagon all of whose sides are tangent to a circle ω with center O.
Suppose that the circumcircle of triangle ACE is concentric with ω. Let J be the foot of the
perpendicular from B to CD. Suppose that the perpendicular from B to DF intersects the
line EO at a point K. Let L be the foot of the perpendicular from K to DE. Prove that
DJ = DL.

G8
G8
Let ABC be an acute triangle with circumcircle ω. Let t be a tangent line to ω. Let ta , tb ,
and tc be the lines obtained by reecting t in the lines BC, CA, and AB, respectively. Show
that the circumcircle of the triangle determined by the lines ta , tb , and tc is tangent to the
circle ω.

9
 Number Theory Problem shortlist 52nd IMO 2011

Number Theory
N1
N1
For any integer d > 0, let f (d) be the smallest positive integer that has exactly d positive
divisors (so for example we have f (1) = 1, f (5) = 16, and f (6) = 12). Prove that for every
integer k ≥ 0 the number f (2k ) divides f (2k+1).

N2
N2
Consider a polynomial P (x) = (x + d1 )(x + d2 )  . . .  (x + d9 ), where d1 , d2 , . . . , d9 are nine
distinct integers. Prove that there exists an integer N such that for all integers x ≥ N the
number P (x) is divisible by a prime number greater than 20.

N3
N3
Let n ≥ 1 be an odd integer. Determine all functions f from the set of integers to itself such
that for all integers x and y the dierence f (x) − f (y) divides xn − y n .

N4
N4
For each positive integer k, let t(k) be the largest odd divisor of k. Determine all positive
integers a for which there exists a positive integer n such that all the dierences

t(n + a) − t(n), t(n + a + 1) − t(n + 1), ..., t(n + 2a − 1) − t(n + a − 1)

are divisible by 4.

N5
N5
Let f be a function from the set of integers to the set of positive integers. Suppose that for
any two integers m and n, the dierence f (m) − f (n) is divisible by f (m − n). Prove that for
all integers m, n with f (m) ≤ f (n) the number f (n) is divisible by f (m).

N6
N6
Let P (x) and Q(x) be two polynomials with integer coecients such that no nonconstant
polynomial with rational coecients divides both P (x) and Q(x). Suppose that for every
positive integer n the integers P (n) and Q(n) are positive, and 2Q(n) − 1 divides 3P (n) − 1.
Prove that Q(x) is a constant polynomial.

10
52nd IMO 2011 Problem shortlist Number Theory

N7
N7
Let p be an odd prime number. For every integer a, dene the number

a a2 ap−1
Sa = + ++ .
1 2 p−1

Let m and n be integers such that

m
S3 + S4 − 3S2 = .
n
Prove that p divides m.

N8
N8
Let k be a positive integer and set n = 2k + 1. Prove that n is a prime number if and only if
the following holds: there is a permutation a1 , . . . , an−1 of the numbers 1, 2, . . . , n − 1 and a
sequence of integers g1 , g2 , . . . , gn−1 such that n divides giai − ai+1 for every i ∈ {1, 2, . . . , n − 1},
where we set an = a1 .

11
4

Algebra
A1. Find all the functions f : Z → Z such that
f (a)2 + f (b)2 + f (c)2 = 2f (a)f (b) + 2f (b)f (c) + 2f (c)f (a)

for all integers a, b, c satisfying a + b + c = 0.

A2. Let Z and Q be the sets of integers and rationals respectively.

a) Does there exist a partition of Z into three non-empty subsets A, B, C such that the sets
A + B, B + C, C + A are disjoint?

b) Does there exist a partition of Q into three non-empty subsets A, B, C such that the sets
A + B, B + C, C + A are disjoint?

Here X + Y denotes the set {x + y | x ∈ X, y ∈ Y }, for X, Y ⊆ Z and X, Y ⊆ Q.

A3. Let a2 , . . . , an be n − 1 positive real numbers, where n ≥ 3, such that a2 a3 · · · an = 1.

Prove that
(1 + a2 )2 (1 + a3 )3 · · · (1 + an )n > nn .

A4. Let f and g be two nonzero polynomials with integer coecients and deg f > deg g.
Suppose that for innitely many primes p the polynomial pf + g has a rational root. Prove
that f has a rational root.

A5. Find all functions f : R → R that satisfy the conditions

f (1 + xy) − f (x + y) = f (x)f (y) for all x, y ∈ R

and f (−1) = 0.

A6. Let f : N → N be a function, and let f m be f applied m times. Suppose that for
every n ∈ N there exists a k ∈ N such that f 2k (n) = n + k, and let kn be the smallest such k.
Prove that the sequence k1 , k2 , . . . is unbounded.

A7. We say that a function f : Rk → R is a metapolynomial if, for some positive integers m
and n, it can be represented in the form

f (x1 , . . . , xk ) = max min Pi,j (x1 , . . . , xk )

i=1,...,m j=1,...,n

where Pi,j are multivariate polynomials. Prove that the product of two metapolynomials is also
a metapolynomial.
 5

Combinatorics
C1. Several positive integers are written in a row. Iteratively, Alice chooses two adjacent
numbers x and y such that x > y and x is to the left of y, and replaces the pair (x, y) by either
(y + 1, x) or (x − 1, x). Prove that she can perform only nitely many such iterations.

C2. Let n ≥ 1 be an integer. What is the maximum number of disjoint pairs of elements of the
set {1, 2, . . . , n} such that the sums of the dierent pairs are dierent integers not exceeding n?

C3. In a 999 × 999 square table some cells are white and the remaining ones are red. Let T
be the number of triples (C1 , C2 , C3) of cells, the rst two in the same row and the last two in
the same column, with C1 and C3 white and C2 red. Find the maximum value T can attain.

C4. Players A and B play a game with N ≥ 2012 coins and 2012 boxes arranged around a
circle. Initially A distributes the coins among the boxes so that there is at least 1 coin in each
box. Then the two of them make moves in the order B, A, B, A, . . . by the following rules:

• On every move of his B passes 1 coin from every box to an adjacent box.

• On every move of hers A chooses several coins that were not involved in B’s previous
move and are in dierent boxes. She passes every chosen coin to an adjacent box.

Player A’s goal is to ensure at least 1 coin in each box after every move of hers, regardless of
how B plays and how many moves are made. Find the least N that enables her to succeed.

C5. The columns and the rows of a 3n × 3n square board are numbered 1, 2, . . . , 3n. Every
square (x, y) with 1 ≤ x, y ≤ 3n is colored asparagus, byzantium or citrine according as the
modulo 3 remainder of x + y is 0, 1 or 2 respectively. One token colored asparagus, byzantium
or citrine is placed on each square, so that there are 3n2 tokens of each color.
Suppose that one can permute the tokens so that each token is moved to a distance of
at most d from its original position, each asparagus token replaces a byzantium token, each
byzantium token replaces a citrine token, and each citrine token replaces an asparagus token.
Prove that it is possible to permute the tokens so that each token is moved to a distance of at
most d + 2 from its original position, and each square contains a token with the same color as
the square.

C6. Let k and n be xed positive integers. In the liar’s guessing game, Amy chooses integers
x and N with 1 ≤ x ≤ N . She tells Ben what N is, but not what x is. Ben may then repeatedly
ask Amy whether x ∈ S for arbitrary sets S of integers. Amy will always answer with yes or no,
but she might lie. The only restriction is that she can lie at most k times in a row. After he
has asked as many questions as he wants, Ben must specify a set of at most n positive integers.
If x is in this set he wins; otherwise, he loses. Prove that:

a) If n ≥ 2k then Ben can always win.

b) For suciently large k there exist n ≥ 1.99k such that Ben cannot guarantee a win.

C7. There are given 2500 points on a circle labeled 1, 2, . . . , 2500 in some order. Prove that
one can choose 100 pairwise disjoint chords joining some of these points so that the 100 sums
of the pairs of numbers at the endpoints of the chosen chords are equal.
6

Geometry
G1. In the triangle ABC the point J is the center of the excircle opposite to A. This excircle
is tangent to the side BC at M, and to the lines AB and AC at K and L respectively. The
lines LM and BJ meet at F , and the lines KM and CJ meet at G. Let S be the point of
intersection of the lines AF and BC, and let T be the point of intersection of the lines AG
and BC. Prove that M is the midpoint of ST .

G2. Let ABCD be a cyclic quadrilateral whose diagonals AC and BD meet at E. The
extensions of the sides AD and BC beyond A and B meet at F . Let G be the point such that
ECGD is a parallelogram, and let H be the image of E under reection in AD. Prove that
D, H, F , G are concyclic.

G3. In an acute triangle ABC the points D, E and F are the feet of the altitudes through A,
B and C respectively. The incenters of the triangles AEF and BDF are I1 and I2 respectively;
the circumcenters of the triangles ACI1 and BCI2 are O1 and O2 respectively. Prove that I1 I2
and O1 O2 are parallel.

G4. Let ABC be a triangle with AB = AC and circumcenter O. The bisector of ∠BAC
intersects BC at D. Let E be the reection of D with respect to the midpoint of BC. The lines
through D and E perpendicular to BC intersect the lines AO and AD at X and Y respectively.
Prove that the quadrilateral BXCY is cyclic.

G5. Let ABC be a triangle with ∠BCA = 90◦ , and let C0 be the foot of the altitude
from C. Choose a point X in the interior of the segment CC0 , and let K, L be the points on
the segments AX, BX for which BK = BC and AL = AC respectively. Denote by M the
intersection of AL and BK. Show that MK = ML.

G6. Let ABC be a triangle with circumcenter O and incenter I. The points D, E and F on
the sides BC, CA and AB respectively are such that BD + BF = CA and CD + CE = AB.
The circumcircles of the triangles BF D and CDE intersect at P = D. Prove that OP = OI.

G7. Let ABCD be a convex quadrilateral with non-parallel sides BC and AD. Assume
that there is a point E on the side BC such that the quadrilaterals ABED and AECD are
circumscribed. Prove that there is a point F on the side AD such that the quadrilaterals
ABCF and BCDF are circumscribed if and only if AB is parallel to CD.

G8. Let ABC be a triangle with circumcircle ω and ℓ a line without common points with ω.
Denote by P the foot of the perpendicular from the center of ω to ℓ. The side-lines BC, CA, AB
intersect ℓ at the points X, Y, Z dierent from P . Prove that the circumcircles of the triangles
AXP, BY P and CZP have a common point dierent from P or are mutually tangent at P .
 7

Number Theory
N1. Call admissible a set A of integers that has the following property:
If x, y ∈ A (possibly x = y) then x2 + kxy + y 2 ∈ A for every integer k.

Determine all pairs m, n of nonzero integers such that the only admissible set containing both m
and n is the set of all integers.

N2. Find all triples (x, y, z) of positive integers such that x ≤ y ≤ z and
x3 (y 3 + z 3 ) = 2012(xyz + 2).

m m
N3. Determine
 all integers m ≥ 2 such that every n with 3
≤n≤ 2
divides the binomial
n

coecient m−2n
.

N4. An integer a is called friendly if the equation (m2 + n)(n2 + m) = a(m − n)3 has a
solution over the positive integers.

a) Prove that there are at least 500 friendly integers in the set {1, 2, . . . , 2012}.

b) Decide whether a = 2 is friendly.

N5. For a nonnegative integer n dene rad(n) = 1 if n = 0 or n = 1, and rad(n) = p1 p2 · · · pk

where p1 < p2 < · · · < pk are all prime factors of n. Find all polynomials f (x) with nonnegative
integer coecients such that rad(f (n)) divides rad(f (nrad(n) )) for every nonnegative integer n.
n
N6. Let x and y be positive integers. If x2 − 1 is divisible by 2n y + 1 for every positive
integer n, prove that x = 1.

N7. Find all n ∈ N for which there exist nonnegative integers a1 , a2 , . . . , an such that
1 1 1 1 2 n
a
+ a
+ · · · + a
= a
+ a
+ · · · + = 1.
21 22 2n 31 32 3an

N8. Prove that for every prime p > 100 and every integer r there exist two integers a and b
such that p divides a2 + b5 − r.
Shortlisted problems 3

Problems
Algebra
A1. Let n be a positive integer and let a1 , . . . , an´1 be arbitrary real numbers. Dene the
sequences u0 , . . . , un and v0 , . . . , vn inductively by u0 “ u1 “ v0 “ v1 “ 1, and
uk`1 “ uk ` ak uk´1 , vk`1 “ vk ` an´k vk´1 for k “ 1, . . . , n ´ 1.
Prove that un “ vn .
(France)
A2. Prove that in any set of 2000 distinct real numbers there exist two pairs a ą b and c ą d
with a ‰ c or b ‰ d, such that ˇ ˇ
ˇa ´ b ˇ 1
ˇ c ´ d ´ 1ˇ ă 100000 .
ˇ ˇ

(Lithuania)
A3. Let Qą0 be the set of positive rational numbers. Let f : Qą0 Ñ R be a function satisfying
the conditions
f pxqf pyq ě f pxyq and f px ` yq ě f pxq ` f pyq
for all x, y P Qą0 . Given that f paq “ a for some rational a ą 1, prove that f pxq “ x for all
x P Qą0 .
(Bulgaria)
A4. Let n be a positive integer, and consider a sequence a1 , a2 , . . . , an of positive integers.
Extend it periodically to an innite sequence a1 , a2 , . . . by dening an`i “ ai for all i ě 1. If
a1 ď a2 ď ¨ ¨ ¨ ď an ď a1 ` n
and
aai ď n ` i ´ 1 for i “ 1, 2, . . . , n,
prove that
a1 ` ¨ ¨ ¨ ` an ď n2 .

(Germany)
A5. Let Zě0 be the set of all nonnegative integers. Find all the functions f : Zě0 Ñ Zě0
satisfying the relation
f pf pf pnqqq “ f pn ` 1q ` 1
for all n P Zě0 .
(Serbia)
A6. Let m ‰ 0 be an integer. Find all polynomials P pxq with real coecients such that
px3 ´ mx2 ` 1qP px ` 1q ` px3 ` mx2 ` 1qP px ´ 1q “ 2px3 ´ mx ` 1qP pxq
for all real numbers x.
(Serbia)
4 IMO 2013 Colombia

Combinatorics
C1. Let n be a positive integer. Find the smallest integer k with the following property: Given
any real numbers a1 , . . . , ad such that a1 ` a2 ` ¨ ¨ ¨ ` ad “ n and 0 ď ai ď 1 for i “ 1, 2, . . . , d, it
is possible to partition these numbers into k groups (some of which may be empty) such that the
sum of the numbers in each group is at most 1.
(Poland)
C2. In the plane, 2013 red points and 2014 blue points are marked so that no three of the
marked points are collinear. One needs to draw k lines not passing through the marked points and
dividing the plane into several regions. The goal is to do it in such a way that no region contains
points of both colors.
Find the minimal value of k such that the goal is attainable for every possible conguration of
4027 points.
(Australia)
C3. A crazy physicist discovered a new kind of particle which he called an imon, after some of
them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each
imon can participate in many entanglement relations. The physicist has found a way to perform
the following two kinds of operations with these particles, one operation at a time.

piq If some imon is entangled with an odd number of other imons in the lab, then the physicist
can destroy it.

piiq At any moment, he may double the whole family of imons in his lab by creating a copy I 1
of each imon I. During this procedure, the two copies I 1 and J 1 become entangled if and only if
the original imons I and J are entangled, and each copy I 1 becomes entangled with its original
imon I; no other entanglements occur or disappear at this moment.

Prove that the physicist may apply a sequence of such operations resulting in a family of imons,
no two of which are entangled.
(Japan)
C4. Let n be a positive integer, and let A be a subset of t1, . . . , nu. An A-partition of n into k
parts is a representation of n as a sum n “ a1 ` ¨ ¨ ¨ ` ak , where the parts a1 , . . . , ak belong to A
and are not necessarily distinct. The number of dierent parts in such a partition is the number
of (distinct) elements in the set ta1 , a2 , . . . , ak u.
We say that an A-partition of n into k parts is optimal if there is no A-partition
? of n into r
3
parts with r ă k. Prove that any optimal A-partition of n contains at most 6n dierent parts.
(Germany)
C5. Let r be a positive integer, and let a0 , a1 , . . . be an innite sequence of real numbers.
Assume that for all nonnegative integers m and s there exists a positive integer n P rm ` 1, m ` rs
such that
am ` am`1 ` ¨ ¨ ¨ ` am`s “ an ` an`1 ` ¨ ¨ ¨ ` an`s .

Prove that the sequence is periodic, i. e. there exists some p ě 1 such that an`p “ an for all n ě 0.
(India)
Shortlisted problems 5

C6. In some country several pairs of cities are connected by direct two-way ights. It is possible
to go from any city to any other by a sequence of ights. The distance between two cities is dened
to be the least possible number of ights required to go from one of them to the other. It is known
that for any city there are at most 100 cities at distance exactly three from it. Prove that there is
no city such that more than 2550 other cities have distance exactly four from it.
(Russia)
C7. Let n ě 2 be an integer. Consider all circular arrangements of the numbers 0, 1, . . . , n; the
n ` 1 rotations of an arrangement are considered to be equal. A circular arrangement is called
beautiful if, for any four distinct numbers 0 ď a, b, c, d ď n with a ` c “ b ` d, the chord joining
numbers a and c does not intersect the chord joining numbers b and d.
Let M be the number of beautiful arrangements of 0, 1, . . . , n. Let N be the number of pairs
px, yq of positive integers such that x ` y ď n and gcdpx, yq “ 1. Prove that

M “ N ` 1.

(Russia)
C8. Players A and B play a paintful game on the real line. Player A has a pot of paint with
four units of black ink. A quantity p of this ink suces to blacken a (closed) real interval of length
p. In every round, player A picks some positive integer m and provides 1{2m units of ink from the
pot. Player B then picks an integer k and blackens the interval from k{2m to pk ` 1q{2m (some
parts of this interval may have been blackened before). The goal of player A is to reach a situation
where the pot is empty and the interval r0, 1s is not completely blackened.
Decide whether there exists a strategy for player A to win in a nite number of moves.
(Austria)
6 IMO 2013 Colombia

Geometry
G1. Let ABC be an acute-angled triangle with orthocenter H, and let W be a point on
side BC. Denote by M and N the feet of the altitudes from B and C, respectively. Denote
by ω1 the circumcircle of BW N , and let X be the point on ω1 which is diametrically opposite
to W . Analogously, denote by ω2 the circumcircle of CW M , and let Y be the point on ω2 which
is diametrically opposite to W . Prove that X, Y and H are collinear.
(Thaliand)
G2. Let ω be the circumcircle of a triangle ABC. Denote by M and N the midpoints of the
sides AB and AC, respectively, and denote by T the midpoint of the arc BC of ω not containing A.
The circumcircles of the triangles AM T and AN T intersect the perpendicular bisectors of AC
and AB at points X and Y , respectively; assume that X and Y lie inside the triangle ABC. The
lines M N and XY intersect at K. Prove that KA “ KT .
(Iran)
G3. In a triangle ABC, let D and E be the feet of the angle bisectors of angles A and B,
respectively. A rhombus is inscribed into the quadrilateral AEDB (all vertices of the rhombus
lie on dierent sides of AEDB). Let ϕ be the non-obtuse angle of the rhombus. Prove that
ϕ ď maxt=BAC, =ABCu.
(Serbia)
G4. Let ABC be a triangle with =B ą =C. Let P and Q be two dierent points on line AC
such that =P BA “ =QBA “ =ACB and A is located between P and C. Suppose that there
exists an interior point D of segment BQ for which P D “ P B. Let the ray AD intersect the circle
ABC at R ‰ A. Prove that QB “ QR.
(Georgia)
G5. Let ABCDEF be a convex hexagon with AB “ DE, BC “ EF , CD “ F A, and
=A ´ =D “ =C ´ =F “ =E ´ =B. Prove that the diagonals AD, BE, and CF are concurrent.
(Ukraine)
G6. Let the excircle of the triangle ABC lying opposite to A touch its side BC at the point A1 .
Dene the points B1 and C1 analogously. Suppose that the circumcentre of the triangle A1 B1 C1
lies on the circumcircle of the triangle ABC. Prove that the triangle ABC is right-angled.
(Russia)
Shortlisted problems 7

Number Theory
N1. Let Zą0 be the set of positive integers. Find all functions f : Zą0 Ñ Zą0 such that
m2 ` f pnq | mf pmq ` n
for all positive integers m and n.
(Malaysia)
N2. Prove that for any pair of positive integers k and n there exist k positive integers
m1 , m2 , . . . , mk such that
2k ´ 1
ˆ ˙ˆ ˙ ˆ ˙
1 1 1
1` “ 1` 1` ¨¨¨ 1 ` .
n m1 m2 mk

(Japan)
N3. Prove that there exist innitely many positive integers n such that the largest prime divisor
of n4 ` n2 ` 1 is equal to the largest prime divisor of pn ` 1q4 ` pn ` 1q2 ` 1.
(Belgium)
N4. Determine whether there exists an innite sequence of nonzero digits a1 , a2 , a3 , . . . and a
positive integer N such that for every integer k ą N , the number ak ak´1 . . . a1 is a perfect square.
(Iran)
N5. Fix an integer k ě 2. Two players, called Ana and Banana, play the following game of
numbers: Initially, some integer n ě k gets written on the blackboard. Then they take moves
in turn, with Ana beginning. A player making a move erases the number m just written on the
blackboard and replaces it by some number m1 with k ď m1 ă m that is coprime to m. The rst
player who cannot move anymore loses.
An integer n ě k is called good if Banana has a winning strategy when the initial number is n,
and bad otherwise.
Consider two integers n, n1 ě k with the property that each prime number p ď k divides n if
and only if it divides n1 . Prove that either both n and n1 are good or both are bad.
(Italy)
N6. Determine all functions f : Q ÝÑ Z satisfying
ˆ ˙
f pxq ` a ´x ` a¯
f “f
b b
for all x P Q, a P Z, and b P Zą0 . (Here, Zą0 denotes the set of positive integers.)
(Israel)
N7. Let ν be an irrational positive number, and let m be a positive integer. A pair pa, bq of
positive integers is called good if
arbνs ´ btaνu “ m.
A good pair pa, bq is called excellent if neither of the pairs pa´b, bq and pa, b´aq is good. (As usual,
by txu and rxs we denote the integer numbers such that x ´ 1 ă txu ď x and x ď rxs ă x ` 1.)
Prove that the number of excellent pairs is equal to the sum of the positive divisors of m.
(U.S.A.)
4 IMO 2014 South Africa

Problems
Algebra
A1. Let z0 ă z1 ă z2 ă ¨ ¨ ¨ be an innite sequence of positive integers. Prove that there
exists a unique integer n ě 1 such that
z0 ` z1 ` ¨ ¨ ¨ ` zn
zn ă ď zn`1 .
n
(Austria)
A2. Dene the function f : p0, 1q Ñ p0, 1q by
#
1
x` 2
if x ă 21 ,
f pxq “
x2 if x ě 21 .

Let a and b be two real numbers such that 0 ă a ă b ă 1. We dene the sequences an and bn
by a0 “ a, b0 “ b, and an “ f pan´1 q, bn “ f pbn´1 q for n ą 0. Show that there exists a positive
integer n such that
pan ´ an´1 qpbn ´ bn´1 q ă 0.
(Denmark)
A3. For a sequence x1 , x2 , . . . , xn of real numbers, we dene its price as
max |x1 ` ¨ ¨ ¨ ` xi |.
1ďiďn

Given n real numbers, Dave and George want to arrange them into a sequence with a
low price. Diligent Dave checks all possible ways and nds the minimum possible price D.
Greedy George, on the other hand, chooses x1 such that |x1 | is as small as possible; among
the remaining numbers, he chooses x2 such that |x1 ` x2 | is as small as possible, and so on.
Thus, in the ith step he chooses xi among the remaining numbers so as to minimise the value
of |x1 ` x2 ` ¨ ¨ ¨ ` xi |. In each step, if several numbers provide the same value, George chooses
one at random. Finally he gets a sequence with price G.
Find the least possible constant c such that for every positive integer n, for every collection
of n real numbers, and for every possible sequence that George might obtain, the resulting
values satisfy the inequality G ď cD.
(Georgia)
A4. Determine all functions f : Z Ñ Z satisfying
` ˘
f f pmq ` n ` f pmq “ f pnq ` f p3mq ` 2014
for all integers m and n.
(Netherlands)
Shortlisted problems 5

A5. Consider all polynomials P pxq with real coecients that have the following property:
for any two real numbers x and y one has

|y 2 ´ P pxq| ď 2 |x| if and only if |x2 ´ P pyq| ď 2 |y| .

Determine all possible values of P p0q.

(Belgium)
A6. Find all functions f : Z Ñ Z such that
n2 ` 4f pnq “ f pf pnqq2

for all n P Z.
(United Kingdom)
6 IMO 2014 South Africa

Combinatorics
C1. Let n points be given inside a rectangle R such that no two of them lie on a line parallel
to one of the sides of R. The rectangle R is to be dissected into smaller rectangles with sides
parallel to the sides of R in such a way that none of these rectangles contains any of the given
points in its interior. Prove that we have to dissect R into at least n ` 1 smaller rectangles.
(Serbia)
m
C2. We have 2 sheets of paper, with the number 1 written on each of them. We perform
the following operation. In every step we choose two distinct sheets; if the numbers on the two
sheets are a and b, then we erase these numbers and write the number a ` b on both sheets.
Prove that after m2m´1 steps, the sum of the numbers on all the sheets is at least 4m .
(Iran)
C3. Let n ě 2 be an integer. Consider an n ˆ n chessboard divided into n2 unit squares.
We call a conguration of n rooks on this board happy if every row and every column contains
exactly one rook. Find the greatest positive integer k such that for every happy conguration
of rooks, we can nd a k ˆ k square without a rook on any of its k 2 unit squares.
(Croatia)
C4. Construct a tetromino by attaching two 2 ˆ 1 dominoes along their longer sides such
that the midpoint of the longer side of one domino is a corner of the other domino. This
construction yields two kinds of tetrominoes with opposite orientations. Let us call them S-
and Z-tetrominoes, respectively.

S-tetrominoes Z-tetrominoes

Assume that a lattice polygon P can be tiled with S-tetrominoes. Prove than no matter
how we tile P using only S- and Z-tetrominoes, we always use an even number of Z-tetrominoes.
(Hungary)
C5. Consider n ě 3 lines in the plane such that no two lines are parallel and no three have a
common point. These lines divide the plane into polygonal
Pa regions;
T let F be the set of regions
having nite area. Prove that it is possible to colour n{2 of the lines blue in such a way
that no region in F has a completely blue boundary. (For a real number x, rxs denotes the
least integer which is not smaller than x.)
(Austria)
Shortlisted problems 7

C6. We are given an innite deck of cards, each with a real number on it. For every real
number x, there is exactly one card in the deck that has x written on it. Now two players draw
disjoint sets A and B of 100 cards each from this deck. We would like to dene a rule that
declares one of them a winner. This rule should satisfy the following conditions:

1. The winner only depends on the relative order of the 200 cards: if the cards are laid down
in increasing order face down and we are told which card belongs to which player, but
not what numbers are written on them, we can still decide the winner.

2. If we write the elements of both sets in increasing order as A “ ta1 , a2 , . . . , a100 u and
B “ tb1 , b2 , . . . , b100 u, and ai ą bi for all i, then A beats B.

3. If three players draw three disjoint sets A, B, C from the deck, A beats B and B beats C,
then A also beats C.

How many ways are there to dene such a rule? Here, we consider two rules as dierent if there
exist two sets A and B such that A beats B according to one rule, but B beats A according to
the other.
(Russia)
C7. Let M be a set of n ě 4 points in the plane, no three of which are collinear. Initially these
points are connected with n segments so that each point in M is the endpoint of exactly two
segments. Then, at each step, one may choose two segments AB and CD sharing a common
interior point and replace them by the segments AC and BD if none of them is present at this
moment. Prove that it is impossible to perform n3 {4 or more such moves.
(Russia)
C8. A card deck consists of 1024 cards. On each card, a set of distinct decimal digits is
written in such a way that no two of these sets coincide (thus, one of the cards is empty). Two
players alternately take cards from the deck, one card per turn. After the deck is empty, each
player checks if he can throw out one of his cards so that each of the ten digits occurs on an
even number of his remaining cards. If one player can do this but the other one cannot, the
one who can is the winner; otherwise a draw is declared.
Determine all possible rst moves of the rst player after which he has a winning strategy.
(Russia)
C9. There are n circles drawn on a piece of paper in such a way that any two circles
intersect in two points, and no three circles pass through the same point. Turbo the snail slides
along the circles in the following fashion. Initially he moves on one of the circles in clockwise
direction. Turbo always keeps sliding along the current circle until he reaches an intersection
with another circle. Then he continues his journey on this new circle and also changes the
direction of moving, i.e. from clockwise to anticlockwise or vice versa.
Suppose that Turbo’s path entirely covers all circles. Prove that n must be odd.
(India)
8 IMO 2014 South Africa

Geometry
G1. The points P and Q are chosen on the side BC of an acute-angled triangle ABC so
that =P AB “ =ACB and =QAC “ =CBA. The points M and N are taken on the rays AP
and AQ, respectively, so that AP “ P M and AQ “ QN . Prove that the lines BM and CN
intersect on the circumcircle of the triangle ABC.
(Georgia)
G2. Let ABC be a triangle. The points K, L, and M lie on the segments BC, CA, and AB,
respectively, such that the lines AK, BL, and CM intersect in a common point. Prove that it
is possible to choose two of the triangles ALM , BM K, and CKL whose inradii sum up to at
least the inradius of the triangle ABC.
(Estonia)
G3. Let Ω and O be the circumcircle and the circumcentre of an acute-angled triangle ABC
with AB ą BC. The angle bisector of =ABC intersects Ω at M ‰ B. Let Γ be the circle
with diameter BM . The angle bisectors of =AOB and =BOC intersect Γ at points P and Q,
respectively. The point R is chosen on the line P Q so that BR “ M R. Prove that BR  AC.
(Here we always assume that an angle bisector is a ray.)
(Russia)
G4. Consider a xed circle Γ with three xed points A, B, and C on it. Also, let us x
a real number λ P p0, 1q. For a variable point P R tA, B, Cu on Γ, let M be the point on
the segment CP such that CM “ λ ¨ CP . Let Q be the second point of intersection of the
circumcircles of the triangles AM P and BM C. Prove that as P varies, the point Q lies on a
xed circle.
(United Kingdom)
G5. Let ABCD be a convex quadrilateral with =B “ =D “ 90 . Point H is the foot of
˝

the perpendicular from A to BD. The points S and T are chosen on the sides AB and AD,
respectively, in such a way that H lies inside triangle SCT and

=SHC ´ =BSC “ 90˝ , =T HC ´ =DT C “ 90˝ .

Prove that the circumcircle of triangle SHT is tangent to the line BD.
(Iran)
G6. Let ABC be a xed acute-angled triangle. Consider some points E and F lying on
the sides AC and AB, respectively, and let M be the midpoint of EF . Let the perpendicular
bisector of EF intersect the line BC at K, and let the perpendicular bisector of M K intersect
the lines AC and AB at S and T , respectively. We call the pair pE, F q interesting, if the
quadrilateral KSAT is cyclic.
Suppose that the pairs pE1 , F1 q and pE2 , F2 q are interesting. Prove that
E1 E2 F1 F2
“ .
AB AC
(Iran)
G7. Let ABC be a triangle with circumcircle Ω and incentre I. Let the line passing through I
and perpendicular to CI intersect the segment BC and the arc BC (not containing A) of Ω at
points U and V , respectively. Let the line passing through U and parallel to AI intersect AV
at X, and let the line passing through V and parallel to AI intersect AB at Y . Let W and Z be
the midpoints of AX and BC, respectively. Prove that if the points I, X, and Y are collinear,
then the points I, W , and Z are also collinear.
(U.S.A.)
Shortlisted problems 9

Number Theory
N1. Let n ě 2 be an integer, and let An be the set
An “ t2n ´ 2k | k P Z, 0 ď k ă nu.

Determine the largest positive integer that cannot be written as the sum of one or more (not
necessarily distinct) elements of An .
(Serbia)
N2. Determine all pairs px, yq of positive integers such that
a3
7x2 ´ 13xy ` 7y 2 “ |x ´ y| ` 1 .

(U.S.A.)
N3. A coin is called a Cape Town coin if its value is 1{n for some positive integer n. Given
a collection of Cape Town coins of total value at most 99 ` 21 , prove that it is possible to split
this collection into at most 100 groups each of total value at most 1.
(Luxembourg)
N4. Let n ą 1 be a given integer. Prove that innitely many terms of the sequence pak qkě1 ,
dened by Z k^
n
ak “ ,
k
are odd. (For a real number x, txu denotes the largest integer not exceeding x.)
(Hong Kong)
N5. Find all triples pp, x, yq consisting of a prime number p and two positive integers x and y
such that xp´1 ` y and x ` y p´1 are both powers of p.
(Belgium)
N6. Let a1 ă a2 ă ¨ ¨ ¨ ă an be pairwise coprime positive integers with a1 being prime
and a1 ě n ` 2. On the segment I “ r0, a1 a2 ¨ ¨ ¨ an s of the real line, mark all integers that are
divisible by at least one of the numbers a1 , . . . , an . These points split I into a number of smaller
segments. Prove that the sum of the squares of the lengths of these segments is divisible by a1 .
(Serbia)
N7. Let c ě 1 be an integer. Dene a sequence of positive integers by a1 “ c and
an`1 “ a3n ´ 4c ¨ a2n ` 5c2 ¨ an ` c

for all n ě 1. Prove that for each integer n ě 2 there exists a prime number p dividing an but
none of the numbers a1 , . . . , an´1 .
(Austria)
N8. For every real number x, let }x} denote the distance between x and the nearest integer.
Prove that for every pair pa, bq of positive integers there exist an odd prime p and a positive
integer k satisfying › › › › › ›
› a › › b › ›a ` b›
› ›`› ›`›
› pk › › pk › › pk › “ 1.
›

(Hungary)
Shortlisted problems 3

Problems
Algebra
A1. Suppose that a sequence a1 , a2 , . . . of positive real numbers satises
kak
ak`1 ě
a2k ` pk ´ 1q

for every positive integer k. Prove that a1 ` a2 ` ¨ ¨ ¨ ` an ě n for every n ě 2.

(Serbia)
A2. Determine all functions f : Z Ñ Z with the property that
` ˘ ` ˘
f x ´ f pyq “ f f pxq ´ f pyq ´ 1

holds for all x, y P Z.

(Croatia)
A3. Let n be a xed positive integer. Find the maximum possible value of
ÿ
ps ´ r ´ nqxr xs ,
1ďrăsď2n

where ´1 ď xi ď 1 for all i “ 1, 2, . . . , 2n.

(Austria)
A4. Find all functions f : R Ñ R satisfying the equation
` ˘
f x ` f px ` yq ` f pxyq “ x ` f px ` yq ` yf pxq

for all real numbers x and y.

(Albania)
A5. Let 2Z ` 1 denote the set of odd integers. Find all functions f : Z Ñ 2Z ` 1 satisfying
` ˘ ` ˘
f x ` f pxq ` y ` f x ´ f pxq ´ y “ f px ` yq ` f px ´ yq
for every x, y P Z.
(U.S.A.)
A6. Let n be a xed integer with n ě 2. We say that two polynomials P and Q with real
coecients are block-similar if for each i P t1, 2, . . . , nu the sequences

P p2015iq, P p2015i ´ 1q, . . . , P p2015i ´ 2014q and

Qp2015iq, Qp2015i ´ 1q, . . . , Qp2015i ´ 2014q

are permutations of each other.

paq Prove that there exist distinct block-similar polynomials of degree n ` 1.
pbq Prove that there do not exist distinct block-similar polynomials of degree n.
(Canada)
4 IMO 2015 Thailand

Combinatorics
C1. In Lineland there are n ě 1 towns, arranged along a road running from left to right.
Each town has a left bulldozer (put to the left of the town and facing left) and a right bulldozer
(put to the right of the town and facing right). The sizes of the 2n bulldozers are distinct.
Every time when a right and a left bulldozer confront each other, the larger bulldozer pushes
the smaller one o the road. On the other hand, the bulldozers are quite unprotected at their
rears; so, if a bulldozer reaches the rear-end of another one, the rst one pushes the second one
o the road, regardless of their sizes.
Let A and B be two towns, with B being to the right of A. We say that town A can sweep
town B away if the right bulldozer of A can move over to B pushing o all bulldozers it meets.
Similarly, B can sweep A away if the left bulldozer of B can move to A pushing o all bulldozers
of all towns on its way.
Prove that there is exactly one town which cannot be swept away by any other one.
(Estonia)
C2. Let V be a nite set of points in the plane. We say that V is balanced if for any two
distinct points A, B P V, there exists a point C P V such that AC “ BC. We say that V is
center-free if for any distinct points A, B, C P V, there does not exist a point P P V such that
P A “ P B “ P C.

(a) Show that for all n ě 3, there exists a balanced set consisting of n points.

(b) For which n ě 3 does there exist a balanced, center-free set consisting of n points?

(Netherlands)
C3. For a nite set A of positive integers, we call a partition of A into two disjoint nonempty
subsets A1 and A2 good if the least common multiple of the elements in A1 is equal to the
greatest common divisor of the elements in A2 . Determine the minimum value of n such that
there exists a set of n positive integers with exactly 2015 good partitions.
(Ukraine)
C4. Let n be a positive integer. Two players A and B play a game in which they take turns
choosing positive integers k ď n. The rules of the game are:

piq A player cannot choose a number that has been chosen by either player on any previous
turn.

piiq A player cannot choose a number consecutive to any of those the player has already chosen
on any previous turn.

piiiq The game is a draw if all numbers have been chosen; otherwise the player who cannot
choose a number anymore loses the game.

The player A takes the rst turn. Determine the outcome of the game, assuming that both
players use optimal strategies.
(Finland)
Shortlisted problems 5

C5. Consider an innite sequence a1 , a2 , . . . of positive integers with ai ď 2015 for all i ě 1.
Suppose that for any two distinct indices i and j we have i ` ai ‰ j ` aj .
Prove that there exist two positive integers b and N such that
ˇ ˇ
ˇ ÿn ˇ
pa ´ bq ˇ ď 10072
ˇ ˇ
ˇ i
ˇi“m`1 ˇ

whenever n ą m ě N .
(Australia)
C6. Let S be a nonempty set of positive integers. We say that a positive integer n is clean if
it has a unique representation as a sum of an odd number of distinct elements from S. Prove
that there exist innitely many positive integers that are not clean.
(U.S.A.)
C7. In a company of people some pairs are enemies. A group of people is called unsociable
if the number of members in the group is odd and at least 3, and it is possible to arrange all
its members around a round table so that every two neighbors are enemies. Given that there
are at most 2015 unsociable groups, prove that it is possible to partition the company into 11
parts so that no two enemies are in the same part.
(Russia)
6 IMO 2015 Thailand

Geometry
G1. Let ABC be an acute triangle with orthocenter H. Let G be the point such that the
quadrilateral ABGH is a parallelogram. Let I be the point on the line GH such that AC
bisects HI. Suppose that the line AC intersects the circumcircle of the triangle GCI at C
and J. Prove that IJ “ AH.
(Australia)
G2. Let ABC be a triangle inscribed into a circle Ω with center O. A circle Γ with center A
meets the side BC at points D and E such that D lies between B and E. Moreover, let F and
G be the common points of Γ and Ω. We assume that F lies on the arc AB of Ω not containing
C, and G lies on the arc AC of Ω not containing B. The circumcircles of the triangles BDF
and CEG meet the sides AB and AC again at K and L, respectively. Suppose that the lines
F K and GL are distinct and intersect at X. Prove that the points A, X, and O are collinear.
(Greece)
G3. Let ABC be a triangle with =C “ 900 , and let H be the foot of the altitude from C.
A point D is chosen inside the triangle CBH so that CH bisects AD. Let P be the intersection
point of the lines BD and CH. Let ω be the semicircle with diameter BD that meets the
segment CB at an interior point. A line through P is tangent to ω at Q. Prove that the
lines CQ and AD meet on ω.
(Georgia)
G4. Let ABC be an acute triangle, and let M be the midpoint of AC. A circle ω passing
through B and M meets the sides AB and BC again at P and Q, respectively. Let T be
the point such that the quadrilateral BP T Q is a parallelogram. Suppose that T lies on the
circumcircle of the triangle ABC. Determine all possible values of BT {BM.
(Russia)
G5. Let ABC be a triangle with CA ‰ CB. Let D, F , and G be the midpoints of the
sides AB, AC, and BC, respectively. A circle Γ passing through C and tangent to AB at D
meets the segments AF and BG at H and I, respectively. The points H 1 and I 1 are symmetric
to H and I about F and G, respectively. The line H 1 I 1 meets CD and F G at Q and M,
respectively. The line CM meets Γ again at P . Prove that CQ “ QP .
(El Salvador)
G6. Let ABC be an acute triangle with AB ą AC, and let Γ be its circumcircle. Let H,
M, and F be the orthocenter of the triangle, the midpoint of BC, and the foot of the altitude
from A, respectively. Let Q and K be the two points on Γ that satisfy =AQH “ 900 and
=QKH “ 900 . Prove that the circumcircles of the triangles KQH and KF M are tangent to
each other.
(Ukraine)
G7. Let ABCD be a convex quadrilateral, and let P , Q, R, and S be points on the sides
AB, BC, CD, and DA, respectively. Let the line segments P R and QS meet at O. Suppose
that each of the quadrilaterals AP OS, BQOP , CROQ, and DSOR has an incircle. Prove that
the lines AC, P Q, and RS are either concurrent or parallel to each other.
(Bulgaria)
G8. A triangulation of a convex polygon Π is a partitioning of Π into triangles by diagonals
having no common points other than the vertices of the polygon. We say that a triangulation
is a Thaiangulation if all triangles in it have the same area.
Prove that any two dierent Thaiangulations of a convex polygon Π dier by exactly two
triangles. (In other words, prove that it is possible to replace one pair of triangles in the rst
Thaiangulation with a dierent pair of triangles so as to obtain the second Thaiangulation.)
(Bulgaria)
Shortlisted problems 7

Number Theory
N1. Determine all positive integers M for which the sequence a0 , a1 , a2 , . . ., dened by
2M `1
a0 “ 2
and ak`1 “ ak tak u for k “ 0, 1, 2, . . ., contains at least one integer term.
(Luxembourg)
N2. Let a and b be positive integers such that a!b! is a multiple of a! ` b!. Prove that
3a ě 2b ` 2.
(United Kingdom)
N3. Let m and n be positive integers such that m ą n. Dene xk “ pm ` kq{pn ` kq for k “
1, 2, . . . , n ` 1. Prove that if all the numbers x1 , x2 , . . . , xn`1 are integers, then x1 x2 ¨ ¨ ¨ xn`1 ´ 1
is divisible by an odd prime.
(Austria)
N4. Suppose that a0 , a1 , . . . and b0 , b1 , . . . are two sequences of positive integers satisfying
a0 , b0 ě 2 and
an`1 “ gcdpan , bn q ` 1, bn`1 “ lcmpan , bn q ´ 1
for all n ě 0. Prove that the sequence (an ) is eventually periodic; in other words, there exist
integers N ě 0 and t ą 0 such that an`t “ an for all n ě N .
(France)
N5. Determine all triples pa, b, cq of positive integers for which ab ´ c, bc ´ a, and ca ´ b are
powers of 2.
Explanation: A power of 2 is an integer of the form 2n , where n denotes some nonnegative
integer.
(Serbia)
N6. Let Zą0 denote the set of positive integers. Consider a function f : Zą0 Ñ Zą0 . For
any m, n P Zą0 we write f n pmq “ looomooon
f pf p. . . f pmq . . .qq. Suppose that f has the following two
n
properties:
f n pmq ´ m
piq If m, n P Zą0 , then P Zą0 ;
n
piiq The set Zą0 z tf pnq | n P Zą0 u is nite.

Prove that the sequence f p1q ´ 1, f p2q ´ 2, f p3q ´ 3, . . . is periodic.

(Singapore)
N7. Let Zą0 denote the set of positive
` integers. For˘ any positive integer k, a function
f : Zą0 Ñ Zą0 is called k-good if gcd f pmq ` n, f pnq ` m ď k for all m ‰ n. Find all k such
that there exists a k-good function.
(Canada)
śk αi
N8. For every positive integer n with prime factorization n “ i“1 pi , dene
ÿ
℧pnq “ αi .
i : pi ą10100

That is, ℧pnq is the number of prime factors of n greater than 10100 , counted with multiplicity.
Find all strictly increasing functions f : Z Ñ Z such that
` ˘
℧ f paq ´ f pbq ď ℧pa ´ bq for all integers a and b with a ą b.

(Brazil)
Shortlisted problems 3

Problems
Algebra

A1. Let a, b and c be positive real numbers such that min {ab, bc, ca} > 1. Prove that
» Ç å2
a+b+c
3
(a2 + 1)(b2 + 1)(c2 + 1) 6 + 1.
3

A2. Find the smallest real constant C such that for any positive real numbers a1 , a2 , a3 , a4
and a5 (not necessarily distinct), one can always choose distinct subscripts i, j, k and l such
that ∣ ∣
∣a ak ∣∣
∣ i
∣ aj
∣ − ∣∣ 6 C.
al

A3. Find all integers n > 3 with the following property: for all real numbers a1 , a2 , . . . , an
and b1 , b2 , . . . , bn satisfying |ak | + |bk | = 1 for 1 6 k 6 n, there exist x1 , x2 , . . . , xn , each of
which is either −1 or 1, such that
∣ ∣ ∣ ∣
∣ n ∣ ∣ n
∣∑ ∣ ∣∑ ∣
∣
∣
∣ xk ak ∣ + ∣ xk bk ∣∣
∣ ∣ 6 1.
∣k=1 ∣ ∣k=1 ∣

A4. Denote by R+ the set of all positive real numbers. Find all functions f : R+ → R+ such
that Ä ä
xf (x2 )f (f (y)) + f (yf (x)) = f (xy) f (f (x2 )) + f (f (y 2 ))
for all positive real numbers x and y.

A5.
a
(a) Prove that for every positive integer n, there exists a fraction where a and b are integers
√ √ √ b
satisfying 0 < b 6 n + 1 and n 6 ab 6 n + 1.
a
(b) Prove that there are innitely many positive integers n such that there is no fraction
√ √ √ b
where a and b are integers satisfying 0 < b 6 n and n 6 ab 6 n + 1.
4 IMO 2016 Hong Kong

A6. The equation

(x − 1)(x − 2) · · · (x − 2016) = (x − 1)(x − 2) · · · (x − 2016)

is written on the board. One tries to erase some linear factors from both sides so that each
side still has at least one factor, and the resulting equation has no real roots. Find the least
number of linear factors one needs to erase to achieve this.

A7. Denote by R the set of all real numbers. Find all functions f : R → R such that
f (0) 6= 0 and
f (x + y)2 = 2f (x)f (y) + max {f (x2 ) + f (y 2 ), f (x2 + y 2 )}
for all real numbers x and y.

A8. Determine the largest real number a such that for all n > 1 and for all real numbers
x0 , x1 , . . . , xn satisfying 0 = x0 < x1 < x2 < · · · < xn , we have
Ç å
1 1 1 2 3 n+1
+ + ··· + >a + + ··· + .
x1 − x0 x2 − x1 xn − xn−1 x1 x2 xn
Shortlisted problems 5

Combinatorics
C1. The leader of an IMO team chooses positive integers n and k with n > k, and announces
them to the deputy leader and a contestant. The leader then secretly tells the deputy leader
an n-digit binary string, and the deputy leader writes down all n-digit binary strings which
dier from the leader’s in exactly k positions. (For example, if n = 3 and k = 1, and if the
leader chooses 101, the deputy leader would write down 001, 111 and 100.) The contestant
is allowed to look at the strings written by the deputy leader and guess the leader’s string.
What is the minimum number of guesses (in terms of n and k) needed to guarantee the correct
answer?

C2. Find all positive integers n for which all positive divisors of n can be put into the cells
of a rectangular table under the following constraints:

• each cell contains a distinct divisor;

• the sums of all rows are equal; and

• the sums of all columns are equal.

C3. Let n be a positive integer relatively prime to 6. We paint the vertices of a regular
n-gon with three colours so that there is an odd number of vertices of each colour. Show that
there exists an isosceles triangle whose three vertices are of dierent colours.

C4. Find all positive integers n for which we can ll in the entries of an n × n table with
the following properties:

• each entry can be one of I, M and O;

• in each row and each column, the letters I, M and O occur the same number of times;
and

• in any diagonal whose number of entries is a multiple of three, the letters I, M and O
occur the same number of times.

C5. Let n > 3 be a positive integer. Find the maximum number of diagonals of a regular
n-gon one can select, so that any two of them do not intersect in the interior or they are
perpendicular to each other.
6 IMO 2016 Hong Kong

C6. There are n > 3 islands in a city. Initially, the ferry company oers some routes between
some pairs of islands so that it is impossible to divide the islands into two groups such that
no two islands in dierent groups are connected by a ferry route.
After each year, the ferry company will close a ferry route between some two islands X
and Y . At the same time, in order to maintain its service, the company will open new routes
according to the following rule: for any island which is connected by a ferry route to exactly
one of X and Y , a new route between this island and the other of X and Y is added.
Suppose at any moment, if we partition all islands into two nonempty groups in any way,
then it is known that the ferry company will close a certain route connecting two islands from
the two groups after some years. Prove that after some years there will be an island which is
connected to all other islands by ferry routes.

C7. Let n > 2 be an integer. In the plane, there are n segments given in such a way that
any two segments have an intersection point in the interior, and no three segments intersect
at a single point. Je places a snail at one of the endpoints of each of the segments and claps
his hands n − 1 times. Each time when he claps his hands, all the snails move along their own
segments and stay at the next intersection points until the next clap. Since there are n − 1
intersection points on each segment, all snails will reach the furthest intersection points from
their starting points after n − 1 claps.

(a) Prove that if n is odd then Je can always place the snails so that no two of them ever
occupy the same intersection point.

(b) Prove that if n is even then there must be a moment when some two snails occupy the
same intersection point no matter how Je places the snails.

C8. Let n be a positive integer. Determine the smallest positive integer k with the following
property: it is possible to mark k cells on a 2n × 2n board so that there exists a unique
partition of the board into 1 × 2 and 2 × 1 dominoes, none of which contains two marked
cells.
Shortlisted problems 7

Geometry
G1. In a convex pentagon ABCDE, let F be a point on AC such that ∠F BC = 90◦ .
Suppose triangles ABF , ACD and ADE are similar isosceles triangles with

∠F AB = ∠F BA = ∠DAC = ∠DCA = ∠EAD = ∠EDA.

Let M be the midpoint of CF . Point X is chosen such that AM XE is a parallelogram. Show

that BD, EM and F X are concurrent.

G2. Let ABC be a triangle with circumcircle Γ and incentre I. Let M be the midpoint of
side BC. Denote by D the foot of perpendicular from I to side BC. The line through I per-
pendicular to AI meets sides AB and AC at F and E respectively. Suppose the circumcircle
of triangle AEF intersects Γ at a point X other than A. Prove that lines XD and AM meet
on Γ.

G3. Let B = (−1, 0) and C = (1, 0) be xed points on the coordinate plane. A nonempty,
bounded subset S of the plane is said to be nice if

(i) there is a point T in S such that for every point Q in S, the segment T Q lies entirely
in S; and

(ii) for any triangle P1 P2 P3 , there exists a unique point A in S and a permutation σ of the
indices {1, 2, 3} for which triangles ABC and Pσ(1) Pσ(2) Pσ(3) are similar.

Prove that there exist two distinct nice subsets S and S ′ of the set {(x, y) : x > 0, y > 0}
such that if A ∈ S and A′ ∈ S ′ are the unique choices of points in (ii), then the product
BA · BA′ is a constant independent of the triangle P1 P2 P3 .

G4. Let ABC be a triangle with AB = AC 6= BC and let I be its incentre. The line BI
meets AC at D, and the line through D perpendicular to AC meets AI at E. Prove that the
reection of I in AC lies on the circumcircle of triangle BDE.

G5. Let D be the foot of perpendicular from A to the Euler line (the line passing through the
circumcentre and the orthocentre) of an acute scalene triangle ABC. A circle ω with centre
S passes through A and D, and it intersects sides AB and AC at X and Y respectively. Let
P be the foot of altitude from A to BC, and let M be the midpoint of BC. Prove that the
circumcentre of triangle XSY is equidistant from P and M .
8 IMO 2016 Hong Kong

G6. Let ABCD be a convex quadrilateral with ∠ABC = ∠ADC < 90◦ . The internal
angle bisectors of ∠ABC and ∠ADC meet AC at E and F respectively, and meet each
other at point P . Let M be the midpoint of AC and let ω be the circumcircle of triangle
BP D. Segments BM and DM intersect ω again at X and Y respectively. Denote by Q the
intersection point of lines XE and Y F . Prove that P Q ⊥ AC.

G7. Let I be the incentre of a non-equilateral triangle ABC, IA be the A-excentre, IA′ be
the reection of IA in BC, and lA be the reection of line AIA′ in AI. Dene points IB , IB′
and line lB analogously. Let P be the intersection point of lA and lB .

(a) Prove that P lies on line OI where O is the circumcentre of triangle ABC.

(b) Let one of the tangents from P to the incircle of triangle ABC meet the circumcircle at
points X and Y . Show that ∠XIY = 120◦ .

G8. Let A1 , B1 and C1 be points on sides BC, CA and AB of an acute triangle ABC
respectively, such that AA1 , BB1 and CC1 are the internal angle bisectors of triangle ABC.
Let I be the incentre of triangle ABC, and H be the orthocentre of triangle A1 B1 C1 . Show
that
AH + BH + CH > AI + BI + CI.
Shortlisted problems 9

Number Theory
N1. For any positive integer k, denote the sum of digits of k in its decimal representation by
S(k). Find all polynomials P (x) with integer coecients such that for any positive integer
n > 2016, the integer P (n) is positive and

S(P (n)) = P (S(n)).

N2. Let τ (n) be the number of positive divisors of n. Let τ1 (n) be the number of positive
divisors of n which have remainders 1 when divided by 3. Find all possible integral values of
the fraction ττ1(10n)
(10n)
.

N3. Dene P (n) = n2 + n + 1. For any positive integers a and b, the set
{P (a), P (a + 1), P (a + 2), . . . , P (a + b)}

is said to be fragrant if none of its elements is relatively prime to the product of the other
elements. Determine the smallest size of a fragrant set.

N4. Let n, m, k and l be positive integers with n 6= 1 such that nk + mnl + 1 divides nk+l − 1.
Prove that

• m = 1 and l = 2k; or
nk−l −1
• l|k and m = nl −1
.

N5. Let a be a positive integer which is not a square number. Denote by A the set of all
positive integers k such that
x2 − a
k= 2 (1)
x − y2
√
for some integers x and y with x > a. Denote by B the set √ of all positive integers k such
that (1) is satised for some integers x and y with 0 6 x < a. Prove that A = B.

N6. Denote by N the set of all positive integers. Find all functions f : N → N such that
for all positive integers m and n, the integer f (m) + f (n) − mn is nonzero and divides
mf (m) + nf (n).
10 IMO 2016 Hong Kong

N7. Let n be an odd positive integer. In the Cartesian plane, a cyclic polygon P with area
S is chosen. All its vertices have integral coordinates, and all squares of its side lengths are
divisible by n. Prove that 2S is an integer divisible by n.

N8. Find all polynomials P (x) of odd degree d and with integer coecients satisfying the
following property: for each positive integer n, there exist n positive integers x1 , x2 , . . . , xn
(xi ) (xi )
such that 12 < PP (x j)
< 2 and PP (x j)
is the d-th power of a rational number for every pair of
indices i and j with 1 6 i, j 6 n.
 a1 , a2 , . . . , an , k M
1 1 1
` ` ¨¨¨` “k a1 a2 . . . an “ M.
a1 a2 an
M ą1

P pxq “ M px ` 1qk ´ px ` a1 qpx ` a2 q ¨ ¨ ¨ px ` an q

• a´b a b

• qab a b

• a2 ` b2 ´ c2 ´ d2
a, b, c, d

S A S S f
A T “ f pSq S f f ˝g˝f ‰g˝f ˝g
g A g‰f f pT q “ T

a1 , a2 , . . .

an “ ´ max pai ` aj q n ą 2017

i`j“n

M |an | ď M
n
 ně3 n px1 , x2 , . . . , xn q
y1 , y2 , . . . , yn

ÿ
n´1
yi yi`1 “ y1 y2 ` y2 y3 ` y3 y4 ` ¨ ¨ ¨ ` yn´1 yn ě ´1.
i“1

K “ Kpnq
ÿ
xi xj ě K
1ďiăjďn

n px1 , x2 , . . . , xn q

f: RÑR

f pf pxqf pyqq ` f px ` yq “ f pxyq

x, y P R

a0 , a1 , a2 , . . . b0 , b1 , b2 , . . .
a0 “ 0, a1 “ 1
#
an bn ` an´1 , bn´1 “ 1
an`1 “ n “ 1, 2, . . .
an bn ´ an´1 , bn´1 ą 1

a2017 a2018 2017

f: RÑR
` ˘` ˘
x, y P R f pxq ` y f pyq ` x ą 0 f pxq ` y “ f pyq ` x

f pxq ` y ď f pyq ` x xąy

 R

n 3n
n a b c
X Y
2
X Y 3n {2

2j j

2j 2j`1

2n n

N ě2 N pN ` 1q
N pN ´ 1q
2N

H0 R0 n
ně1
Rn´1
Rn Rn´1 Rn “ 1
Rn1
Rn Rn1 ď 1
Hn´1 Hn Hn´1 Hn “ 1
9
10
100
 ną1 nˆnˆn n3
nˆnˆ1 n2

3n

X Y fX pkq k
X

X ˚ Y “ X Y tfX pyq : y P Y u.

A aą0 B bą0
A˚B “B˚A

A ˚ pA ˚ ¨ ¨ ¨ ˚ pA ˚ pA ˚ Aqq . . . q “ B
looooooooooooooooooomooooooooooooooooooon ˚ pB ˚ ¨ ¨ ¨ ˚ pB ˚ pB ˚ Bqq . . . q .
looooooooooooooooooomooooooooooooooooooon
A b B a

c
p2n ` 1q ˆ p2n ` 1q c c
N
N
 ABCDE AB “ BC “ CD =EAB “ =BCD
=EDC “ =CBA E BC
AC BD

R S Ω t Ω
R R1 R S I
RS Ω Γ ISR1 t
A Γ t R AI Ω J
JR1 Γ

O ABC OA
ABC B C P Q H
P QH ABC

ABC ω A D E F
ω BC CA AB AEF BC
P Q M AD MP Q ω

ABCC1 B1 A1 AB “ BC
AA1 BB1 CC1
AC1 A1 C D ω ABC ω A1 BC1
E‰B BB1 DE ω

ně3 n A B
A B
A B
A

ABCD I Ia Ib Ic
Id DAB ABC BCD CDA
AIb Id CIb Id X
BIa Ic DIa Ic Y =XIY “ 900
 a0 , a1 , a2 , . . .
#? ?
an , an
an`1 “ ně0
an ` 3,

a0 ą 1 a an “ a
n

pě2
i t0, 1, . . . , p´1u
ai
t0, 1, 2, 3, 4, 5, 6, 7, 8, 9u
i P t0, 1, . . . , p ´ 1u
p´1
ÿ
p´1
M “ a0 ` 10 ¨ a1 ` ¨ ¨ ¨ ` 10 ¨ ap´1 “ aj ¨ 10j .
j“0

M p

ně2 a1 , a2 , . . . , an
n 1ďiďn

ai , ai ` ai`1 , . . . , ai ` ai`1 ` ¨ ¨ ¨ ` ai`n´1

n ai “ ai´n iąn

m t m
t
10 ´ 1 10k ´ 1
c P t1, 2, 3, . . . , 2017u
c¨m c¨m
1ďkăt Spmq m Spmq m “ 1, 2, . . .
Spmq

pp, qq pąq

pp ` qqp`q pp ´ qqp´q ´ 1
pp ` qqp´q pp ´ qqp`q ´ 1
 n n
n pa1 , a2 , . . . , an q
1 1 1
a1 ` a2 ` ¨ ¨ ¨ ` an ` ` ¨¨¨`
a1 a2 an

px, yq x
y S
f px, yq
f px, yq “ 1 px, yq S
n

f px, yq “ a0 xn ` a1 xn´1 y ` a2 xn´2 y 2 ` ¨ ¨ ¨ ` an´1 xy n´1 ` an y n .

p Zą0
f : Zą0 ˆ Zą0 Ñ t0, 1u

• f p1, 1q “ 0

• f pa, bq ` f pb, aq “ 1 pa, bq

1

• f pa ` b, bq “ f pa, bq pa, bq

p´1
ÿ a
f pn2 , pq ě 2p ´ 2.
n“1
 Qą0
f : Qą0 Ñ Qą0
f x2 f pyq2 “ f pxq2 f pyq
` ˘

x, y P Qą0

n ě 3 a1 , a2 , . . . , an
an`1 “ a1 an`2 “ a2
ai ai`1 ` 1 “ ai`2
i “ 1, 2, . . . , n

ř ř
F G S xPF 1{x “ xPG 1{x
ř
ră1 xPF 1{x ‰ r
F S

a0 , a1 , a2 , . . . a0 “ 0 a1 “ 1
ně2 1ďkďn
an´1 ` ¨ ¨ ¨ ` an´k
an “ .
k
a2018 ´ a2017

f : p0, 8q Ñ R
ˆ ˙
1 ´y¯
x` f pyq “ f pxyq ` f
x x
x, y ą 0

m, n ě 2 f px1 , . . . , xn q
Yx ` . . . ` x ]
1 n  (
f px1 , . . . , xn q “ x1 , . . . , xn P 0, 1, . . . , m ´ 1
m
f n

c c c c
3 a 3 b 3 c 3 d
S“ ` ` ` ,
b`7 c`7 d`7 a`7
a, b, c, d a ` b ` c ` d “ 100
 n ě 3 S 2n
m “ 2, 3, . . . , n S
m

20 ˆ 20

K
K

n
n`1 0 n n
0
k
k n
n

QnU QnU QnU QnU

` ` ` ¨¨¨`
1 2 3 n
rxs x

1 1 ` 2 ` 3 ` 4 “ 10

2018 1
1 ` 2 ` ¨ ¨ ¨ ` 2018

k
2k
 a b

piq
a b

piiq

piq piiq
 ABC Γ D E
AB AC AD “ AE
BD CE Ŋ
AB Ŋ
AC F G
DE  F G

ABC AB “ AC M BC P
PB ă PC PA BC X Y
PB PC B PX C PY
=P XM “ =P Y M AP XY

ω T

piq T ω

piiq T

t n
n t

T ABC A1 B 1 C1
T BC CA AB Ω A1 B 1 C 1
A1 T B 1 T C1 T Ω A2 B 2 C2
AA2 BB2 CC2 Ω

ABC ω I ℓ
AI BI CI D E F A B C
I x y z AD BE CF
Θ Θ ω

ABCD AB ¨ CD “ BC ¨ DA X
=XAB “ =XCD =XBC “ =XDA =AXB `
=CXD “ 180˝

O Ω ABC
P Ω A B C Ω
AOP BOP COP OA OB OC
ℓA ℓB ℓC BC CA AB OA OB OC
ℓA ℓB ℓC
OP
 pn, kq
s sn sk

n ą 1 nˆn

piq 1 n

piiq
n n2

Ri i Cj
j R1 ` ¨ ¨ ¨ ` Rn C1 ` ¨ ¨ ¨ ` Cn n4

a0 , a1 , a2 , . . . an “ 2n ` 2tn{2u

a1 a2 . . . an . . .
a1 a2 an´1 an
` ` ¨¨¨` `
a2 a3 an a1
něk k
m an “ an`1 něm

x y z t

xy ´ zt “ x ` y “ z ` t.

xy zt

f : t1, 2, 3, . . .u Ñ t2, 3, . . .u f pm ` nq | f pmq ` f pnq

m, n cą1
f

n ě 2018 a1 , a2 , . . . , an , b1 , b2 , . . . , bn
5n
a1 a2 an
, , ...,
b1 b2 bn
4 Bath — UK, 11th–22nd July 2019

Problems
Algebra
A1. Let Z be the set of integers. Determine all functions f : Z Ñ Z such that, for all
integers a and b,
f p2aq ` 2f pbq “ f pf pa ` bqq.
(South Africa)
A2. Let u1 , u2 , . . . , u2019 be real numbers satisfying

u1 ` u2 ` ¨ ¨ ¨ ` u2019 “ 0 and u21 ` u22 ` ¨ ¨ ¨ ` u22019 “ 1.

Let a “ minpu1 , u2 , . . . , u2019 q and b “ maxpu1 , u2 , . . . , u2019 q. Prove that

1
ab ď ´ .
2019
(Germany)
A3. Let n ě 3 be a positive integer and let pa1 , a2 , . . . , an q be a strictly increasing
sequence of n positive real numbers with sum equal to 2. Let X be a subset of t1, 2, . . . , nu
such that the value of ˇ ˇ
ˇ ÿ ˇ
ˇ1 ´
ˇ ˇ
ai ˇ
ˇ iPX
ˇ
is minimised. Prove that there exists a strictly increasing sequence of n positive real numbers
pb1 , b2 , . . . , bn q with sum equal to 2 such that
ÿ
bi “ 1.
iPX

(New Zealand)
A4. Let n ě 2 be a positive integer and a1 , a2 , . . . , an be real numbers such that

a1 ` a2 ` ¨ ¨ ¨ ` an “ 0.

Dene the set A by  ˇ (

A “ pi, jq ˇ 1 ď i ă j ď n, |ai ´ aj | ě 1 .
Prove that, if A is not empty, then ÿ
ai aj ă 0.
pi,jqPA

(China)
A5. Let x1 , x2 , . . . , xn be dierent real numbers. Prove that
#
ÿ ź 1 ´ xi xj 0, if n is even;
“
1ďiďn j‰i
xi ´ xj 1, if n is odd.

(Kazakhstan)
Shortlisted problems 5

A6. A polynomial P px, y, zq in three variables with real coecients satises the identities

P px, y, zq “ P px, y, xy ´ zq “ P px, zx ´ y, zq “ P pyz ´ x, y, zq.

Prove that there exists a polynomial F ptq in one variable such that

P px, y, zq “ F px2 ` y 2 ` z 2 ´ xyzq.

(Russia)
A7. Let Z be the set of integers. We consider functions f : Z Ñ Z satisfying
` ˘ ` ˘
f f px ` yq ` y “ f f pxq ` y

for all integers x and y. For such a function, we say that an integer v is f -rare if the set

Xv “ tx P Z : f pxq “ vu

is nite and nonempty.

(a) Prove that there exists such a function f for which there is an f -rare integer.

(b) Prove that no such function f can have more than one f -rare integer.

(Netherlands)
6 Bath — UK, 11th–22nd July 2019

Combinatorics
C1. The innite sequence a0 , a1 , a2 , . . . of (not necessarily dierent) integers has the
following properties: 0 ď ai ď i for all integers i ě 0, and
ˆ ˙ ˆ ˙ ˆ ˙
k k k
` ` ¨¨¨` “ 2k
a0 a1 ak
for all integers k ě 0.
Prove that all integers N ě 0 occur in the sequence (that is, for all N ě 0, there exists i ě 0
with ai “ N ).
(Netherlands)
C2. You are given a set of n blocks, each weighing at least 1; their total weight is 2n.
Prove that for every real number r with 0 ď r ď 2n ´ 2 you can choose a subset of the blocks
whose total weight is at least r but at most r ` 2.
(Thailand)
C3. Let n be a positive integer. Harry has n coins lined up on his desk, each showing
heads or tails. He repeatedly does the following operation: if there are k coins showing heads
and k ą 0, then he ips the k th coin over; otherwise he stops the process. (For example, the
process starting with T HT would be T HT Ñ HHT Ñ HT T Ñ T T T , which takes three
steps.)
Letting C denote the initial conguration (a sequence of n H’s and T ’s), write ℓpCq for the
number of steps needed before all coins show T . Show that this number ℓpCq is nite, and
determine its average value over all 2n possible initial congurations C.
(USA)
C4. On a at plane in Camelot, King Arthur builds a labyrinth L consisting of n walls,
each of which is an innite straight line. No two walls are parallel, and no three walls have a
common point. Merlin then paints one side of each wall entirely red and the other side entirely
blue.
At the intersection of two walls there are four corners: two diagonally opposite corners
where a red side and a blue side meet, one corner where two red sides meet, and one corner
where two blue sides meet. At each such intersection, there is a two-way door connecting the
two diagonally opposite corners at which sides of dierent colours meet.
After Merlin paints the walls, Morgana then places some knights in the labyrinth. The
knights can walk through doors, but cannot walk through walls.
Let kpLq be the largest number k such that, no matter how Merlin paints the labyrinth L,
Morgana can always place at least k knights such that no two of them can ever meet. For
each n, what are all possible values for kpLq, where L is a labyrinth with n walls?
(Canada)
C5. On a certain social network, there are 2019 users, some pairs of which are friends,
where friendship is a symmetric relation. Initially, there are 1010 people with 1009 friends each
and 1009 people with 1010 friends each. However, the friendships are rather unstable, so events
of the following kind may happen repeatedly, one at a time:
Let A, B, and C be people such that A is friends with both B and C, but B and C
are not friends; then B and C become friends, but A is no longer friends with them.
Prove that, regardless of the initial friendships, there exists a sequence of such events after
which each user is friends with at most one other user.
(Croatia)
Shortlisted problems 7

C6. Let n ą 1 be an integer. Suppose we are given 2n points in a plane such that
no three of them are collinear. The points are to be labelled A1 , A2 , . . . , A2n in some order.
We then consider the 2n angles =A1 A2 A3 , =A2 A3 A4 , . . . , =A2n´2 A2n´1 A2n , =A2n´1 A2n A1 ,
=A2n A1 A2 . We measure each angle in the way that gives the smallest positive value (i.e.
between 0˝ and 180˝). Prove that there exists an ordering of the given points such that the
resulting 2n angles can be separated into two groups with the sum of one group of angles equal
to the sum of the other group.
(USA)
C7. There are 60 empty boxes B1 , . . . , B60 in a row on a table and an unlimited supply
of pebbles. Given a positive integer n, Alice and Bob play the following game.
In the rst round, Alice takes n pebbles and distributes them into the 60 boxes as she
wishes. Each subsequent round consists of two steps:

(a) Bob chooses an integer k with 1 ď k ď 59 and splits the boxes into the two groups
B1 , . . . , Bk and Bk`1, . . . , B60 .

(b) Alice picks one of these two groups, adds one pebble to each box in that group, and removes
one pebble from each box in the other group.

Bob wins if, at the end of any round, some box contains no pebbles. Find the smallest n
such that Alice can prevent Bob from winning.
(Czech Republic)
C8. Alice has a map of Wonderland, a country consisting of n ě 2 towns. For every
pair of towns, there is a narrow road going from one town to the other. One day, all the roads
are declared to be “one way” only. Alice has no information on the direction of the roads, but
the King of Hearts has oered to help her. She is allowed to ask him a number of questions.
For each question in turn, Alice chooses a pair of towns and the King of Hearts tells her the
direction of the road connecting those two towns.
Alice wants to know whether there is at least one town in Wonderland with at most one
outgoing road. Prove that she can always nd out by asking at most 4n questions.

Comment. This problem could be posed with an explicit statement about points being awarded for
weaker bounds cn for some c ą 4, in the style of IMO 2014 Problem 6.
(Thailand)
C9. For any two dierent real numbers x and y, we dene Dpx, yq to be the unique
integer d satisfying 2d ď |x ´ y| ă 2d`1 . Given a set of reals F , and an element x P F , we say
that the scales of x in F are the values of Dpx, yq for y P F with x ‰ y.
Let k be a given positive integer. Suppose that each member x of F has at most k dierent
scales in F (note that these scales may depend on x). What is the maximum possible size of F ?
(Italy)
8 Bath — UK, 11th–22nd July 2019

Geometry
G1. Let ABC be a triangle. Circle Γ passes through A, meets segments AB and AC
again at points D and E respectively, and intersects segment BC at F and G such that F lies
between B and G. The tangent to circle BDF at F and the tangent to circle CEG at G meet
at point T . Suppose that points A and T are distinct. Prove that line AT is parallel to BC.
(Nigeria)
G2. Let ABC be an acute-angled triangle and let D, E, and F be the feet of altitudes
from A, B, and C to sides BC, CA, and AB, respectively. Denote by ωB and ωC the incircles
of triangles BDF and CDE, and let these circles be tangent to segments DF and DE at M
and N , respectively. Let line MN meet circles ωB and ωC again at P ‰ M and Q ‰ N ,
respectively. Prove that MP “ N Q.
(Vietnam)
G3. In triangle ABC, let A1 and B1 be two points on sides BC and AC, and let P and Q
be two points on segments AA1 and BB1 , respectively, so that line P Q is parallel to AB. On
ray P B1 , beyond B1 , let P1 be a point so that =P P1 C “ =BAC. Similarly, on ray QA1 ,
beyond A1 , let Q1 be a point so that =CQ1 Q “ =CBA. Show that points P , Q, P1 , and Q1
are concyclic.
(Ukraine)
G4. Let P be a point inside triangle ABC. Let AP meet BC at A1 , let BP meet CA
at B1 , and let CP meet AB at C1 . Let A2 be the point such that A1 is the midpoint of P A2 ,
let B2 be the point such that B1 is the midpoint of P B2 , and let C2 be the point such that
C1 is the midpoint of P C2 . Prove that points A2 , B2 , and C2 cannot all lie strictly inside the
circumcircle of triangle ABC.
(Australia)
G5. Let ABCDE be a convex pentagon with CD “ DE and =EDC ‰ 2 ¨ =ADB.
Suppose that a point P is located in the interior of the pentagon such that AP “ AE and
BP “ BC. Prove that P lies on the diagonal CE if and only if areapBCDq ` areapADEq “
areapABDq ` areapABP q.
(Hungary)
G6. Let I be the incentre of acute-angled triangle ABC. Let the incircle meet BC, CA,
and AB at D, E, and F , respectively. Let line EF intersect the circumcircle of the triangle
at P and Q, such that F lies between E and P . Prove that =DP A ` =AQD “ =QIP .
(Slovakia)
G7. The incircle ω of acute-angled scalene triangle ABC has centre I and meets sides BC,
CA, and AB at D, E, and F , respectively. The line through D perpendicular to EF meets ω
again at R. Line AR meets ω again at P . The circumcircles of triangles P CE and P BF meet
again at Q ‰ P . Prove that lines DI and P Q meet on the external bisector of angle BAC.
(India)
G8. Let L be the set of all lines in the plane and let f be a function that assigns to each
line ℓ P L a point f pℓq on ℓ. Suppose that for any point X, and for any three lines ℓ1 , ℓ2 , ℓ3
passing through X, the points f pℓ1 q, f pℓ2 q, f pℓ3 q and X lie on a circle.
Prove that there is a unique point P such that f pℓq “ P for any line ℓ passing through P .
(Australia)
Shortlisted problems 9

Number Theory
N1. Find all pairs pm, nq of positive integers satisfying the equation

p2n ´ 1qp2n ´ 2qp2n ´ 4q ¨ ¨ ¨ p2n ´ 2n´1 q “ m!

(El Salvador)
N2. Find all triples pa, b, cq of positive integers such that a3 ` b3 ` c3 “ pabcq2 .
(Nigeria)
N3. We say that a set S of integers is rootiful if, for any positive integer n and any
a0 , a1 , . . . , an P S, all integer roots of the polynomial a0 ` a1 x ` ¨ ¨ ¨ ` an xn are also in S. Find
all rootiful sets of integers that contain all numbers of the form 2a ´ 2b for positive integers
a and b.
(Czech Republic)
N4. Let Zą0 be the set of positive integers. A positive integer constant C is given. Find
all functions f : Zą0 Ñ Zą0 such that, for all positive integers a and b satisfying a ` b ą C,

a ` f pbq | a2 ` b f paq.

(Croatia)
N5. Let a be a positive integer. We say that a positive integer b is a-good if `anb˘ ´ 1 is
divisible by an ` 1 for all positive integers n with an ě b. Suppose b is a positive integer such
that b is a-good, but b ` 2 is not a-good. Prove that b ` 1 is prime.
(Netherlands)
N6. Let H “  Xi?2\ : i P Zą0 ( “ t1, 2, 4, 5, 7, . . .u, and let n be a positive integer. Prove
?
that there exists a constant C such that, if A Ă t1, 2, . . . , nu satises |A| ě C n, then there
exist a, b P A such that a ´ b P H. (Here Zą0 is the set of positive integers, and tzu denotes the
greatest integer less than or equal to z.)
(Brazil)
N7. Prove that there is a constant c ą 0 and innitely many positive integers n with the
following property: there are innitely many positive integers that cannot be expressed as the
sum of fewer than cn logpnq pairwise coprime nth powers.
(Canada)
N8. Let a and b be two positive integers. Prove that the integer
R 2V
2 4a
a `
b

is not a square. (Here rzs denotes the least integer greater than or equal to z.)
(Russia)
4 Saint-Petersburg — Russia, 18th–28th September 2020

Problems
Algebra
A1. Version 1. Let n be a positive integer, and set N “ 2n . Determine the smallest real
number an such that, for all real x,
c
2N ` 1
N x
ď an px ´ 1q2 ` x.
2

Version 2. For every positive integer N , determine the smallest real number bN such that,
for all real x, c
2N ` 1
N x
ď bN px ´ 1q2 ` x.
2
(Ireland)
A2. Let A denote the set of all polynomials in three variables x, y, z with integer
coecients. Let B denote the subset of A formed by all polynomials which can be expressed as

px ` y ` zqP px, y, zq ` pxy ` yz ` zxqQpx, y, zq ` xyzRpx, y, zq

with P, Q, R P A. Find the smallest non-negative integer n such that xi y j z k P B for all non-
negative integers i, j, k satisfying i ` j ` k ě n.
(Venezuela)
A3. Suppose that a, b, c, d are positive real numbers satisfying pa ` cqpb ` dq “ ac ` bd.
Find the smallest possible value of
a b c d
` ` ` .
b c d a
(Israel)
A4. Let a, b, c, d be four real numbers such that a ě b ě c ě d ą 0 and a ` b ` c ` d “ 1.
Prove that
pa ` 2b ` 3c ` 4dq aa bb cc dd ă 1.
(Belgium)
A5. A magician intends to perform the following trick. She announces a positive integer
n, along with 2n real numbers x1 ă . . . ă x2n , to the audience. A member of the audience then
secretly chooses a polynomial P pxq of degree n with real coecients, computes the 2n values
P px1 q, . . . , P px2n q, and writes down these 2n values on the blackboard in non-decreasing order.
After that the magician announces the secret polynomial to the audience.
Can the magician nd a strategy to perform such a trick?
(Luxembourg)
A6. Determine all functions f : Z Ñ Z such that
2 `b2
fa pa ` bq “ af paq ` bf pbq for every a, b P Z.

Here, f n denotes the nth iteration of f , i.e., f 0 pxq “ x and f n`1pxq “ f pf n pxqq for all n ě 0.
(Slovakia)
Shortlisted problems 5

A7. Let n and k be positive integers. Prove that for a1 , . . . , an P r1, 2k s one has
n
ÿ ai ?
a ď 4 kn.
2 2
i“1 a1 ` . . . ` ai

(Iran)
A8. Let R` be the set of positive real numbers. Determine all functions f : R` Ñ R`
such that, for all positive real numbers x and y,
` ˘
f x ` f pxyq ` y “ f pxqf pyq ` 1.

(Ukraine)
6 Saint-Petersburg — Russia, 18th–28th September 2020

Combinatorics
C1. Let n be a positive integer. Find the number of permutations a1 , a2 , . . . , an of the
sequence 1, 2, . . . , n satisfying

a1 ď 2a2 ď 3a3 ď . . . ď nan .

(United Kingdom)
C2. In a regular 100-gon, 41 vertices are colored black and the remaining 59 vertices are
colored white. Prove that there exist 24 convex quadrilaterals Q1 , . . . , Q24 whose corners are
vertices of the 100-gon, so that

• the quadrilaterals Q1 , . . . , Q24 are pairwise disjoint, and

• every quadrilateral Qi has three corners of one color and one corner of the other color.

(Austria)
C3. Let n be an integer with n ě 2. On a slope of a mountain, n2 checkpoints are
marked, numbered from 1 to n2 from the bottom to the top. Each of two cable car companies,
A and B, operates k cable cars numbered from 1 to k; each cable car provides a transfer from
some checkpoint to a higher one. For each company, and for any i and j with 1 ď i ă j ď k,
the starting point of car j is higher than the starting point of car i; similarly, the nishing point
of car j is higher than the nishing point of car i. Say that two checkpoints are linked by some
company if one can start from the lower checkpoint and reach the higher one by using one or
more cars of that company (no movement on foot is allowed).
Determine the smallest k for which one can guarantee that there are two checkpoints that
are linked by each of the two companies.
(India)
C4. The Fibonacci numbers F0 , F1 , F2 , . . . are dened inductively by F0 “ 0, F1 “ 1, and
Fn`1 “ Fn ` Fn´1 for n ě 1. Given an integer n ě 2, determine the smallest size of a set S of
integers such that for every k “ 2, 3, . . . , n there exist some x, y P S such that x ´ y “ Fk .
(Croatia)
C5. Let p be an odd prime, and put N “ 41 pp3 ´ pq ´ 1. The numbers 1, 2, . . . , N are
painted arbitrarily in two colors, red and blue. For any positive integer n ď N , denote by rpnq
the fraction of integers in t1, 2, . . . , nu that are red.
Prove that there exists a positive integer a P t1, 2, . . . , p ´ 1u such that rpnq ‰ a{p for all
n “ 1, 2, . . . , N .
(Netherlands)
C6. 4n coins of weights 1, 2, 3, . . . , 4n are given. Each coin is colored in one of n colors
and there are four coins of each color. Show that all these coins can be partitioned into two
sets with the same total weight, such that each set contains two coins of each color.
(Hungary)
Shortlisted problems 7

C7. Consider any rectangular table having nitely many rows and columns, with a real
number apr, cq in the cell in row r and column c. A pair pR, Cq, where R is a set of rows and
C a set of columns, is called a saddle pair if the following two conditions are satised:
piq For each row r 1 , there is r P R such that apr, cq ě apr 1 , cq for all c P C;
piiq For each column c1 , there is c P C such that apr, cq ď apr, c1 q for all r P R.
A saddle pair pR, Cq is called a minimal pair if for each saddle pair pR1 , C 1 q with R1 Ď R
and C 1 Ď C, we have R1 “ R and C 1 “ C.
Prove that any two minimal pairs contain the same number of rows.
(Thailand)
C8. Players A and B play a game on a blackboard that initially contains 2020 copies
of the number 1. In every round, player A erases two numbers x and y from the blackboard,
and then player B writes one of the numbers x ` y and |x ´ y| on the blackboard. The game
terminates as soon as, at the end of some round, one of the following holds:
(1) one of the numbers on the blackboard is larger than the sum of all other numbers;
(2) there are only zeros on the blackboard.
Player B must then give as many cookies to player A as there are numbers on the blackboard.
Player A wants to get as many cookies as possible, whereas player B wants to give as few as
possible. Determine the number of cookies that A receives if both players play optimally.
(Austria)
8 Saint-Petersburg — Russia, 18th–28th September 2020

Geometry
G1. Let ABC be an isosceles triangle with BC “ CA, and let D be a point inside side
AB such that AD ă DB. Let P and Q be two points inside sides BC and CA, respectively,
such that =DP B “ =DQA “ 90˝ . Let the perpendicular bisector of P Q meet line segment
CQ at E, and let the circumcircles of triangles ABC and CP Q meet again at point F , dierent
from C.
Suppose that P, E, F are collinear. Prove that =ACB “ 90˝ .
(Luxembourg)
G2. Let ABCD be a convex quadrilateral. Suppose that P is a point in the interior of
ABCD such that

=P AD : =P BA : =DP A “ 1 : 2 : 3 “ =CBP : =BAP : =BP C.

The internal bisectors of angles ADP and P CB meet at a point Q inside the triangle ABP .
Prove that AQ “ BQ.
(Poland)
G3. Let ABCD be a convex quadrilateral with =ABC ą 90˝ , =CDA ą 90˝ , and
=DAB “ =BCD. Denote by E and F the reections of A in lines BC and CD, respectively.
Suppose that the segments AE and AF meet the line BD at K and L, respectively. Prove that
the circumcircles of triangles BEK and DF L are tangent to each other.
(Slovakia)
G4. In the plane, there are n ě 6 pairwise disjoint disks D1 , D2 , . . . , Dn with radii
R1 ě R2 ě . . . ě Rn . For every i “ 1, 2, . . . , n, a point Pi is chosen in disk Di . Let O be an
arbitrary point in the plane. Prove that

OP1 ` OP2 ` . . . ` OPn ě R6 ` R7 ` . . . ` Rn .

(A disk is assumed to contain its boundary.)

(Iran)
G5. Let ABCD be a cyclic quadrilateral with no two sides parallel. Let K, L, M , and N
be points lying on sides AB, BC, CD, and DA, respectively, such that KLMN is a rhombus
with KL  AC and LM  BD. Let ω1 , ω2 , ω3 , and ω4 be the incircles of triangles AN K,
BKL, CLM, and DMN , respectively. Prove that the internal common tangents to ω1 and ω3
and the internal common tangents to ω2 and ω4 are concurrent.
(Poland)
G6. Let I and IA be the incenter and the A-excenter of an acute-angled triangle ABC
with AB ă AC. Let the incircle meet BC at D. The line AD meets BIA and CIA at E
and F , respectively. Prove that the circumcircles of triangles AID and IA EF are tangent to
each other.
(Slovakia)
Shortlisted problems 9

G7. Let P be a point on the circumcircle of an acute-angled triangle ABC. Let D,

E, and F be the reections of P in the midlines of triangle ABC parallel to BC, CA, and AB,
respectively. Denote by ωA , ωB , and ωC the circumcircles of triangles ADP , BEP , and CF P ,
respectively. Denote by ω the circumcircle of the triangle formed by the perpendicular bisectors
of segments AD, BE and CF .
Show that ωA , ωB , ωC , and ω have a common point.
(Denmark)
G8. Let Γ and I be the circumcircle and the incenter of an acute-angled triangle ABC.
Two circles ωB and ωC passing through B and C, respectively, are tangent at I. Let ωB meet
the shorter arc AB of Γ and segment AB again at P and M, respectively. Similarly, let ωC
meet the shorter arc AC of Γ and segment AC again at Q and N , respectively. The rays P M
and QN meet at X, and the tangents to ωB and ωC at B and C, respectively, meet at Y .
Prove that the points A, X, and Y are collinear.
(Netherlands)
G9. Prove that there exists a positive constant c such that the following statement is
true:
Assume that n is an integer with n ě 2, and let S be a set of n points in the plane such
that the distance between any two distinct points in S is at least 1. Then there is a line ℓ
separating S such that the distance from any point of S to ℓ is at least cn´1{3 .
(A line ℓ separates a point set S if some segment joining two points in S crosses ℓ.)
(Taiwan)
10 Saint-Petersburg — Russia, 18th–28th September 2020

Number Theory
N1. Given a positive integer k, show that there exists a prime p such that one can choose
distinct integers a1 , a2 , . . . , ak`3 P t1, 2, . . . , p ´ 1u such that p divides ai ai`1 ai`2 ai`3 ´ i for all
i “ 1, 2, . . . , k.
(South Africa)
N2. For each prime p, there is a kingdom of p-Landia consisting of p islands numbered
1, 2, . . . , p. Two distinct islands numbered n and m are connected by a bridge if and only if
p divides pn2 ´ m ` 1qpm2 ´ n ` 1q. The bridges may pass over each other, but cannot cross.
Prove that for innitely many p there are two islands in p-Landia not connected by a chain of
bridges.
(Denmark)
N3. Let n be an integer with n ě 2. Does there exist a sequence pa1 , . . . , an q of positive
integers with not all terms being equal such that the arithmetic mean of every two terms is
equal to the geometric mean of some (one or more) terms in this sequence?
(Estonia)
N4. For any odd prime p and any integer n, let dp pnq P t0, 1, . . . , p ´ 1u denote the
remainder when n is divided by p. We say that pa0 , a1 , a2 , . . .q is a p-sequence, if a0 is a positive
integer coprime to p, and an`1 “ an ` dp pan q for n ě 0.
(a) Do there exist innitely many primes p for which there exist p-sequences pa0 , a1 , a2 , . . .q and
pb0 , b1 , b2 , . . .q such that an ą bn for innitely many n, and bn ą an for innitely many n?
(b) Do there exist innitely many primes p for which there exist p-sequences pa0 , a1 , a2 , . . .q and
pb0 , b1 , b2 , . . .q such that a0 ă b0 , but an ą bn for all n ě 1?
(United Kingdom)
N5. Determine all functions f dened on the set of all positive integers and taking
non-negative integer values, satisfying the three conditions:
piq f pnq ‰ 0 for at least one n;
piiq f pxyq “ f pxq ` f pyq for every positive integers x and y;
piiiq there are innitely many positive integers n such that f pkq “ f pn ´ kq for all k ă n.
(Croatia)
N6. For a positive integer n, let dpnq be the number of positive divisors of n, and let
ϕpnq be the number of positive integers not exceeding n which are coprime to n. Does there
exist a constant C such that
ϕpdpnqq
ďC
dpϕpnqq
for all n ě 1?
(Cyprus)
N7. Let S be a set consisting of n ě 3 positive integers, none of which is a sum of two
other distinct members of S. Prove that the elements of S may be ordered as a1 , a2 , . . . , an so
that ai does not divide ai´1 ` ai`1 for all i “ 2, 3, . . . , n ´ 1.
(Ukraine)
 n A 0, 1, 2, 3, . . . , 5n 4n 2
a, b, c A a b c c 2a 3b

ij
n 1 n n
n 1
i j i 1, . . . , n j 1, . . . , n n 1
1 2
n2 4
n n 1

a1 a2 an
n
1 2 n
a1 , a2 , . . . , an 1, 2, . . . , n

x1 , . . . , xn
n n n n
xi xj xi xj .
i 1j 1 i 1j 1

n 2 a1 , a2 , . . . , an
a1 a2 an 1
n
ak 2 1
a1 a2 ak 1 .
k 1
1 ak 3

A m 2
B1 , B2 , B3 , . . . , Bm A
m1 , m2 , m3 , . . . , mm A m 2

n 1 x0 , x1 , . . . , xn 1 n 2
xi xi 1 x2i 1 1 i 1, 2, . . . , n
3 2
2n
x0 x1 xn xn 1 .
3

f :R R

f a f b f b f c f c f a f ab2 bc2 ca2 f a2 b b2 c c2 a

a, b, c
 S
a, b, c, d S gcd a, b gcd c, d x, y, z S
gcd x, y gcd y, z gcd z, x

n 3 m n 1 n
n C1 , C2 , . . . , Cn m
n 1
Ci i 1, . . . , n
n

2021 1 2021
2021
k k
k k
a b a k b

n
X Y
X Y

A B NAB
A B NBA
B A NAB NBA
A
B

n k n k 1 2n 1
S 2k k S
k S
n 1 n
k
 3m 3m m 1
S F

X
F S X

3m2 3m
3m2

m 2 X
x

F
x x
x
x
x
S x

N T N
100

r s c T r, c T s, c 2

T r, c r c
 ABCD AC BC P
AB B ACD
PD Q AP Q PC
R CD AQ BR

ABCD I
ω ACI BA BC A
C ω X Z AD CD D ω Y
T
ADT X CDY Z

n S x, y
x y 2n
S 4n2 F n2
S S F
2
n F
n S x, y
x y 2n
S 4n2 F F
S S F
F

ABCD Ω Ω D
BA BC E F T
ABC T E  CD T F  AD K D DF
TD TK AC DT BK

ABCD
O ABCD ABC ADC AC
B1 D1 OB B
AC D1 OD D
AC B1
BD1  DB1 O OB OD

n 3 n
1 1
 D ABC AB AC
BAD DAC E AC ADE DCB
F AB ADF DBC
X AC CX BX O1 O2
ADC DXE BC EF O1 O2

ω ABC ΩA
BC X Y ω ΩA P Q
A ΩA X Y P
AP X Q
AQY R AR BC
 n 1 a, b
a2 b 3
ab 3b 8
n.
a2 b 3

n 100 n, n 1, . . . , 2n n 1

n k n
d1 , d2 , . . . , dk i 1, 2, . . . , k d1 di

r 1 B R
R B

k X Y
k
X YX r YX
B r 1
2021

a, b, c, n

n! an 1
bn 1
cn 1 .

n 2 n
n a1 a2 an
n 1 a1 2 a2 n an

a1 , a2 , a3 , . . . an 2m
an an m n m
N d an an d n N

P x P1 x P x Pk 1 x
P Pk x k 1 n P x
m 1 Pm m
1 ,...,P n
n 2m n
Shortlisted problems 3

Problems
Algebra
A1. Let pan qně1 be a sequence of positive real numbers with the property that
pan`1 q2 ` an an`2 ď an ` an`2
for all positive integers n. Show that a2022 ď 1.
(Nigeria)
A2. Let k ě 2 be an integer. Find the smallest integer n ě k ` 1 with the property that
there exists a set of n distinct real numbers such that each of its elements can be written as a
sum of k other distinct elements of the set.
(Slovakia)
A3. Let Rą0 be the set of positive real numbers. Find all functions f : Rą0 Ñ Rą0 such
that, for every x P Rą0 , there exists a unique y P Rą0 satisfying
xf pyq ` yf pxq ď 2.
(Netherlands)
A4. Let n ě 3 be an integer, and let x1 , x2 , ..., xn be real numbers in the interval r0, 1s.
Let s “ x1 ` x2 ` . . . ` xn , and assume that s ě 3. Prove that there exist integers i and j with
1 ď i ă j ď n such that
2j´i xi xj ą 2s´3 .
(Trinidad and Tobago)
A5. Find all positive integers n ě 2 for which there exist n real numbers a1 ă ¨ ¨ ¨ ă an
and a real number r ą 0 such that the 12 npn ´ 1q dierences aj ´ ai for 1 ď i ă j ď n are equal,
1
in some order, to the numbers r1 , r2 , . . . , r 2 npn´1q .
(Czech Republic)
A6. Let R be the set of real numbers. We denote by F the set of all functions f : R Ñ R
such that
f px ` f pyqq “ f pxq ` f pyq
for every x, y P R. Find all rational numbers q such that for every function f P F , there exists
some z P R satisfying f pzq “ qz.
(Indonesia)
A7. For a positive integer n we denote by spnq the sum of the digits of n. Let P pxq “
xn ` an´1 xn´1 ` ¨ ¨ ¨ ` a1 x ` a0 be a polynomial, where n ě 2 and ai is a positive integer for all
0 ď i ď n ´ 1. Could it be the case that, for all positive integers k, spkq and spP pkqq have the
same parity?
(Belarus)
A8. For a positive integer n, an n-sequence is a sequence pa0 , . . . , an q of non-negative
integers satisfying the following condition: if i and j are non-negative integers with i ` j ď n,
then ai ` aj ď n and aai `aj “ ai`j .
Let f pnq be the number of n-sequences. Prove that there exist positive real numbers c1 , c2
and λ such that
c1 λn ă f pnq ă c2 λn
for all positive integers n.
(Canada)
4 Oslo, Norway, 6th–16th July 2022

Combinatorics
C1. A ˘1-sequence is a sequence of 2022 numbers a1 , . . . , a2022 , each equal to either `1 or
´1. Determine the largest C so that, for any ˘1-sequence, there exists an integer k and indices
1 ď t1 ă . . . ă tk ď 2022 so that ti`1 ´ ti ď 2 for all i, and
∣ ∣
∣ÿk ∣
∣ ati ∣ ě C.
∣ ∣
∣i“1 ∣

(Czech Republic)
C2. The Bank of Oslo issues coins made out of two types of metal: aluminium (denoted
A) and copper (denoted C). Morgane has n aluminium coins, and n copper coins, and arranges
her 2n coins in a row in some arbitrary initial order. Given a xed positive integer k ď 2n, she
repeatedly performs the following operation: identify the largest subsequence containing the
k-th coin from the left which consists of consecutive coins made of the same metal, and move
all coins in that subsequence to the left end of the row. For example, if n “ 4 and k “ 4, the
process starting from the conguration AACCCACA would be

AACCCACA Ñ CCCAAACA Ñ AAACCCCA Ñ CCCCAAAA Ñ ¨ ¨ ¨ .

Find all pairs pn, kq with 1 ď k ď 2n such that for every initial conguration, at some point
of the process there will be at most one aluminium coin adjacent to a copper coin.
(France)
C3. In each square of a garden shaped like a 2022 ˆ 2022 board, there is initially a tree
of height 0. A gardener and a lumberjack alternate turns playing the following game, with the
gardener taking the rst turn:

• The gardener chooses a square in the garden. Each tree on that square and all the
surrounding squares (of which there are at most eight) then becomes one unit taller.

• The lumberjack then chooses four dierent squares on the board. Each tree of positive
height on those squares then becomes one unit shorter.

We say that a tree is majestic if its height is at least 106 . Determine the largest number K
such that the gardener can ensure there are eventually K majestic trees on the board, no matter
how the lumberjack plays.
(Colombia)
C4.
Let n ą 3 be a positive integer. Suppose that n children are arranged in a circle, and n
coins are distributed between them (some children may have no coins). At every step, a child
with at least 2 coins may give 1 coin to each of their immediate neighbours on the right and
left. Determine all initial distributions of coins from which it is possible that, after a nite
number of steps, each child has exactly one coin.
(Israel)
Shortlisted problems 5

C5. Let m, n ě 2 be integers, let X be a set with n elements, and let X1 , X2 , . . . , Xm

be pairwise distinct non-empty, not necessary disjoint subsets of X. A function f : X Ñ
t1, 2, . . . , n ` 1u is called nice if there exists an index k such that
ÿ ÿ
f pxq ą f pxq for all i ‰ k.
xPXk xPXi

Prove that the number of nice functions is at least nn .

(Germany)
C6. Let n be a positive integer. We start with n piles of pebbles, each initially containing
a single pebble. One can perform moves of the following form: choose two piles, take an equal
number of pebbles from each pile and form a new pile out of these pebbles. For each positive
integer n, nd the smallest number of non-empty piles that one can obtain by performing a
nite sequence of moves of this form.
(Croatia)
C7. Lucy starts by writing s integer-valued 2022-tuples on a blackboard. After doing that,
she can take any two (not necessarily distinct) tuples v “ pv1 , . . . , v2022 q and w “ pw1 , . . . , w2022 q
that she has already written, and apply one of the following operations to obtain a new tuple:

v ` w “ pv1 ` w1 , . . . , v2022 ` w2022 q

v _ w “ pmaxpv1 , w1 q, . . . , maxpv2022 , w2022 qq

and then write this tuple on the blackboard.

It turns out that, in this way, Lucy can write any integer-valued 2022-tuple on the blackboard
after nitely many steps. What is the smallest possible number s of tuples that she initially
wrote?
(Czech Republic)
C8.
Alice lls the elds of an n ˆ n board with numbers from 1 to n2 , each number being used
exactly once. She then counts the total number of good paths on the board. A good path is a
sequence of elds of arbitrary length (including 1) such that:

(i) The rst eld in the sequence is one that is only adjacent to elds with larger numbers,

(ii) Each subsequent eld in the sequence is adjacent to the previous eld,

(iii) The numbers written on the elds in the sequence are in increasing order.

Two elds are considered adjacent if they share a common side. Find the smallest possible
number of good paths Alice can obtain, as a function of n.
(Serbia)
C9. Let Zě0 be the set of non-negative integers, and let f : Zě0 ˆ Zě0 Ñ Zě0 be a
bijection such that whenever f px1 , y1 q ą f px2 , y2 q, we have f px1 ` 1, y1 q ą f px2 ` 1, y2 q and
f px1 , y1 ` 1q ą f px2 , y2 ` 1q.
Let N be the number of pairs of integers px, yq, with 0 ď x, y ă 100, such that f px, yq is
odd. Find the smallest and largest possible value of N .
(U.S.A.)
6 Oslo, Norway, 6th–16th July 2022

Geometry
G1. Let ABCDE be a convex pentagon such that BC “ DE. Assume there is a point
T inside ABCDE with T B “ T D, T C “ T E and =T BA “ =AET . Let lines CD and CT
intersect line AB at points P and Q, respectively, and let lines CD and DT intersect line AE
at points R and S, respectively. Assume that points P, B, A, Q and R, E, A, S respectively, are
collinear and occur on their lines in this order. Prove that the points P , S, Q, R are concyclic.
(Slovakia)
G2. In the acute-angled triangle ABC, the point F is the foot of the altitude from A, and
P is a point on the segment AF . The lines through P parallel to AC and AB meet BC at D
and E, respectively. Points X ‰ A and Y ‰ A lie on the circles ABD and ACE, respectively,
such that DA “ DX and EA “ EY .
Prove that B, C, X and Y are concyclic.
(Netherlands)
G3. Let ABCD be a cyclic quadrilateral. Assume that the points Q, A, B, P are collinear
in this order, in such a way that the line AC is tangent to the circle ADQ, and the line BD is
tangent to the circle BCP . Let M and N be the midpoints of BC and AD, respectively. Prove
that the following three lines are concurrent: line CD, the tangent of circle AN Q at point A,
and the tangent to circle BM P at point B.
(Slovakia)
G4. Let ABC be an acute-angled triangle with AC ą AB, let O be its circumcentre, and
let D be a point on the segment BC. The line through D perpendicular to BC intersects the
lines AO, AC and AB at W , X and Y , respectively. The circumcircles of triangles AXY and
ABC intersect again at Z ‰ A.
Prove that if OW “ OD, then DZ is tangent to the circle AXY .
(United Kingdom)
G5. Let ABC be a triangle, and let `1 and `2 be two parallel lines. For i “ 1, 2, let `i
meet the lines BC, CA, and AB at Xi , Yi , and Zi , respectively. Suppose that the line through
Xi perpendicular to BC, the line through Yi perpendicular to CA, and nally the line through
Zi perpendicular to AB, determine a non-degenerate triangle ∆i .
Show that the circumcircles of ∆1 and ∆2 are tangent to each other.
(Vietnam)
G6. In an acute-angled triangle ABC, point H is the foot of the altitude from A. Let
P be a moving point such that the bisectors k and ` of angles P BC and P CB, respectively,
intersect each other on the line segment AH. Let k and AC meet at E, let ` and AB meet
at F , and let EF and AH meet at Q. Prove that, as P varies, the line P Q passes through a
xed point.
(Iran)
G7. Let ABC and A1 B 1 C 1 be two triangles having the same circumcircle ω, and the same
orthocentre H. Let Ω be the circumcircle of the triangle determined by the lines AA1 , BB 1
and CC 1 . Prove that H, the centre of ω, and the centre of Ω are collinear.
(Denmark)
G8. Let AA1 BCC 1 B 1 be a convex cyclic hexagon such that AC is tangent to the incircle
of the triangle A1 B 1 C 1 , and A1 C 1 is tangent to the incircle of the triangle ABC. Let the lines
AB and A1 B 1 meet at X and let the lines BC and B 1 C 1 meet at Y .
Prove that if XBY B 1 is a convex quadrilateral, then it has an incircle.
(Australia)
Shortlisted problems 7

Number Theory
N1. A number is called Norwegian if it has three distinct positive divisors whose sum is
equal to 2022. Determine the smallest Norwegian number.
(Note: The total number of positive divisors of a Norwegian number is allowed to be larger
than 3.)
(Cyprus)
N2. Find all positive integers n ą 2 such that
ˇ
ˇ ź
n! ˇˇ pp ` qq.
păqďn,
p,q primes

(Nigeria)
N3. Let a ą 1 be a positive integer, and let d ą 1 be a positive integer coprime to a. Let
x1 “ 1 and, for k ě 1, dene
#
xk ` d if a doesn’t divide xk ,
xk`1 “
xk {a if a divides xk .
Find the greatest positive integer n for which there exists an index k such that xk is divisible
by an .
(Croatia)
N4. Find all triples of positive integers pa, b, pq with p prime and
ap “ b! ` p.
(Belgium)
N5. For each 1 ď i ď 9 and T P N, dene di pT q to be the total number of times the digit
i appears when all the multiples of 1829 between 1 and T inclusive are written out in base 10.
Show that there are innitely many T P N such that there are precisely two distinct values
among d1 pT q, d2 pT q, . . . , d9 pT q.
(United Kingdom)
N6. Let Q be a set of prime numbers, not necessarily nite. For a positive integer n
consider its prime factorisation; dene ppnq to be the sum of all the exponents and qpnq to be
the sum of the exponents corresponding only to primes in Q. A positive integer n is called
special if ppnq ` ppn ` 1q and qpnq ` qpn ` 1q are both even integers. Prove that there is a
constant c ą 0 independent of the set Q such that for any positive integer N ą 100, the number
of special integers in r1, N s is at least cN .
(For example, if Q “ t3, 7u, then pp42q “ 3, qp42q “ 2, pp63q “ 3, qp63q “ 3, pp2022q “ 3,
qp2022q “ 1.)
(Costa Rica)
N7. Let k be a positive integer and let S be a nite set of odd prime numbers. Prove that
there is at most one way (modulo rotation and reection) to place the elements of S around a
circle such that the product of any two neighbors is of the form x2 ` x ` k for some positive
integer x.
(U.S.A.)
N8. Prove that 5n ´ 3n is not divisible by 2n ` 65 for any positive integer n.
(Belgium)
Shortlisted problems 3

Problems
Algebra
A1. Professor Oak is feeding his 100 Pokémon. Each Pokémon has a bowl whose capacity
is a positive real number of kilograms. These capacities are known to Professor Oak. The total
capacity of all the bowls is 100 kilograms. Professor Oak distributes 100 kilograms of food in
such a way that each Pokémon receives a non-negative integer number of kilograms of food
(which may be larger than the capacity of their bowl). The dissatisfaction level of a Pokémon
who received N kilograms of food and whose bowl has a capacity of C kilograms is equal to
|N ´ C|.
Find the smallest real number D such that, regardless of the capacities of the bowls, Pro-
fessor Oak can distribute the food in a way that the sum of the dissatisfaction levels over all
the 100 Pokémon is at most D.
(Ukraine)
A2. Let R be the set of real numbers. Let f : R Ñ R be a function such that

f px ` yqf px ´ yq ě f pxq2 ´ f pyq2

for every x, y P R. Assume that the inequality is strict for some x0 , y0 P R.

Prove that f pxq ě 0 for every x P R or f pxq ď 0 for every x P R.
(Malaysia)
A3. Let x1 , x2 , . . . , x2023 be distinct real positive numbers such that
d ˆ ˙
1 1 1
an “ px1 ` x2 ` ¨ ¨ ¨ ` xn q ` ` ¨¨¨ `
x1 x2 xn

is an integer for every n “ 1, 2, . . . , 2023. Prove that a2023 ě 3034.

(Netherlands)
A4. Let Rą0 be the set of positive real numbers. Determine all functions f : Rą0 Ñ Rą0
such that ` ˘ ` ˘
x f pxq ` f pyq ě f pf pxqq ` y f pyq
for every x, y P Rą0 .
(Belgium)
A5. Let a1 , a2 , . . . , a2023 be positive integers such that

• a1 , a2 , . . . , a2023 is a permutation of 1, 2, . . . , 2023, and

• |a1 ´ a2 |, |a2 ´ a3 |, . . . , |a2022 ´ a2023 | is a permutation of 1, 2, . . . , 2022.

` ˘
Prove that max a1 , a2023 ě 507.
(Australia)
4 Chiba, Japan, 2nd–13th July 2023

A6. Let k ě 2 be an integer. Determine all sequences of positive integers a1 , a2 , . . . for

which there exists a monic polynomial P of degree k with non-negative integer coecients such
that
P pan q “ an`1 an`2 ¨ ¨ ¨ an`k
for every integer n ě 1.
(Malaysia)
A7. Let N be a positive integer. Prove that there exist three permutations a1 , a2 , . . . , aN ;
b1 , b2 , . . . , bN ; and c1 , c2 , . . . , cN of 1, 2, . . . , N such that
∣? a ? ? ∣∣
∣ ak ` bk ` ck ´ 2 N ∣ ă 2023
∣

for every k “ 1, 2, . . . , N .
(China)
Shortlisted problems 5

Combinatorics
C1. Let m and n be positive integers greater than 1. In each unit square of an m ˆ n grid
lies a coin with its tail-side up. A move consists of the following steps:

1. select a 2 ˆ 2 square in the grid;

2. ip the coins in the top-left and bottom-right unit squares;

3. ip the coin in either the top-right or bottom-left unit square.

Determine all pairs pm, nq for which it is possible that every coin shows head-side up after a
nite number of moves.
(Thailand)
C2. Determine the maximal length L of a sequence a1 , . . . , aL of positive integers satisfying
both the following properties:

• every term in the sequence is less than or equal to 22023 , and

• there does not exist a consecutive subsequence ai , ai`1 , . . . , aj (where 1 ď i ď j ď L) with

a choice of signs si , si`1 , . . . , sj P t1, ´1u for which

si ai ` si`1 ai`1 ` ¨ ¨ ¨ ` sj aj “ 0.

(Czech Republic)
C3. Let n be a positive integer. We arrange 1 ` 2 ` ¨ ¨ ¨ ` n circles in a triangle with n
rows, such that the ith row contains exactly i circles. The following gure shows the case n “ 6.

n“6

In this triangle, a ninja-path is a sequence of circles obtained by repeatedly going from a

circle to one of the two circles directly below it. In terms of n, nd the largest value of k such
that if one circle from every row is coloured red, we can always nd a ninja-path in which at
least k of the circles are red.
(Netherlands)
C4. Let n ě 2 be a positive integer. Paul has a 1 ˆ n2 rectangular strip consisting of n2
unit squares, where the ith square is labelled with i for all 1 ď i ď n2 . He wishes to cut the
strip into several pieces, where each piece consists of a number of consecutive unit squares, and
then translate (without rotating or ipping) the pieces to obtain an n ˆ n square satisfying the
following property: if the unit square in the ith row and j th column is labelled with aij , then
aij ´ pi ` j ´ 1q is divisible by n.
Determine the smallest number of pieces Paul needs to make in order to accomplish this.
(U.S.A.)
6 Chiba, Japan, 2nd–13th July 2023

C5. Elisa has 2023 treasure chests, all of which are unlocked and empty at rst. Each day,
Elisa adds a new gem to one of the unlocked chests of her choice, and afterwards, a fairy acts
according to the following rules:

• if more than one chests are unlocked, it locks one of them, or

• if there is only one unlocked chest, it unlocks all the chests.

Given that this process goes on forever, prove that there is a constant C with the following
property: Elisa can ensure that the dierence between the numbers of gems in any two chests
never exceeds C, regardless of how the fairy chooses the chests to lock.
(Israel)
C6. Let N be a positive integer, and consider an N ˆ N grid. A right-down path is a
sequence of grid cells such that each cell is either one cell to the right of or one cell below the
previous cell in the sequence. A right-up path is a sequence of grid cells such that each cell is
either one cell to the right of or one cell above the previous cell in the sequence.
Prove that the cells of the N ˆ N grid cannot be partitioned into less than N right-down
or right-up paths. For example, the following partition of the 5 ˆ 5 grid uses 5 paths.

(Canada)
C7. The Imomi archipelago consists of n ě 2 islands. Between each pair of distinct islands
is a unique ferry line that runs in both directions, and each ferry line is operated by one of
k companies. It is known that if any one of the k companies closes all its ferry lines, then
it becomes impossible for a traveller, no matter where the traveller starts at, to visit all the
islands exactly once (in particular, not returning to the island the traveller started at).
Determine the maximal possible value of k in terms of n.
(Ukraine)
Shortlisted problems 7

Geometry
G1. Let ABCDE be a convex pentagon such that =ABC “ =AED “ 90˝ . Suppose
that the midpoint of CD is the circumcentre of triangle ABE. Let O be the circumcentre of
triangle ACD.
Prove that line AO passes through the midpoint of segment BE.
(Slovakia)
G2. Let ABC be a triangle with AC ą BC. Let ω be the circumcircle of triangle ABC
and let r be the radius of ω. Point P lies on segment AC such that BC “ CP and point S is
the foot of the perpendicular from P to line AB. Let ray BP intersect ω again at D and let Q
lie on line SP such that P Q “ r and S, P, Q lie on the line in that order. Finally, let the line
perpendicular to CQ from A intersect the line perpendicular to DQ from B at E.
Prove that E lies on ω.
(Iran)
G3. Let ABCD be a cyclic quadrilateral with =BAD ă =ADC. Let M be the midpoint
of the arc CD not containing A. Suppose there is a point P inside ABCD such that =ADB “
=CP D and =ADP “ =P CB.
Prove that lines AD, P M, BC are concurrent.
(Slovakia)
G4. Let ABC be an acute-angled triangle with AB ă AC. Denote its circumcircle by Ω
and denote the midpoint of arc CAB by S. Let the perpendicular from A to BC meet BS
and Ω at D and E ‰ A respectively. Let the line through D parallel to BC meet line BE at L
and denote the circumcircle of triangle BDL by ω. Let ω meet Ω again at P ‰ B.
Prove that the line tangent to ω at P , and line BS intersect on the internal bisector
of =BAC.
(Portugal)
G5. Let ABC be an acute-angled triangle with circumcircle ω and circumcentre O. Points
D ‰ B and E ‰ C lie on ω such that BD K AC and CE K AB. Let CO meet AB at X, and
BO meet AC at Y .
Prove that the circumcircles of triangles BXD and CY E have an intersection on line AO.
(Malaysia)
G6. Let ABC be an acute-angled triangle with circumcircle ω. A circle Γ is internally
tangent to ω at A and also tangent to BC at D. Let AB and AC intersect Γ at P and Q
respectively. Let M and N be points on line BC such that B is the midpoint of DM and
C is the midpoint of DN . Lines M P and N Q meet at K and intersect Γ again at I and J
respectively. The ray KA meets the circumcircle of triangle IJK at X ‰ K.
Prove that =BXP “ =CXQ.
(United Kingdom)
8 Chiba, Japan, 2nd–13th July 2023

G7. Let ABC be an acute, scalene triangle with orthocentre H. Let `a be the line through
the reection of B with respect to CH and the reection of C with respect to BH. Lines `b
and `c are dened similarly. Suppose lines `a , `b , and `c determine a triangle T .
Prove that the orthocentre of T , the circumcentre of T and H are collinear.
(Ukraine)
G8. Let ABC be an equilateral triangle. Points A1 , B1 , C1 lie inside triangle ABC such
that triangle A1 B1 C1 is scalene, BA1 “ A1 C, CB1 “ B1 A, AC1 “ C1 B and

=BA1 C ` =CB1 A ` =AC1 B “ 480˝ .

Lines BC1 and CB1 intersect at A2 ; lines CA1 and AC1 intersect at B2 ; and lines AB1 and
BA1 intersect at C2 .
Prove that the circumcircles of triangles AA1 A2 , BB1 B2 , CC1 C2 have two common points.
(U.S.A.)
Shortlisted problems 9

Number Theory
N1. Determine all positive, composite integers n that satisfy the following property: if
the positive divisors of n are 1 “ d1 ă d2 ă ¨ ¨ ¨ ă dk “ n, then di divides di`1 ` di`2 for every
1 ď i ď k ´ 2.
(Colombia)
N2. Determine all pairs pa, pq of positive integers with p prime such that pa `a4 is a perfect
square.
(Bangladesh)
N3. For positive integers n and k ě 2 dene Ek pnq as the greatest exponent r such that
k r divides n!. Prove that there are innitely many n such that E10 pnq ą E9 pnq and innitely
many m such that E10 pmq ă E9 pmq.
(Brazil)
N4. Let a1 , a2 , . . . , an , b1 , b2 , . . . , bn be 2n positive integers such that the n ` 1 products
a1 a2 a3 ¨ ¨ ¨ an ,
b1 a2 a3 ¨ ¨ ¨ an ,
b1 b2 a3 ¨ ¨ ¨ an ,
..
.
b1 b2 b3 ¨ ¨ ¨ bn
form a strictly increasing arithmetic progression in that order. Determine the smallest positive
integer that could be the common dierence of such an arithmetic progression.
(Canada)
N5. Let a1 ă a2 ă a3 ă ¨ ¨ ¨ be positive integers such that ak`1 divides 2pa1 ` a2 ` ¨ ¨ ¨ ` ak q
for every k ě 1. Suppose that for innitely many primes p, there exists k such that p divides
ak . Prove that for every positive integer n, there exists k such that n divides ak .
(Netherlands)
N6. A sequence of integers a0 , a1 , a2 , . . . is called kawaii, if a0 “ 0, a1 “ 1, and, for any
positive integer n, we have
pan`1 ´ 3an ` 2an´1 qpan`1 ´ 4an ` 3an´1 q “ 0.
An integer is called kawaii if it belongs to a kawaii sequence.
Suppose that two consecutive positive integers m and m ` 1 are both kawaii (not necessarily
belonging to the same kawaii sequence). Prove that 3 divides m, and that m{3 is kawaii.
(China)
N7. Let a, b, c, d be positive integers satisfying
ab cd pa ` bqpc ` dq
` “ .
a`b c`d a`b`c`d
Determine all possible values of a ` b ` c ` d.
(Netherlands)
N8. Let Zą0 be the set of positive integers. Determine all functions f : Zą0 Ñ Zą0 such
that
f bf paq pa ` 1q “ pa ` 1qf pbq
holds for all a, b P Zą0 , where f k pnq “ f pf p¨ ¨ ¨ f pnq ¨ ¨ ¨ qq denotes the composition of f with
itself k times.
(Taiwan)