Solution to IMO 2015 shortlisted problems.

Anzo Teh

25 June 2017

1 Algebra
1. A2.Determine all functions f : Z → Z with the property that

f (x − f (y)) = f (f (x)) − f (y) − 1

holds for all x, y ∈ Z.

Solution. Plugging y = f (x) yields f (x − f (f (x))) = −1, meaning that -1 is in the range
of f . Take y such that f (y) = −1 we have f (x + 1) = f (f (x)). For the case where f is
injective, we must have f (x) = x + 1, and this function obviously works with both sides
equal x − y.
Now, let f not be injective, and let f (x) = f (z) for some x, z ∈ R. Then take y such that
f (y) = −1 we have f (x + 1) = f (f (x)) = f (f (z)) = f (z + 1). This means the function is
periodic for sufficiently large domain (i.e. ≥ x1 ). Let M and m be real numbers ≥ x such
that the numbers f (M ) and f (m) are the maximum and minimum numbers in the period,
respectively. Plug x = M − 1 yields R.H.S. as f (f (M − 1)) − f (y) − 1 = f (M ) − f (y) − 1,
and with L.H.S. at most f (M ) we have f (y) ≥ −1 for any real y (if x − f (y) < x1
then we can change x to M − 1 + kc where c is the length of functional period, so that
f (M ) = f (M + kc) and k sufficiently large positive integer). A similar substitution yields
R.H.S. as f (m) − f (y) − 1 and L.H.S. at least f (m), so f (y) ≤ −1. Combining both yields
f ≡ −1, a constant, and this satisfies the functional equation too.

2. A3. Let n be a fixed positive integer. Find the maximum possible value of
X
(s − r − n)xr xs ,
1≤r<s≤2n

where −1 ≤ xi ≤ 1 for all i = 1, · · · , 2n.

Solution. Let x = x1 and
X fix other indices, we know that this is a linear
X function in x
(with constant term (j − i − n)xi xj and coefficient of x as (i − 1 − n)xi
2≤i<j≤2n 2≤i<2n
and thereore the maximum value can be attained when x = 1 or -1. We can then safely
assume that | xi |= 1, ∀i ∈ [1, 2n].
Now let p, q be the number of 1’s and -1’s in the sequence respectively, with p + q = 2n.
W.L.O.G. let p ≤ q (replacing xi by −xi for all i yields the same sum). We further name
a1 < a2 < · · · < ap and bX
1 < b2 < · · · < bq such X
that xai = 1 and xbi X= −1. Now, the
required sum becomes (aj − ai − n) + (bj − bi − n) − (|aj − bi | − n)
1≤i<j≤p 1≤i<j≤q
X X X X
(|aj −bi |) −n( p2 + 2q −pq) = 2(



= (aj −ai ) + (bj −bi ) − (aj −ai )
1≤i<j≤p 1≤i<j≤q 1≤i<j≤p

1
 X X
2n 2n p+q p q






+ (bj − bi )) − (s − r) −n( 2 − 2pq), since 2 = 2 = 2 + 2 + pq
1≤i<j≤q 1≤r<s≤2n
X X X X
and (s − r)= (aj − ai ) + (bj − bi ) + (|aj − bi |). The aim is
1≤r<s≤2n 1≤i<j≤p 1≤i<j≤q
X X
therefore to maximize (aj − ai ) + (bj − bi ) + pqn.
X
Telescoping the terms we know that (aj − ai ) = (a2 − a1 ) + (a3 − a2 ) + · · · + (ap −
ap−1 ) + (a3 − a1 ) + (a4 − a2 ) + · · · + (ap − ap−2 ) + · · · + (ap − a1 ) = pi=1 ((i − 1) − (p − i))ai =
P
Xp X Xq
(2i − p − 1)ai . Similarly, (bj − bi ) = (2i − q − 1)bi . Since {ai } ∪ {bj } = [1, 2n], by
i=1 i=1
rearranging inequality, for fixed p, q the maximum is attained when the terms 1, 2, · · · , 2n
have coefficient −(q − 1), −(q − 3), · · · − (p + 1), −(p − 1), −(p − 1), · · · + (p − 1), +(p −
1), +(p + 1), · · · + (q − 1) (basically, the weightage k appears two times if |k| < p and k 6= 0,
and one time otherwise.) (Remember that p ≡ q (mod 2)).
X X
Now we will prove that the maximum of (aj − ai ) + (bj − bi ) + pqn occurs iff
{p, q} = {n, n} or {n − 1, n + 1}. For p = q = n we have pqn as n3 and the coefficient (or
weightage) of 1, 2, · · · 2n as −(n−1), −(n−1), −(n−3), −(n−3), · · ·+(n−1), +(n−1) while
for the second case we have pqn as n(n − 1)(n + 1) (i.e. n less than the first case) and he
coefficients as −n, −(n−2), −(n−2), −(n−4), −(n−4), · · · (n−2), (n−2), n. The difference
of coefficient between this and the first case will therefore be −1, +1, −1, +1, · · · − 1, +1,
from which we know that the resulting difference between the second and the first case is
−1 + 2 − 3 + 4 · · · − (2n − 1) + 2n = n. (i.e. n more than the first case). Hence, the sum in
these two cases are equal. For other p < n − 1, we split into two cases. For p ≡ n (mod 2),
subtracting the coefficients −(q − 1), −(q − 3), · · · − (p + 1), −(p − 1), −(p − 1), · · · + (p −
1), +(p−1), +(p+1), · · ·+(q−1) by −(n−1), −(n−1), −(n−3), −(n−3), · · ·+(n−1), +(n−
1) yields −(q −n), −(q −n−2), −(q −n−2), · · · 0, 0, 0, · · ·+(q −n−2), +(q −n−2), +(q −n)
so after multplying by 1, 2, · · · 2n and considering the difference n(pq − n2 ) = −n(q − n)2
(since p + q = 2n) and the difference is now (q − n)(2n − 1) + (q − n − 2)(2n − 3) + (q − n −
2)(2n − 5) + · · · − n(q − n)2 < 2n((q − n) + 2(q − n − 2) + 2(q − n − 4) + · · · + 2(2)) − n(q −
n)2 =2n(q − n + 4 · q−n−1 2 · q−n 2
2 ) − n(q − n) = 0. If p ≡ n − 1 mod 2 then use the same
weightage to subtract −n, −(n−2), −(n−2), −(n−4), −(n−4), · · · (n−2), (n−2), n we get
−(q −1−n), −(q −1−n), −(q −3−n), −(q −3−n), · · · , 0, 0, 0, · · ·+(q −1−n), +(q −1−n).
The difference is (q − 1 − n)(2n − 1) + (q − 1 − n)(2n − 3) + · · · − n((q − n)2 − 1) <
2(2n−1)(2+4+· · ·+(q−1−n))−n((q−n)2 −1)= 2(2n−1) q−n−1 2 · q−n+1
2 −n((q−n)2 −1) <
2
n(q − n − 1)(q + n − 1) − n((q − n) − 1) = 0. Summing up, we know that for other
p, the resulting sum is smaller so we can safely assume that p = q = n. If we let
x1 = x3 = · · · = x2n−1 = 1 and x2 = x4 · · · = x2n = −1 then obviously, ai = 2i − 1
and bi = 2i, so they have the same weightage 2i − n − 1. This means the equality case is
attained here.
To compute the sum, notice that for each k ∈ [1, 2n − 1] there are exactly 2n − k ordered
pairs (r, s) with s − r = k and 1 ≤ r, s ≤ 2n. In addition, r + s ≡ k (mod 2) for those pairs
satifsying this property, hence xr xs = (−1)r+s = −1k . This means our desired maximum
2n−1
X
sum now becomes (−1)k (k − n)(2n − k). Ignoring the case where k = n (which gives
k=1
(−1)k (k − n)(2n − k) = 0 anyway) and pairing k with 2n − k (1 ≤ k ≤ 2n − 1) gives
(−1)k (k−n)(2n−k)+(−1)2n−k (n−k)k = (−1)k (n−k)(2k−2n) = 2(−1)k+1 (n−k)2 . Thus
our sum now becomes 2((n−1)2 −(n−2)2 +· · ·+(−1)n−1 (12 )) = 2((n−1)+(n−2)+· · ·+1)

2
 = n(n − 1).

3. A4/IMO 5. Let R be the set of real numbers. Determine all functions f : R → R that
satisfy the equation

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

for all real numbers x and y.

Solution. Plugging x = y = 0 into the original equation gives f (f (0)) = 0, so if f (0) = c
then f (c) = 0. Plugging x = c, y = 0 yields f (f (c)) + f (0) = f (c) + cf (0), or c + c = c2 ,
yielding c = 0, 2. When y = 1, f (x + f (x + 1)) = x + f (x + 1), so x + f (x + 1) is a
fixed point of f at all times (1). Let x = 0 and y be a fixed point, then y + f (0) =
f (f (y)) + f (0) = f (y) + yf (0) = y + yf (0). In other words, (y − 1)f (0) = 0 so if f (0) = 2,
then y = 1, i.e. 1 is the only fixed point of f . This means x + f (x + 1) ≡ 1 = x − 1 + f (x),
yielding f (x) = 2 − x. This function satisfies the equation as f (x + f (x + y)) + f (xy) =
2 − (x + (2 − x − y)) + 2 − xy = 2 + y − xy = x + 2 − x − y + 2y − xy = x + f (x + y) + yf (x).
If f (0) = 0, we show that f (x) ≡ x. when x = −1, −1 = −1 + 0 = −1 + f (−1 + 1) is
a fixed point, too. When x = 1, y = −1, f (1) + f (−1) = 1 + f (0) − f (1), or 2f (1) = 2
so f (1) = 1. Now plugging y = 0 into the original equation yields x + f (x) is a fixed
point, because f (xy) = yf (x) = 0 (2). We show that x + n + f (x) is a fixed point of f ,
∀n ∈ Z≥1 (3). Indeed, if z and z + 1 are both fixed point of f , then plugging x = 1 and
y = z we have LHS= f (1 + f (y + 1)) + f (y) = f (1 + y + 1) + y = f (y + 2) + y while RHS
is 1 + f (1 + y) + yf (1) = 1 + 1 + y + 1 + y. With RHS=LHS, f (y + 2) = y + 2. Doing this
repeatedly yields y + 3, y + 4, · · · fixed points of f . Now plug z = x − 1 + f (x), any x. By
(1), z is a fixed point and z + 1 = x + f (x) is a fixed point by (2), too. We conclude that
we established (3). In particular, n = 1 yields x + 1 + f (x), or x + f (x − 1) fixed points
(∀x ∈ R), so plugging y = −1 yields f (x + f (x − 1)) + f (−x) = x + f (x − 1) − f (x), or
f (x) = −f (x). (4)
Finally, replacing x by −x and y by −y in the problem yields −x + f (−x − y)=−x − f (x +
y) = −(x + f (x + y) by (4), so by (4) again we have f (−x + f (−x − y)) = −f (x + f (x + y)).
−yf (−x) = yf (x), so −f (x + f (x + y)) + f (xy) = −(x + f (x + y)) + yf (x). Adding this
LHS to the original equation, and the RHS to the original equation, and equating them,
we have 2f (xy) = 2yf (x) or f (xy) = yf (x). In particular, f (y) = yf (1) = y when x = 1,
an this function obiously satisfies the problem condition. Q.E.D.

2 Combinatorics
1. 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 left and right bulldozer confront each other, the larger
bulldozer pushes the smaller one off the road. On the other hand, bulldozers are quite
unprotected at their rears; so, if a bulldozer reaches the rear-end of another one, the first
one pushes the second one off the road, regardless of their sizes.
Let A and B be two towns, with B 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 off all bulldozers it meets.
Similarly town B can sweep town A away if the left bulldozer of B can move over to A
pushing off all bulldozers of all towns on its way.

3
 Prove that there is exactly one town that cannot be swept away by any other one.
Solution. We induct on the n, the number of towns. Let Ti , Li , Ri be town i (counted
from the left, so T1 is leftmost and Tn is rightmost), left bulldozer of town i and right
bulldozer of town i, respectively, ∀i ∈ [1, n]. For n = 1 there is nothing to prove; for
n = 2, T2 is swept ⇔ R1 > L2 ⇔ T1 isn’t swept.
By induction hypothesis we can assume that there is a unique town Ts that is not swept
when there are n towns, and add a town Tn+1 on the right. Obviously, there are no way
for Ri and Lj to reach Ts , ∀i ∈ [1, s−1], ∀j ∈ [s+1, n]. We show that exactly one of Ts and
Tn+1 will be swept. Indeed, denote M such that RM = max{Ri | i ∈ [s, n]}, meaning that
RM can sweep Tk , ∀k ∈ [M + 1, n]. If RM > Ln+1 , then after sweeping Tn , RM can sweep
Tn+1 but Ln+1 can’t sweep TM , so it can’t sweep Ts (since s ≤ M ). By our hypothesis no
other bulldozer can sweep Ts so here, Tn+1 is swept but not Ts . Conversely, if Ln+1 > RM ,
then Ln+1 can sweep Tn , Tn−1 , · · · , TM , · · · , Ts . No single town Ti , ∀i ∈ [s, n] can sweep
Tn+1 and by the second sentence of this paragraph, no town Ti , ∀i ∈ [1, s − 1] can sweep
Tn+1 . Hene Ts can be swept, but not Tn+1 .

2. C2/IMO 1. We say that a finite set S of points in the plane is balanced if, for any two
different points A and B in S, there is a point C in S such that AC = BC. We say that
S is centre-free if for any three different points A, B and C in S, there is no points P in
S such that P A = P B = P C.
(a) Show that for all integers n ≥ 3, there exists a balanced set consisting of n points.
(b) Determine all integers n ≥ 3 for which there exists a balanced centre-free set consisting
of n points.
Solution. For n odd, taking A1 A2 · · · An a regular n-gon yields that the perpendicular
bisector of Ai Aj passes through A i+j for i + j even, or A i+j+n for i + j odd (indices taken
2 2
modulo n). This configuration is therefore balanced, and since P with P Ai = P Aj = P Ak
implies P is the centre of the polygon (i.e. P 6= Ai , ∀ ∈ [1, n]), this configuration is also
centre-free.
Now, for even n, consider a circle with centre O and vertices A, B, C such that A, B, C
lie on this circle in that order and that triangles AOB and BOC are both equlateral.
Obviously, the perpendicular bisector of any point on the circle pass through O, and the
perpendicular bisectors of OA, OB, OC pass through B, C, B, respectively. Hence OABC
is balanced. Now we add two points X, Y on the circumfence at a time, such that X, Y
do not overlap the previous points and XOY equilateral. O is equidistant from any point
on the circle, so we only need to consider lines XO, Y O. However, their perpendicular
bisectors pass through Y, X respectively (so the configuration is balanced too).
Finally, if a configuration of n points (A1 , A2 , · · · , An ) is centre-free, then we denote f (i, j)
(i 6= j) such that Af (i,j) is equidistant from Ai and Aj (if there are more than one such
point we take this f arbitrarily). Now f (i, j) 6∈ {i, j} and f (i, j) 6= f (i, k) if j 6= k
(otherwise, Af (i,j) is equidistant from Ai , Aj , Ak , contradiction. Therefore, for fixed i,
{f (i, j)|j ∈ [1, n]\{i}} = {j|j ∈ [1, n]\{i}}. Summing this for all i entails that we counted
each f (i, j) twice, and for each number k, k is in n − 1 of the sets {j|j ∈ [1, n]\{i}},
i = 1, 2, · · · n. Therefore, for each k ∈ [1, n] there are n−1 2 unordered paris of i, j for which
f (i, j)=Ak . Therefore n is odd. (Answer for (b): all odd n).

3. C3. For a finite set A of positive integers, a partition of A into two disjoint nonempty
subsets A1 and A2 is good if the least common multiple of the elements in A1 is equal to

4
 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.
Solution. The largest element in A1 cannot be greater than the smallest element in
A2 , so if we sort the numbers in a1 < a2 < · · · < an then A1 ={a1 , a2 , · · · , ai } for some
i ∈ [1, n] and A2 = {ai+1 , ai+2 , · · · , an }. Also, any element in A1 must divide any element
in A2 .
Denote k-partition as the partition of the set in A1 and A2 s.t. A1 = {a1 , a2 , · · · , ak }
and A2 = {ak+1 , ak+2 , · · · , an }. Also denote the LCM and GCD of this k-partition as the
LCM of A1 and GCD of A2 , respectively. Suppose also that k −1-partition and k-partition
are both good. We show that 3 ≤ k ≤ n − 2, and that k + 1-partition and k − 2-partition
cannot be good. Indeed, every element in {a1 , a2 , · · · , ak−1 } divides {ak , ak+1 , · · · , an }
and every element in {a1 , a2 , · · · , ak } divides {ak+1 , ak+2 , · · · , an }. This entails the fact
that ak is a divisor of ak+1 , ak+2 , · · · , an and multiple of a1 , a2 , · · · , ak−1 . This means the
GCD of k − 1-partition is ak , (so same goes for the LCM of this partition) and the LCM
of k-partition is also ak (so same goes for the GCD of this partition). If k = 2 then the
LCM of 1-partition is a2 . However, A1 = {a1 }, contradiction. Similarly, k cannot be
n − 1 as well. Consider k + 1-partition. Now in A1 , ak+1 is obviously a multiple of every
other element (by hypothesis above) so the LCM is ak+1 . However, since the GCD of
k-partition is ak , there exists element ai (i > k + 1) where ak+1 - ai , so the GCD of this
k + 1-partition cannot be ak+1 , and k + 1-partition is not good. Similarly, k − 2-partition
is not good.
Finally, denote 1 ≤ x1 , x2 , · · · xm ≤ n − 1 be all indices such that xi -partition is not
good. From above, x1 ≤ 2 and xm ≥ n − 2, while xi+1 − xi ≤ 3, ∀i ∈ [1, m]. Notice,
also, that 2015=n − 1 − m. This means n − 2 ≤ xm ≤ x1 + 3(m − 1) ≤ 2 + 3(m − 1), so
n ≤ 3m+1 = 3(n−1−2015)+1 = 3n−6047. We have 2n ≥ 6047, or n ≥ 3024 since n ∈ N.
This can be achieved by taking a3i+1 = 2i+1 · 3i , a3i+2 = 2i · 3i+1 , a3i+3 = 2i+1 · 3i+1 ,
∀i ∈ [0, 1007]. where a 3i + 2-partition will give both LCM and GCD of 2i+1 · 3i+1
(∀i ∈ [0, 1007]) and a 3i + 3-partition will give both LCM and GCD of 2i+1 · 3i+1 .

4. C5/IMO 6. The sequence a1 , a2 , . . . of integers satisfies the conditions:

(i) 1 ≤ aj ≤ 2015 for all j ≥ 1, (ii) k + ak 6= ` + a` for all 1 ≤ k < `.
Prove that there exist two positive integers b and N for which

n
X
(aj − b) ≤ 10072
j=m+1

for all integers m and n such that n > m ≥ N .

Solution. Denote bn as an + n, and we know that bi is distinct for every b. Let x1 < x2 <
· · · < xk be first k numbers such that bi 6= aj , ∀i ≥ 1, ∀1 ≤ j ≤ k. It follows that there
are exactly xk − k such i’s such that bi < xk (1). If k > 2015, then from the fact n < bn ≤
n + 2015 we know that for i ≤ xk − k, bi ≤ i + 2015 ≤ xk − k + 2015 < xk . Therefore,
b1 , b2 , · · · , bxk −k ≤ xk so from point 1, {b1 , b2 , · · · bxk −k } = N ∩ [1, xk ]\{xi | 1 ≤ i ≤ k}.
Now bxk −k+1 ≥ xk + 1, and axk −k+1 = bxk −k+1 − (xk − k + 1) ≥ xk + 1 − (xk − k + 1) =
k > 2015, contradiction. Therefore k is finite (at least 1, since bn > 1 for all n.
We show that b = k and N = xk satisfies the conclusion we want to prove. Now, we can
any N > xk , there are exactly N − k indices i such that bi ≤ N . (2)
further assert that for P
Denote by Sn the sum ni=1 bi , the sum of elements in the set Bn = {bi | 1 ≤ k ≤ n}. Now,

5
 Pn
− b) is precisely Sn − Sm − nj=m+1 j − (n − m)b. We consider Sn , in general,
P
j=m+1 (aj
and prove that Tn ≤ Sn ≤ Tn + (k − 1)(2015 − k), where Tn is taken as n+k
P Pk
i=1 i − j=1 xk ,
the elements in the set Cn = {1, 2, · · · , n + k}\{xi | 1 ≤ i ≤ k}. This is the n smallest
possible sequence that appears in set {b1 , b2 , · · · } so Sn ≥ Tn follows from here.
Denote by X 0 the set containing all elements not in set X. To prove the right inequality,
from point 1.1 we know that if i ∈ Bn ∩ Cn0 , then n + k + 1 ≤ i ≤ n + 2015 and
| Bn ∩ Cn0 |≤ 2015 − k; if j ∈ Cn ∩ Bn0 then n + 2 ≤ i ≤ n + k. and | Cn ∩ Bn0 |≤ k − 1. But
since | Bn ∩ Cn0 |=| Cn ∩ Bn0 | we must have this number at most p = min(k − 1, 2015 − k).
Now, we have Sn − Tn =sum of elements in Bn ∩ Cn0 -sum of elements in Cn ∩ Bn0 ≤
(n + 2015) + (n + 2014) · · · + (n + 2016 − p) − ((n + 2) + (n + 3) + · · · + (n + p + 1)) =
2013 + 2011 + · · · + (2013 − 2(p − 1)) = p2 · (4028 − 2p)=p(2014 − p), which is precisely
(k − 1)(2015 − k).
(m + k + 2) + · · · + (n + k)=k(n − m) + nj=m+1 j, so
P
Finally,
Pn Tn − Tm =(m + k + 1) P+n
j=m+1 (aj − k) = Sn − Sm − j=m+1 j − (n − m)k = (Sn − Tn ) − (Sm − Tm ). From above,
0 ≤ Sn −Tn , Sm −Tm ≤ (k −1)(2015−k), so −(k −1)(2015−k) ≤ (Sn −Tn )−(Sm −Tm ) ≤
(k − 1)(2015 − k). Now (k − 1)(2015 − k) ≤ ( k−1+2015−k
2 )2 = 10072 by AM-GM inequality.
Q.E.D.

3 Geometry
1. 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.
Solution. Denote P as AC ∩ HG. Now IP = P H, from H beign the orthocentre
∠ACH = ∠HBA, from HG k AB we have ∠HBA = ∠BHG, from CH ⊥ AB, HG
and BC ⊥ AH, BG we have ∠CHG = ∠CBG = 90◦ , so CHBG is cyclic and ∠BHG =
IP
∠BCG. Moreover 4IP J ∼ 4CP G. So IJ = CG · CP = CG · PCPH
= CG · sin ∠P HC =
CG · sin ∠ACH = CG · sin ∠HBA = CG · sin ∠BHG = CG · sin ∠BCG = BG = AH.

2. G2/IMO 4. Triangle ABC has circumcircle Ω and circumcenter O. A circle Γ with

center A intersects the segment BC at points D and E, such that B, D, E, and C are all
different and lie on line BC in this order. Let F and G be the points of intersection of Γ
and Ω, such that A, F , B, C, and G lie on Ω in this order. Let K be the second point
of intersection of the circumcircle of triangle BDF and the segment AB. Let L be the
second point of intersection of the circumcircle of triangle CGE and the segment CA.
Suppose that the lines F K and GL are different and intersect at the point X. Prove that
X lies on the line AO.
Solution. Since AO is the perpendicular bisector of F G (why? OF = OG and AF =
AG), we only need the fact ∠AF K = ∠AGL. First, we show that ∠AF D − ∠AGE =
∠ABC − ∠ACB. Indeed, let F G intersect BC at R, and for sake of simplicity assume
that R lies on ray CB beyond B. Taking the triangle RGB and the exterior angle at
B yields ∠GBC = ∠F GB + ∠GRB; taking the triangle RGD and exterior angle at
D yields ∠GDE = ∠F GD + ∠GRD. Now ∠ABC − ∠ACB = (∠ABG + ∠GBC) −
(∠ACF + ∠F CB) = ∠GRB (bearing in mind that ∠ABG = ∠ACF since AG = AF )=
∠GRD = ∠GDE − ∠F GD= 21 ∠GAE − 21 ∠F AD = (90◦ − ∠AGE) − (90◦ − ∠AF D) =
∠AF D − ∠AGE (since AF = AD and AG = AE). Now, ∠AF K − ∠AGL = (∠AF D −

6
 ∠KF D) − (∠AGE − ∠LGE) = (∠ABC − ∠ACB) - (∠ABC − ∠ACB)=0, since BF KD
and CGLE are both cyclic and ∠KF D = ∠KBD = ∠ABC, ∠LGE = ∠LCE = ∠ACB.
3. G3. Let ABC be a triangle with ∠C = 90◦ , 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 ω.
AH
Solution. By Menelaus’ theorem applied on triangle DHB and line CH we have HB =
PD
. Now, let AD intersect ω at T , and let CT intersect ω again at Q0 . We are then left
PB
to prove that P Q0 is tangent to ω, so Q0 ≡ Q. Since ∠DT B = ∠AT B = ∠ACB = 90◦ ,
ACT B is cyclic and so ∠CBA = ∠CT A = ∠Q0 T D = ∠Q0 BD. With ∠DQ0 B = 90◦
we have 4ABC ∼ 4DBQ0 . Finally, if the tangent to Q0 intersects BD at P 0 , then
P 0D DQ0 2 AC 2 AH PD 0 0
P 0 B = ( Q0 B ) = ( AB ) = HB = P B , yielding P ≡ P and thus P Q is tangent to ω.

4. 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 at points P and Q respectively. Let T be
the point such that BP T Q is a parallelogram. Suppose that T lies on the circumcircle of
BT
ABC. Determine all possible values of BM .
Solution. Let S be the common midpoint of BT and P Q. We claim that, if BM QP is
cyclic (regardless of whether T, A, B, C are concyclic) then S lies on a fixed line. Indeed,
consider any P, Q, P 0 , Q0 with BM QP and BM Q0 P 0 cyclic, and P, P 0 on AB, Q, Q0 on
BC, then it is not hard to see that 4M P P 0 ∼ 4M QQ0 . Denoting S 0 as midpoint of P 0 Q0
we know that there exists a spiral similarity centred at M that brings P to P 0 , Q to Q0
and S to S 0 . Moreover, ∠(P P 0 , SS 0 ) = ∠(M P, M S), i.e. if there is another point S 00 with
this property then S, S 0 , S 00 are collinear. So S lies on a fixed line. Denote P0 , Q0 , S0 as
P, Q, S in the case when P Q k AC. We know that S0 is on BM , so ∠P M S = ∠P0 M0 S0
= ∠P0 Q0 B = ∠ACB. Similarly ∠QM S = ∠BAC. In degenerate case where Q coincides
with B, let P1 be the midpoint of BP and we have ∠P1 M B = ∠QM S = ∠BAC, meaning
BM 2 = BP1 · AB. Similarly, BM 2 = BQ1 · BC, where Q1 is defined as S when P ≡ B.
This means that if O is the circumcentre of triangle ABC, then BO ⊥ P1 Q1 since P1 Q1
is antiparallel to BC.
Now T, A, B, C concyclic iff ∠BSO = 90◦ . From S ∈ P1 Q1 and P1 Q1 ⊥ BO, if h1 is
the disance from B to P1 Q1 we have BS 2 = h1 · R (with R the circumradius of 4ABC).
BM 2
Notice also that 4BP1 Q1 and 4BCA are similar with similitude BA·BC . Therefore if h
2 BM 2 hR
is the perpendicular distance from B to AC then BS = h · R( BA·BC ). Since BA·BC is
BS

2
BM , this ratio is what we sought for.
hR 2R|4ABC|
It is not hard to notice that BA·BC = BA·BC·AC , where |4ABC| is the area of triangle
2R|4ABC|
ABC. Indeed, it is well-known that |4ABC| = BA·BC·AC4R . Therefore BA·BC·AC = 12 .
q 
1
√
Finally, BT = 2BS = 2 2 BM = 2BM.

5. G5. Let ABC be a triangle with CA 6= 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 0 and I 0 are
symmetric to H and I about F and G, respectively. The line H 0 I 0 meets CD and F G at
Q and M , respectively. The line CM meets Γ again at P . Prove that CQ = QP .
Solution. Denote the centre of Γ as O, and W.L.O.G. we have CA < CB. Denote also
the angle α and ∠CDA = ∠CID = 21 ∠COD. We know that AC 2 = AD2 + DC 2 − 2 · AD ·

7
 CD·cos α and BC 2 = BD2 +DC 2 −2·BD·CD·cos(180◦ −α). With cos(180◦ −α) = − cos α
2 −AC 2
and AD = BD, we have cos α = BC 2 2 2 2
4·AD·CD (1), and AC + BC = 2AD + 2DC . (2)
Notice that CQ = QP iff OQ ⊥ CM . Also name the point E as the midpoint of F G, and
X the intersection of F G and the tangent to Γ at C. Since F G k AB and E lies on CD, it’s
not hard to notice that XC = XE. Moreover, OD ⊥ F G, OE ⊥ CD, and ∠CEX = α.
What we need now reduces to the fact ∠M CE = ∠QOE (or sin ∠M CE = sin ∠QOE)
and equivalently ∠CM E = 180◦ − ∠QOD (also sin ∠CM E = sin ∠QOD.) However, with
∠M CE + ∠CM E = 180◦ − ∠M EC = ∠EOD = ∠QOD − ∠QOE we only need the fact
ME sin ∠M CE sin ∠QOE QE OE
CE = sin ∠CM E = sin ∠QOD = QD ÷ OD . The first equality follows by sine rule, and the
last equality is well-known in trigonometry. The second equality left to be proven.
−AC 2 2 2
Now ODOE
= cos α = BC 0 AD
4·AD·CD by (1). We need the equivalence CH = HA = AC and
2
CI 0 = BI = BC (bearing in mind that AD = BD). If we let R to be H 0 I 0 ∩ AB
AD
AH 0 CI 0
then the relation RBRA
= H 0 C · I 0 B holds by Menelaus’ theorem. Changing H 0 C into
AH 0 CI 0 AC 2 −AD2
AC − CH 0 and BI 0 into BC − CI 0 yields H 0 C · I 0 B = BC 2 −AD 2 . This, in turn, means

RA 2(AC 2 −AD2 )
RD =
AC 2 −AD2 +BC 2 −AD2
(since D is the midpoint of AB), so by Menelaus’ theorem on
2(AC 2 −AD2 ) AH 0 CQ AH 0 AC 2 −AD2
4ACD and line H 0 I 0 we have
AC 2 −AD2 +BC 2 −AD2
= H 0 C · QD . With H 0 C = AD2
2AD2 2AD2
we have QD = AC 2 +BC 2 −2AD2 . But CD = CQ+QD = AC 2 +BC 2 and CE = 2 CD, CQ
CQ CQ CQ 1
CE =
4AD2 CQ CQ 4AD2 QE AC 2 +BC 2 −4AD2
,
AC 2 +BC 2 QE
= CE−CQ = AC 2 +BC 2 −4AD2 and QD = 2AC 2 +2BC 2 −4AD2 , and therefore
QE OE AC 2 +BC 2 −4AD2 4·AD·CD
QD ÷ OD = 2AC 2 +2BC 2 −4AD2 · BC 2 −AC 2 . (3)
AC −2AD 2 2 2 −2AD 2 2
Now H 0 F = CF − CH 0 = 12 AC − AD
AC = 2AC . Similarly I 0 G = BC 2BC . Therefore
MF H 0 F CI 0 AC AC 2 −2AD2 BC 2 −2AD2 AC 2 −2AD2
by Menelaus’ theorem again M G = H 0 C · I 0 G = BC · ( 2AC / 2BC ) = BC 2 −2AD 2 .
CI 0AC MF AC 2 −2AD2
(It is easy to prove that CH 0BC .) This means F G = BC 2 −AC 2 (F G = M G − M F ),
=
2 −2AD 2 2 +AC 2 −4AD 2
so M E = M F + 21 F G = F G( AC
BC 2 −AC 2
+ 12 ) = F G( BC2(BC 2 −AC 2 ) ). Therefore, M E
CE =
FG BC 2 +AC 2 −4AD2 AD BC 2 +AC 2 −4AD2
CE · 2(BC 2 −AC 2 )
= CD · (BC 2 −AC 2 )
, since AB = 2AD = 2F G and CD = 2CE.
(4)
Finally, combining (2), (3) and (4), we have the relation 2CD2 = AC 2 + BC 2 − 2AD2 that
AC 2 +BC 2 −4AD2 4·AD·CD AD BC 2 +AC 2 −4AD2 QE
implies 2AC 2 +2BC 2 −4AD 2 · BC 2 −AC 2 = CD · (BC 2 −AC 2 )
This proves M E OE
CE = QD ÷ OD .

6. G6/IMO 3. Let ABC be an acute triangle with AB > AC. Let Γ be its cirumcircle, H
its orthocenter, and F the foot of the altitude from A. Let M be the midpoint of BC.
Let Q be the point on Γ such that ∠HQA = 90◦ and let K be the point on Γ such that
∠HKQ = 90◦ . Assume that the points A, B, C, K and Q are all different and lie on Γ
in this order.
Prove that the circumcircles of triangles KQH and F KM are tangent to each other.
Solution. Let QH intersect Γ again at U , we know that ∠AQU = ∠ABU = ∠ACU =
90◦ , so from BU, CH ⊥ AB and CU, BH ⊥ AC we have BHCU a parallelogram, so HU
bisects BC and we have Q, H, M collinear.
Now denote by X the midpoint of QH. First, the circumcircle of M F H is tangent to the
circumcircle of QKH, because they intersect at H and from ∠HF M = ∠QKH = 90◦ ,
the centres of the circles must lie on midpoints of HM and QH, respectively, and H lies
on the line joining the centres. Next, denote by R the radical centre of circumcircles of
HF M, QKH, M KF , The radical axis of HF M and M KF is F M (i.e. BC) and the
radical axis of HF M and QKH is HR, with HR ⊥ QH. It suffices to prove that KR

8
 is tangent to the circumcrcle of QKH since KR is the radical axis of the circles that we
want to prove them tangent.
Now, OX 2 = R2 − QX · XU (power of point)=R2 − XH · (XH + 2HM ) = R2 − XH 2 −
2XH · HM (HM = M U and XH = XQ), XR2 = XH 2 + HR2 and OR2 = OM 2 +
M R2 = (R2 − QM · M U ) + HM 2 + HR2 = (R2 − (2XH + HM ) · HM ) + HM 2 + HR2 =
R2 −2XH ·HM +HR2 . Combining the three yields OX 2 +XR2 = OR2 , so ∠OXR = 90◦ .
Finally, since OX is the perpendicular bisector of KQ, we know that XO is an angle
bisector of lines XH and XK, With ∠OXR = 90◦ , XR is another angle bisector of
these two lines. Therefore, ∠HXR = ∠KXR. With XK = XH, 4XHR ∼ = 4XKR, so
◦
∠XKR = ∠XHR = 90 , and KR is indeed tangent to circumcircle of QKH.

7. 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 segment 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.
Solution. We first start with a lemma: let `0 , `1 , `2 be lines that are either concurrent or
parallel. Let A, C be on `0 , A1 , C1 on `1 and A2 , C2 on `2 . Let C2 A1 intersect AA2 and
CC1 at S and Q, respectively. Let A2 C1 intersect AA1 and CC2 at P and R, respectively.
Then P Q, RS, AC will also be either concurrent and parallel.
Proof: the problem condition tells us that the triangles AA1 A2 and CC1 C2 are De-
sargues’ perspective of each other. This means, if we denote AA1 ∩ CC1 as X1 and
AA2 ∩ CC2 as X2 then the intersection of A1 A2 and C1 C2 will lie on X1 X2 too (or
possibly, X1 X2 , A1 A2 , C1 C2 are all parallel).
By Menelaus’ theorem we have AA11XA1 · AA22XA2 = CC11XC1 · CC22XC2 . Denoting the intersection of
A1 C2 as T (possibly point of infinity) and considering triangles AX1 X2 and CX1 X2 gives
A1 A SX2 X1 T C2 X2 QC X1 T A1 A SX2 C2 X2 QC
A1 X1 · SA · X2 T = −1 = C2 C · QX1 · X2 T , which gives A1 X1 · SA = C2 C · QX1 . Similarly,
A2 X2 QC
A2 A· PPXA1 = CC11XC1 · RX 2 PA SX2 RX2
RC . Combining everything above gives P X1 · SA = RC · QX1 . By
Menelaus’ theorem again P S and QR either intersect on X1 X2 or both parallel to X1 X2 ,
so AP S and CQR are also perspective of each other. Thus AC, P Q, RS are concurrent
or parallel. 
Denote the incircles of AP OS, BQOP , CROQ, and DSOR by ωA , ωB , ωC , ωD , respec-
tively. Denote T (W, XY ) by the point of tangency of circle ωW to line XY too.
We first prove that P R = QS. take E, the exsimilicenter of ωB and ωC and consider the
triangle formed by e(BC), O, Q. Now, ωB and ωC are incircle and excircle of this triangle,
so OT (C, OQ) = QT (B, OQ) (*). In the case where P R k BC, (*) follows by symmetry,
We similarly have P T (B, P R) = OT (A, P R) = OT (A, SQ), OT (B.P R) = OT (B, SQ),
OT (C, P R) = OT (C, SQ) = QT (B, SQ) and RT (C, P R) = OT (D, P R) = OT (D, QS) =
ST (A, QS) Therefore, P R = P O + OR = P T (B, P R) + OT (B.P R) + OT (C, P R) +
RT (C, P R) = OT (A, SQ) + OT (B, SQ) + QT (B, SQ) + ST (A, QS) = SO + OQ = QS. It
then follows that 0=SQ − P R = SO − OR + OQ − OP = SD − DR + BQ − BP. Similarly
0 = SO − OP + OQ − OR = SA − AP + QC − RC. Adding the two equations we have
0 = SD + SA + BQ + QC − DR − RC − BP − AP = AD + BC − DC − AB, and this
last relation yields ABCD circumscribed.
Now, let AD and BC intersect P R, at A2 and C1 , respectively, AB, CD intersect QS at
A1 and C2 respectively. Denote T as the exsimilicenter of ωA and ωC (possible point at
infinity). Denote also ωO as the incircle of ABCD (which we proved exist). Then A is

9
 the exsimilicenter of ωO and ωA ; B, of ωO and ωB ; C, of ωO and ωC ; and D, of ωO and
ωD . Thus by Monge’s theorem, A, C, T are collinear. Moreover, A1 is the exsimilicenter
of ωA and ωB ; and C1 , of ωB and ωC . Again by Monge’s theorem, A1 , C1 , T collinear.
Similarly, A2 , C2 , T collinear. So AC, A1 C1 , A2 C2 parallel or concurrent. Keeping in mind
that P = C1 A2 ∩ AA1 , Q = CC1 ∩ C2 A1 , R = C1 A2 ∩ CC2 , S = A1 C2 ∩ AA2 , we can use
the lemma aforementioned to finish our proof. Q.E.D.

4 Number Theory
1. N1. Determine all positive integers M such that the sequence a0 , a1 , a2 , · · · defined by
1
a0 = M + and ak+1 = ak bak c for k = 0, 1, 2, · · ·
2
contains at least one integer term.
Solution. It’s not hard to notice that if ak = integer+0.5, then ak+1 is either in the same
form or is an integer. Notice also that, if ak is even integer+0.5, then ak+1 is an integer.
As such, all even M are solutions, and from now on we assume ak as an odd integer+0.5.
We denote v2 (x) as the highest power of 2 dividing x. If v2 (ak −1.5) = v2 (bak c−1) = c then
ak+1 = (ak −0.5)2 + ak −0.5 2 . Now ak+1 −1.5 = (ak −0.5)2 + ak −0.5
2 −1.5 ≡ 1+ ak −0.5
2 −1.5 =
ak −1.5 c c c+1 ak −1.5
2 (mod 2 ), since a k − 0.5 ≡ 1 (mod 2 ). By assumption, 2 - a k − 1.5 so 2 ≡
2c−1 c
(mod 2 ), or v2 (ak+1 − 1.5) = v2 (ak − 1.5) − 1. This means that v2 ak+c − 1.5 = 0,
or bak+c c is even (hence satisfying the problem condition). This is particularly true for
k = 0 and M > 1. For M = 1, the sequence yields k = 1.5 for all k, so the answer is every
number except 1.

2. N2. Let a and b be positive integers such that a! + b! divides a!b!. Prove that 3a ≥ 2b + 2.
Solution. If a = 1 then b! + 1 | b!, absurd. So we can assume that a, b ≥ 2 and 3a < 2b + 2
implies b > a, which we can safely assume.
Now change the problem to be a!(1 + (a + 1)(a + 2) · · · b) | a!b!, or 1 + (a + 1)(a + 2) · · · b | b!.
If b > 3a
2 − 1, then ¯ -a ≥ a2 for a even and ≥ a−1
2 otherwise. Let p | b! for some prime
p and p ≤ 2 . Since (a + 1)(a + 2) · · · b consists of b − a ≥ a−1
a−1
2 consecutive integer,
p divides this number and therefore p - 1 + (a + 1)(a + 2) · · · b. Consequently, if prime
p s.t. p | gcd(1 + (a + 1)(a + 2) · · · b, b!) then a+1
2 ≤ p ≤ a and p - a + 1, a + 2, · · · b.
Therefore, since 2p > a we must have 2p > b as well, yielding p k b!. Considering all those
primes yield the gcd of the two numbers is at most ( a2 + 1)( a2 + 2) · · · a, for a even, or
a(a − 2) · · · · · a+1 a+3
2 (or 2 ) (notice that we eliminated all even factors since they cannot be
prime). In both cases they are less than 1 + (a + 1)(a + 2) · · · b, so the problem condition
cannot hold.

3. N3. Let m and n be positive integers such that m > n. Define xk = m+k n+k 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.
Solution. Let ak = xk −1 = m−n n+k , we know that m−n is divisible by n+1, n+2, · · · 2n+1
x
so it is divisible by l = lcm(n + 1, n + 2, · · · 2n + 1). Let g(k) = n+k and we show
that eactly one of g(k) among g(1), g(2), · · · g(n + 1) is odd. Indeed, if 2c ≤ n < 2c+1
then 2c+1 ≤ 2n < 2c+2 and we know that exactly one power of 2, which is 2c+1 , is in
n + 1, n + 2, · · · 2n + 1. Conversely, only one number is divisible by 2c+1 and g(2c+1 − n)
is odd, but g(k) is even for other k.

10
 Now, let x = m−n and ak = g(k)·x. Now P (x) = x1 x2 · · · xn+1 −1 = ( n+1
Q
Qn+1 l k=1 (g(k)·x+1))−
i−1
Q
1= x( i=1 ci x ), where ci is x( b1 <b2 <···bi g(b1 )g(b2 ) · · · g(bi )). If P (x) is a power of 2,
then x must be a power
Qn+1 of 2, and from the fact that c1 is odd but c2 , c3 , · · · cn+1 all even
we conclude that ( i=1 cQ i−1 ) must be 1, which is impossible as g(1), g(2), · · · g(n + 1)
ix
are all at least one and ( n+1
i=1 ci x
i−1 ) > c ≥ n + 1. Contradiction is achieved and P (x)
i
is divisible by an odd prime.

4. N4. Suppose that a0 , a1 , · · · and b0 , b1 , · · · are two sequences of positive integers such
that a0 , b0 ≥ 2 and

an+1 = gcd (an , bn ) + 1, bn+1 = lcm (an , bn ) − 1.

Show 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 .
Solution. We partition the sequence (an ) into groups of adjacent numbers such that
ai+1 and ai are in the same group if and only if ai+1 > ai . Obviously, ai+1 − 1 | ai , so
ai+1 > ai ⇔ ai+1 = ai + 1 ⇔ ai | bi ⇔ bi+1 = bi − 1. The tail of a group is defined
as the last (and therefore the largest) number in that group; we claim that the sequence
of numbers containing all tails of groups must be non-increasing. Indeed, let an be a
tail, then an+1 = gcd(an , bn ) + 1, and for sake of simplicity denote this number by g + 1.
an bn
We then have bn+1 = − 1. Now, suppose that the next tail is at least an , then
g
an bn
(an+k , bn+k ) = (g + k, − k), ∀k ≤ an − g. We therefore have an+an −g = an and
g
an bn an bn
bn+an −g = − an + g. Notice that g = gcd(an , bn ) so g | bn , and an divides both
g g
and an , so gcd(an+an −g , bn+an −g ) = g < an , and this an+an −g is a tail now (hence cannot
exceed an ).
Since the tail of the sequence cannot decrease forever, it must remain constant at one
point. Now, for sufficiently large indices when the tail remains constant, from above we
know that if an and am are both tails then gcd(an , bn ) = gcd(am , bm ). It folows that the
number succeeding each tail must be the same too, and that’s the smallest number of the
group thereafter. Summing up, the smallest and the biggest number (i.e. first and last
number) in a period becomes constant, and ai+1 = ai + 1 for ai , ai+1 in the same group.
We therefore conclude that the groups must be identical at one point, hence eventually
periodic.

5. N6. Let Z>0 denote the set of positive integers. Consider a function f : Z>0 → Z>0 . For
any m, n ∈ Z>0 we write f n (m) = f (f (. . . f (m) . . .)). Suppose that f has the following
| {z }
n
two properties:
f n (m)−m
(i) if m, n ∈ Z>0 , then n ∈ Z>0 ; (ii) The set Z>0 \ {f (n) | n ∈ Z>0 } is finite.
Prove that the sequence f (1) − 1, f (2) − 2, f (3) − 3, . . . is periodic.
Solution. If f (m) = f (k), then f n (m) = f n (k), ∀n ∈ N. By (i), n divides both f n (m)−m
and f n (m) − k, so n divides m − k for all positive integers n. This means m − k = 0
and f is injective. From (i) again we have f (m) − m > 0, ∀m ∈ N. This allows us to
partition the set of positive integers into groups such that for one group A = {ai | i ≥ 0},
ak+1 = f (ak ), ∀k ≥ 1 and we name a0 as the element such that there exists no integer i
such that f (i) = a0 . By (ii), the number of set A is finite, so name them as A1 , A2 , · · · Ap .

11
We proceed with this lemma:
For any set Ak = {ai | i ≥ 0} such that there eists a positive integer s with ai+1 − ai < s
for infinitely many i, the number a0 , a1 , · · · necessarily form an arithmetic progression.
Proof: For every i and every M , we can find infinitely many j > i + M s.t. j satisfies this
property aj+1 −aj < s. Now, take M > |ai+1 −ai |+s and we have j −i divides both aj −ai
and aj+1 − ai+1 . It therefore divides (aj+1 − ai+1 ) − (aj − ai ) = (aj+1 − aj ) − (ai+1 − ai )
and |(aj+1 − aj ) − (ai+1 − ai )| ≤ |(aj+1 − aj )| + |(ai+1 − ai )| ≤ |(aj+1 − aj )| + s < j − i,
meaning that (aj+1 − aj ) − (ai+1 − ai ) = 0. Taking this for infinitely many j yields
aj+1 − aj = x, a constant for infinitely many j. This, in turn, allows us to take any i and
j with aj+1 − aj = x and j − i > |(aj+1 − aj )| + x. Repeating the above yields the same
thing, whereby ai+1 − ai = aj+1 − aj = x. Thus, ai+1 − ai is indeed a constant for all i,
i.e. the elements form an arithmetic progression.
We prove, inductively, that elements in all sets satisfy the lemma condition, hence form
arithmetic progressions. First we prove that this is true for at least one set. Now, among
any interval [k(pm + 1) + 1, (k + 1)(p + 1)], there must exist two integers i and j in this
interval such that i, j ∈ Ac for some integer c. We record such c, and consider different
c ∈ [1, p] for all integers k. This means, there exist a number c that is recorded infinitely
many times. W.l.o.g. let c = 1, so this is fulfilled for A1 since we can substitute p + 1
into s in the lemma. Suppose that this is true for groups A1 , A2 , · · · Ai , and let D= lcm
(d1 , d2 , · · · , di ). Also name B = Ai+1 ∪ Ai+1 ∪ · · · ∪ Ap (the unselected). This means that,
if D | a − b for a, b ∈ N, we have a ∈ Ak ⇔ b ∈ Ak , ∀k ∈ [1, i]. More importantly, this
means a ∈ B ⇔ b ∈ B. With this, we conclude that B contains at least an element in
the interval [a + 1, a + D] for each a (otherwise A1 , A2 , · · · Ai jointly contains all positive
integers), and at least p − i + 1 elements among [a + 1, a + (p − i + 1)D]. In other words,
there are at least two elements in the interval belong to the same set, say Ac , and record
this c. Repeat this for infinitely many disjoint intervals of length (p − i + 1)D, and since
the choice of c is finite (in the set [i + 1, p]), at least one such c recorded infinitely many
times, hence such c (say, i + 1) fulfills the condition in the lemma (this time we have
s = (p − i + 1)D).
Finally, since every element in each set form an arithmetic progression, we denote D=lcm
(d1 , d2 , . . . dp ) (whereby di is the common difference of Ai ) and prove that f (i) − i has
period D. Indeed, for every i ∈ N. i and i + D are in the same group, say, Ac . Hence
f (i + D) − (i + D) = f (i) − i = dc . Q.E.D.

12