The 35th Nordic Mathematical Contest

Friday, 16 April 2021

Time allowed: 4 hours. Each problem is worth 7 points.

Only writing and drawing tools are allowed.

Problem 1. On a blackboard a finite number of integers greater than one

are written. Every minute, Nordi additionally writes on the blackboard the
smallest positive integer greater than every other integer on the blackboard and
not divisible by any of the numbers on the blackboard. Show that from some
point onwards Nordi only writes primes on the blackboard.

Problem 2. Find all functions f : R → R satisfying that for every x ∈ R,

f (x(1 + |x|)) ≤ x ≤ f (x)(1 + |f (x)|).

Problem 3. Let n be a positive integer. Alice and Bob play the following
game. First, Alice picks n + 1 subsets A1 , . . . , An+1 of {1, . . . , 2n } each of size
2n−1 . Second, Bob picks n + 1 arbitrary integers a1 , . . . , an+1 . Finally, Alice
picks an integer t. Bob wins if there exists an integer 1 ≤ i ≤ n + 1 and s ∈ Ai
such that s + ai ≡ t (mod 2n ). Otherwise, Alice wins.
Find all values of n where Alice has a winning strategy.

Problem 4. Let A, B, C and D be points on the circle ω such that ABCD is

a convex quadrilateral. Suppose that AB and CD intersect at a point E such
that A is between B and E and that BD and AC intersect at a point F . Let
X 6= D be the point on ω such that DX and EF are parallel. Let Y be the
reflection of D through EF and suppose that Y is inside the circle ω.
Show that A, X, and Y are collinear.

1
Solutions
Problem 1. Let a be the largest integer initially written on the blackboard.
Furthermore, denote by an the integer written by Nordi on the blackboard after
n minutes.
Suppose that p > a is prime. If Nordi never writes p on the blackboard,
there exist an < p < an+1 since a1 , a2 , . . . is a strictly increasing sequence of
positive integers. However, p is a prime greater than an , so p is not divisible by
any of the integers written on the blackboard after n minutes. This contradicts
that an+1 is the smallest integer greater than an which is not divisible by any
of the integers on the blackboard after n minutes. It follows that every prime
greater than a is written on the blackboard.
It follows that every non-prime written on the blackboard contains only
prime factors less than or equal to a. Assume for contradiction that Nordi
writes infinitely many integers on the blackboard that are not integer. Let
b1 , b2 , . . . be these integers, and let p1 , . . . , pr be the primes less than or equal
to a. It follows that for every n ∈ N, we can write
e e
bn = p1n,1 p2n,2 · · · pern,r ,

where en,1 , . . . , en,r are non-negative integers.

Note that for any infinite sequence of non-negative integers, we may find an
infinite subsequence that is weakly increasing: If the sequence is bounded, some
integer occurs infinitely many times, otherwise we may find an infinite strictly
increasing subsequence.
Consider now the sequence

(e1,1 , e1,2 , . . . , e1,r ), (e2,1 , e2,2 , . . . , e2,r ), . . . .

For the first coordinate, we may find an infinite weakly increasing subsequence
en1 ,1 , en2 ,1 , . . . , eni ,1 , . . . . Considering the sequence en1 ,2 , en2 ,2 , . . . , we may now
again find a weakly increasing subsequence en01 ,2 , en02 ,2 , . . . . In this manner, we
may find indices m1 < m2 < . . . such that for every 1 ≤ i ≤ r, em1 ,i , em2 ,i , . . .
is a weakly increasing sequence. However, then bm1 | bm2 | bm3 | . . . . A
contradiction. Thus, Nordi only writes finitely many integers on the blackboard
that are not primes.

Problem 2. With g(x) = x(1 + |x|) we want that f (g(x)) ≤ x ≤ g(f (x)) for
all x. The solution only uses that g is strictly increasing and surjective with an
inverse which is also strictly increasing.
Notice that the inverse function to such g gives a solution f = g −1 since
x ≤ x ≤ x is true for all x ∈ R.
For uniqueness take any x and let y = g −1 (x). Then g(f (x)) ≥ x. On the
other hand f (g(y)) ≤ y and hence g(f (x)) = g(f (g(y))) ≤ g(y) = x where we
used that g is increasing in the inequality. In other words g(f (x)) = x for all x
and hence f (x) = g −1 (x).

2
 Solving y(1 + |y|) = x we get explicitly for f that
( √
−1+ 1+4x
2 ,x ≥ 0
f (x) = 1−√1−4x
2 , x ≤0

Problem 3. Bob has a winning strategy for every n ∈ N. Initially, note that
Bob wins if and only if he can “shift” the sets A1 , . . . , An+1 modulo 2n such
that they together cover every residue class. For a set of integers C ⊂ Z and
r ∈ N, let C + r be the set {c + r | c ∈ C}, and let (C mod r) denote the subset
of {0, 1, . . . , r − 1} corresponding to the residue classes modulo r represented by
the members of C.
Let A1 , . . . , An+1 be the subsets of {1, . . . , 2n } chosen by Alice. Bob now
proceeds as follows. Suppose some choice of a1 , . . . , an+1 is given, let B0 =
{0, 1, 2, . . . , 2n − 1}, and for 1 ≤ i ≤ n + 1, let Bi = Bi−1 \ ((Ai + ai ) mod 2n ).
Note that if Alice chooses t such that the residue class of t modulo 2n is not
contained in Bj for some 1 ≤ j ≤ n + 1, then Bob can choose an i ≤ j and find
s ∈ Ai such that s + ai ≡ t (mod 2n ). Thus, Bob wins if he can ensure that
Bn+1 = ∅.
To that end, we show that Bob can choose a1 , . . . , an+1 such that |Bi | ≤
|Bi−1 | /2 for every 1 ≤ i ≤ n. If this holds, |Bn+1 | ≤ 2n−(n+1) = 1/2, and
the conclusion follows. Consider some 1 ≤ i ≤ n + 1. We wish to find ai such
that (Ai + ai ) mod 2n contains at least half of the elements of Bi−1 . Note that
(Ai + b) mod 2n contains 2n−1 elements and consider the sum
n
2X −1
S := |((Ai + a) mod 2n ) ∩ Bi−1 | .
a=0

For each b ∈ Bi−1 , there are exactly 2n−1 choices of 0 ≤ a < 2n such that
b is contained in ((Ai + a) mod 2n ), one for each element of Ai . It follows
that S = 2n−1 · |Bi−1 |. Since there are only 2n summands in S, at least one
must have magnitude at least |Bi−1 | /2. Thus, there is some 0 ≤ a < 2n with
|((Ai + a) mod 2n ) ∩ Bi−1 | ≥ |Bi−1 | /2, so choosing ai = a, Bob ensures that
|Bi | = |Bi−1 \ ((Ai + ai ) mod 2n )| ≤ |Bi−1 | /2.

Problem 4. It can be difficult to find out what to do, but the key is to show
that AY F E is cyclic. The motivation for this is that we want to show that
∠BAY = ∠BAX. But ∠BAX = ∠BDX since BXDA is cyclic, and ∠BDX =
∠F DX = ∠DF E since DX and EF are parallel, and ∠DF E = ∠EF Y since
Y is the reflection of D through EF , so ∠BAX = ∠EF Y . Hence we only need
to show that ∠BAY = 180◦ − ∠EAY = ∠EF Y , and this is true if and only if
AY F E is cyclic. The trick is to show that AY F E is cyclic in a different way,
i.e. by showing that ∠EAF = ∠EY F . This follows from ABCD being cyclic
since then ∠EAF = 180◦ − ∠CAB = 180◦ − ∠CDB = ∠F DE = ∠EY F . The
last equality follows from Y being a reflection.

3
 Note: We have shown the claim for just one configuration, the one in the
sketch. The other cases follow from the same idea, but one need to chase angles
in a different way. Using oriented angles one can take case of all possibilities.