2012 APMO PROBLEMS

Time allowed: 4 hours Each problem is worth 7 points

*The contest problems are to be kept confidential until they are posted on the offi-
cial APMO website (http://www.mmjp.or.jp/competitions/APMO). Please do not
disclose nor discuss the problems over the internet until that date. Calculators are
not allowed to use.

Problem 1. Let P be a point in the interior of a triangle ABC, and let D, E, F

be the point of intersection of the line AP and the side BC of the triangle, of the
line BP and the side CA, and of the line CP and the side AB, respectively. Prove
that the area of the triangle ABC must be 6 if the area of each of the triangles
P F A, P DB and P EC is 1.
Problem 2. Into each box of a 2012 × 2012 square grid, a real number greater
than or equal to 0 and less than or equal to 1 is inserted. Consider splitting the grid
into 2 non-empty rectangles consisting of boxes of the grid by drawing a line parallel
either to the horizontal or the vertical side of the grid. Suppose that for at least one
of the resulting rectangles the sum of the numbers in the boxes within the rectangle
is less than or equal to 1, no matter how the grid is split into 2 such rectangles.
Determine the maximum possible value for the sum of all the 2012 × 2012 numbers
inserted into the boxes.
Problem 3. Determine all the pairs (p, n) of a prime number p and a positive
p
integer n for which npn +1
+1
is an integer.
Problem 4. Let ABC be an acute triangle. Denote by D the foot of the
perpendicular line drawn from the point A to the side BC, by M the midpoint of
BC, and by H the orthocenter of ABC. Let E be the point of intersection of the
circumcircle Γ of the triangle ABC and the half line M H, and F be the point of
intersection (other than E) of the line ED and the circle Γ. Prove that BF AB
CF = AC
must hold.
Here we denote by XY the length of the line segment XY .
Problem 5. Let n be an integer greater than or equal to 2. Prove that if the
real numbers a1 , a2 , · · · , an satisfy a21 + a22 + · · · + a2n = n, then
X 1 n
≤
n − ai aj 2
1≤i<j≤n

must hold.

1
 SOLUTIONS FOR 2012 APMO PROBLEMS

Problem 1.
Solution: Let us denote by 4XY Z the area of the triangle XY Z. Let
x = 4P AB, y = 4P BC and z = 4P CA.
From
y : z = 4BCP : 4ACP = BF : AF = 4BP F : 4AP F = (x − 1) : 1
follows that z(x − 1) = y, which yields (z + 1)x = x + y + z. Similarly, we get
(x + 1)y = x + y + z and (y + 1)z = x + y + z. Thus, we obtain (x + 1)y = (y + 1)z =
(z + 1)x.
We may assume without loss of generality that x ≤ y, z. If we assume that y > z
holds, then we get (y + 1)z > (z + 1)x, which is a contradiction. Similarly, we see
that y < z leads to a contradiction (x + 1)y < (y + 1)z. Therefore, we must have
y = z. Then, we also get from (y + 1)z = (z + 1)x that x = z must hold. We now
obtain from (x − 1) : 1 = y : z = 1 : 1 that x = y = z = 2 holds. Therefore, we
conclude that the area of the triangle ABC equals x + y + z = 6.

Problem 2.
Solution: If we insert numbers as in the figure below (00 s are to be inserted in the
remaining blank boxes), then we see that the condition of the problem is satisfied
and the total number of all the numbers inserted is 5.

0 1 0
1 1 1
0 1 0

We will show that the sum of all the numbers to be inserted in the boxes of the
given grid cannot be more than 5 if the distribution of the numbers has to satisfy
the requirement of the problem. Let n = 2012. Let us say that the row number
(the column number) of a box in the given grid is i (j, respectively) if the box lies
on the i-th row and the j-th column. For a pair of positive integers x and y, denote
by R(x, y) the sum of the numbers inserted in all of the boxes whose row number is
greater than or equal to x and less than or equal to y (assign the value 0 if x > y).
First let a be the largest integer satisfying 1 ≤ a ≤ n and R(1, a − 1) ≤ 1, and
then choose the smallest integer c satisfying a ≤ c ≤ n and R(c + 1, n) ≤ 1. It is
possible to choose such a pair a, c since R(1, 0) = 0 and R(n + 1, n) = 0. If a < c,
then we have a < n and so, by the maximality of a, we must have R(1, a) > 1,
while from the minimality of c, we must have R(a + 1, n) > 1. Then by splitting the
grid into 2 rectangles by means of the horizontal line bordering the a-th row and
the a + 1-th row, we get the splitting contradicting the requirement of the problem.
Thus, we must have a = c.
Similarly, if for any pair of integers x, y we define C(x, y) to be the sum of the
numbers inserted in all of the boxes whose column number is greater than or equal
to x and less than or equal to y (C(x, y) = 0 if x > y), then we get a number b for
which
C(1, b − 1) ≤ 1, C(b + 1, n) ≤ 1, 1 ≤ b ≤ n.
1
2

If we let r be the number inserted in the box whose row number is a and the column
number is b, then since r ≤ 1, we conclude that the sum of the numbers inserted
into all of the boxes is
≤ R(1, a − 1) + R(a + 1, n) + C(1, b − 1) + C(b + 1, n) + r ≤ 5.

Problem 3.
Solution
For integers a, b and a positive integer m, let us write a ≡ b (mod m) if a − b
p
is divisible by m. Since npn +1
+1
must be a positive integer, we see that pn ≤ np must
hold. This means that if p = 2, then 2n ≤ n2 must hold. As it is easy to show by
induction that 2n > n2 holds if n ≥ 5, we conclude that if p = 2, then n ≤ 4 must
be satisfied. And we can check that (p, n) = (2, 2), (2, 4) satisfy the condition of
the problem, while (2, 3) does not.
Next, we consider the case where p ≥ 3.
Suppose s is an integer satisfying s ≥ p. If sp ≤ ps for such an s, then we have
 p  p
1 1
(s + 1)p = sp 1 + ≤ ps 1 +
s p
p p
X 1 X 1
= ps p Cr r < p
s

r=0
p r=0
r!
 p 
X 1
≤ ps 1 +
r=1
2r−1
< ps (1 + 2) ≤ ps+1
Thus we have (s + 1)p < ps+1 , and by induction on n, we can conclude that if
n > p, then np < pn . This implies that we must have n ≤ p in order to satisfy our
requirement pn ≤ np .
We note that since pn + 1 is even, so is np + 1, which, in turn implies that n must
be odd and therefore, pn + 1 is divisible by p + 1, and np + 1 is also divisible by
p + 1. Thus we have np ≡ −1 (mod (p + 1)), and therefore, n2p ≡ 1 (mod (p + 1)).
Now, let e be the smallest positive integer for which ne ≡ 1 (mod (p+1)). Then,
we can write 2p = ex + y, where x, y are non-negative integers and 0 ≤ y < e, and
we have

1 ≡ n2p = (ne )x · ny ≡ ny (mod (p + 1)),

which implies, because of the minimality of e, that y = 0 must hold. This means
that 2p is an integral multiple of e, and therefore, e must equal one of the numbers
1, 2, p, 2p.
Now, if e = 1, p, then we get np ≡ 1 (mod (p + 1)), which contradicts the
fact that p is an odd prime. Since n and p + 1 are relatively prime, we have by
Euler’s Theorem that nϕ(p+1) ≡ 1 (mod (p+1)), where ϕ(m) denotes the number of
integers j(1 ≤ j ≤ m) which are relatively prime with m. From ϕ(p+1) < p+1 < 2p
and the minimality of e, we can then conclude that e = 2 must hold.
From n2 ≡ 1 (mod (p + 1)), we get
p−1
−1 ≡ np = n(2· 2 +1) ≡ n (mod (p + 1)),
 3

which implies that p + 1 divides n + 1. Therefore, we must have p ≤ n, which,

together with the fact n ≤ p, show that p = n must hold.
It is clear that the pair (p, p) for any prime p ≥ 3 satisfies the condition of the
problem, and thus, we conclude that the pairs (p, n) which satisfy the condition of
the problem must be of the form (2, 4) and (p, p) with any prime p.
Alternate Solution. Let us consider the case where p ≥ 3. As we saw in the
preceding solution, n must be odd if the pair (p, n) satisfy the condition of the
problem. Now, let q be a prime factor of p + 1. Then, since p + 1 divides pn + 1, q
must be a prime factor of pn + 1 and of np + 1 as well. Suppose q ≥ 3. Then, from
np ≡ −1 (mod q), it follows that n2p ≡ 1 (mod q) holds. If we let e be the smallest
positive integer satisfying ne ≡ 1 (mod q), then by using the same argument as
we used in the preceding solution, we can conclude that e must equal one of the
numbers 1, 2, p, 2p. If e = 1, p, then we get np ≡ 1 (mod q), which contradicts the
assumption q ≥ 3. Since n is not a multiple of q, by Fermat’s Little Theorem we
get nq−1 ≡ 1 (mod q), and therefore, we get by the minimality of e that e = 2 must
hold. From n2 ≡ 1 (mod q), we also get
p−1
np = n(2· 2 +1) ≡ n (mod q),
p
and since n ≡ −1 (mod q), we have n ≡ −1 (mod q) as well.
Now, if q = 2 then since n is odd, we have n ≡ −1 (mod q) as well. Thus, we
conclude that for an arbitrary prime factor q of p + 1, n ≡ −1 (mod q) must hold.
Suppose, for a prime q, q k for some positive integer k is a factor of p + 1. Then
q must be a factor of np + 1 as well. But since
k

np + 1 = (n + 1)(np−1 − np−2 + · · · − n + 1) and

p−1 p−2 p−1 p−2
n −n + · · · − n + 1 ≡ (−1) − (−1) + · · · − (−1) + 1 6≡ 0 (mod q),
k
we see that q must divide n + 1. By applying the argument above for each prime
factor q of p + 1, we can then conclude that n + 1 must be divisible by p + 1, and
as we did in the preceding proof, we can conclude that n = p must hold.

Problem 4.
Solution: If AB = AC, then we get BF = CF and the conclusion of the problem
is clearly satisfied. So, we assume that AB 6= AC in the sequel.
Due to symmetry, we may suppose without loss of generality that AB > AC.
Let K be the point on the circle Γ such that AK is a diameter of this circle. Then,
we get
∠BCK = ∠ACK − ∠ACB = 90◦ − ∠ACB = ∠CBH
and
∠CBK = ∠ABK − ∠ABC = 90◦ − ∠ABC = ∠BCH,
from which we conclude that the triangles BCK and CBH are congruent. There-
fore, the quadrilateral BKCH is a parallelogram, and its diagonal HK passes
through the center M of the other diagonal BC. Therefore, the 3 points H, M, K
lie on the same straight line, and we have ∠AEM = ∠AEK = 90◦ .
From ∠AED = 90◦ = ∠ADM , we see that the 4 points A, E, D, M lie on
the circumference of the same circle, from which we obtain ∠AM B = ∠AED =
∠AEF = ∠ACF . Putting this fact together with the fact that ∠ABM = ∠AF C,
AM AC
we conclude that the triangles ABM and AF C are similar, and we get BM =F C.
By a similar argument, we get that the triangles ACM and AF B are similar, and
4

AM AB AC AB
therefore, that CM = F B holds. Noting that BM = CM , we also get F C = F B ,
BF AB
from which we can conclude that CF = AC , proving the assertion of the problem.

Problem 5.
a2i +a2j
Solution: Let us note first that if i 6= j, then since ai aj ≤ 2 , we have

a2i + a2j n n
n − ai aj ≥ n − ≥ n − = > 0.
2 2 2

If we set bi = |ai | (i = 1, 2, . . . , n), then we get b21 + b22 + · · · + b2n = n and n−a1i aj ≤
1
n−bi bj , which shows that it is enough to prove the assertion of the problem in the
case where all of a1 , a2 , · · · , an are non-negative. Hence, we assume from now on
that a1 , a2 , · · · , an are all non-negative.
By multiplying by n the both sides of the desired inequality we get the inequality:

X n n2
≤
n − ai aj 2
1≤i<j≤n

n a a
i j
and since n−ai aj = 1 + n−a i aj
, we obtain from the inequality above by subtracting
n(n−1)
2 from both sides the following inequality:
X ai aj n
(i) ≤
n − ai aj 2
1≤i<j≤n

We will show that this inequality (i) holds.

If for some i the equality a2i = n is valid, then aj = 0 must hold for all j 6= i and
the inequality (i) is trivially satisfied. So, we assume from now on that a2i < n is
valid for each i. 2
a2 +a2

ai +aj
Let us assume that i 6= j from now on. Since 0 ≤ ai aj ≤ 2 ≤ i2 j
holds, we have
 2
ai +aj
ai aj ai aj 2 1 (ai + aj )2
(ii) ≤ ≤ = · .
n − ai aj a2 +a2
n− i2 j n−
a2i +a2j 2 (n − a2i ) + (n − a2j )
2

Since n − a2i > 0, n − a2j > 0, we also get from the Cauchy-Schwarz inequality that

!
a2j a2i
+ ((n − a2i ) + (n − a2j )) ≥ (ai + aj )2 ,
n − a2i n − a2j

from which it follows that

!
(ai + aj )2 a2j a2i
(iii) ≤ +
(n − a2i ) + (n − a2j ) n − a2i n − a2j
 5

holds. Combining the inequalities (ii) and (iii), we get

!
X ai aj 1 X a2j a2i
≤ 2 +
n − ai aj 2 n − ai n − a2j
1≤i<j≤n 1≤i<j≤n

1X a2j
=
2 n − a2i
i6=j
n
1 X n − a2 i
=
2 i=1 n − a2i
n
= ,
2
which establishes the desired inequality (i).
 Solutions of APMO 2013
Problem 1. Let ABC be an acute triangle with altitudes AD, BE and CF , and let O
be the center of its circumcircle. Show that the segments OA, OF, OB, OD, OC, OE dissect
the triangle ABC into three pairs of triangles that have equal areas.

Solution. Let M and N be midpoints of sides BC and AC, respectively. Notice that
∠M OC = 21 ∠BOC = ∠EAB, ∠OM C = 90◦ = ∠AEB, so triangles OM C and AEB are
similar and we get OM
AE
= OC
AB
. For triangles ON A and BDA we also have ON
BD
OA
= BA . Then
OM ON
AE
= BD or BD · OM = AE · ON.
Denote by S(Φ) the area of the figure Φ. So, we see that S(OBD) = 12 BD · OM =
1
2
AE · ON = S(OAE). Analogously, S(OCD) = S(OAF ) and S(OCE) = S(OBF ).

Alternative solution. Let R be the circumradius of triangle ABC, and as usual write
A, B, C for angles ∠CAB, ∠ABC, ∠BCA respectively, and a, b, c for sides BC, CA, AB
respectively. Then the area of triangle OCD is
1
S(OCD) = 2
· OC · CD · sin(∠OCD) = 21 R · CD · sin(∠OCD).

Now CD = b cos C, and

180◦ − 2A
∠OCD = = 90◦ − A
2
(since triangle OBC is isosceles, and ∠BOC = 2A). So

S(OCD) = 21 Rb cos C sin(90◦ − A) = 21 Rb cos C cos A.

A similar calculation gives

S(OAF ) = 21 OA · AF · sin(∠OAF )
= 12 R · (b cos A) sin(90◦ − C)
= 21 Rb cos A cos C,

so OCD and OAF have the same area. In the same way we find that OBD and OAE have
the same area, as do OCE and OBF .
2
Problem 2. Determine all positive integers n for which √n +1 is an integer. Here [r]
[ n]2 +2
denotes the greatest integer less than or equal to r.

Solution. We will show that there are no positive integers n satisfying the condition of
the problem. √
Let m = [ n] and a = n−m2 . We have m ≥ 1 since n ≥ 1. From n2 +1 = (m2 +a)2 +1 ≡
(a − 2)2 + 1 (mod (m2 + 2)), it follows that the condition of the problem is equivalent to the
fact that (a − 2)2 + 1 is divisible by m2 + 2. Since we have

0 < (a − 2)2 + 1 ≤ max{22 , (2m − 2)2 } + 1 ≤ 4m2 + 1 < 4(m2 + 2),

1
we see that (a − 2)2 + 1 = k(m2 + 2) must hold with k = 1, 2 or 3. We will show that none
of these can occur.
Case 1. When k = 1. We get (a − 2)2 − m2 = 1, and this implies that a − 2 = ±1, m = 0
must hold, but this contradicts with fact m ≥ 1.
Case 2. When k = 2. We have (a − 2)2 + 1 = 2(m2 + 2) in this case, but any perfect
square is congruent to 0, 1, 4 mod 8, and therefore, we have (a − 2)2 + 1 ≡ 1, 2, 5 (mod 8),
while 2(m2 + 2) ≡ 4, 6 (mod 8). Thus, this case cannot occur either.
Case 3. When k = 3. We have (a − 2)2 + 1 = 3(m2 + 2) in this case. Since any perfect
square is congruent to 0 or 1 mod 3, we have (a − 2)2 + 1 ≡ 1, 2 (mod 3), while 3(m2 + 2) ≡ 0
(mod 3), which shows that this case cannot occur either.

Problem 3. For 2k real numbers a1 , a2 , . . . , ak , b1 , b2 , . . . , bk define the sequence of

numbers Xn by
Xk
Xn = [ai n + bi ] (n = 1, 2, . . .).
i=1
Pk
If the sequence Xn forms an arithmetic progression, show that i=1 ai must be an integer.
Here [r] denotes the greatest integer less than or equal to r.

Solution. Let us write A = ki=1 ai and B = ki=1 bi . Summing the corresponding terms
P P
of the following inequalities over i,
ai n + bi − 1 < [ai n + bi ] ≤ ai n + bi ,
we obtain An + B − k < Xn < An + B. Now suppose that {Xn } is an arithmetic progression
with the common difference d, then we have nd = Xn+1 − X1 and A + B − k < X1 ≤ A + B
Combining with the inequalities obtained above, we get
A(n + 1) + B − k < nd + X1 < A(n + 1) + B,
or
An − k ≤ An + (A + B − X1 ) − k < nd < An + (A + B − X1 ) < An + k,
from which we conclude that |A − d| < nk must hold. Since this inequality holds for any
positive integer n, we must have A = d. Since {Xn } is a sequence of integers, d must be an
integer also, and thus we conclude that A is also an integer.

Problem 4. Let a and b be positive integers, and let A and B be finite sets of integers
satisfying:
(i) A and B are disjoint;
(ii) if an integer i belongs either to A or to B, then i + a belongs to A or i − b belongs
to B.
Prove that a|A| = b|B|. (Here |X| denotes the number of elements in the set X.)

Solution. Let A∗ = {n − a : n ∈ A} and B ∗ = {n + b : n ∈ B}. Then, by (ii),

A ∪ B ⊆ A∗ ∪ B ∗ and by (i),
|A ∪ B| ≤ |A∗ ∪ B ∗ | ≤ |A∗ | + |B ∗ | = |A| + |B| = |A ∪ B|. (1)

2
Thus, A ∪ B =P A∗ ∪ B ∗ P
and A∗ and B ∗ have no element in common. For each finite set X
of integers, let (X) = x∈X x. Then
X X X
(A) + (B) = (A ∪ B)
X X X
= (A∗ ∪ B ∗ ) = (A∗ ) + (B ∗ )
X X
= (A) − a|A| + (B) + b|B|, (2)

which implies a|A| = b|B|.

Alternative solution. Let us construct a directed graph whose vertices are labelled by
the members of A ∪ B and such that there is an edge from i to j iff j ∈ A and j = i + a or
j ∈ B and j = i − b. From (ii), each vertex has out-degree ≥ 1 and, from (i), each vertex has
in-degree ≤ 1. Since the sum of the out-degrees equals the sum of the in-degrees, each vertex
has in-degree and out-degree equal to 1. This is only possible if the graph is the union of
disjoint cycles, say G1 , G2 , . . . , Gn . Let |Ak | be the number of elements of A in Gk and |Bk |
be the number of elements of B in Gk . The cycle Gk will involve increasing vertex labels by
a a total of |Ak | times and decreasing them by b a total of |Bk | times. Since it is a cycle, we
have a|Ak | = b|Bk |. Summing over all cycles gives the result.

Problem 5. Let ABCD be a quadrilateral inscribed in a circle ω, and let P be a point

on the extension of AC such that P B and P D are tangent to ω. The tangent at C intersects
P D at Q and the line AD at R. Let E be the second point of intersection between AQ and
ω. Prove that B, E, R are collinear.
Solution. To show B, E, R are collinear, it is equivalent to show the lines AD, BE, CQ
are concurrent. Let CQ intersect AD at R and BE intersect AD at R0 . We shall show
RD/RA = R0 D/R0 A so that R = R0 .
Since 4P AD is similar to 4P DC and 4P AB is similar to 4P BC, we have AD/DC =
P A/P D = P A/P B = AB/BC. Hence, AB · DC = BC · AD. By Ptolemy’s theorem,
AB · DC = BC · AD = 21 CA · DB. Similarly CA · ED = CE · AD = 12 AE · DC.
Thus
DB 2DC
= , (3)
AB CA
and
DC 2ED
= . (4)
CA AE

3
 ..........................................................
............ .........
......... ........
........ .......
..
.. . ...... ......
..... ......
.. . .....
.
...... .....
..... .....
.. . . .....
... . .....
. .... ...
...
. ... ...
...
. ...
...
A .
...
..............
...
...
............................... ...
... ............... ............ ...
...
.
.... .... ..... .......... ................ ...
... .... .... ....... ......... ...
...
...
... .... .......
... ... .....
.....
.........
. .........
.... .........
ω ...
...
... ... ... . ..... ... .......... ...
... ... . ...
.... ... .... ....... ............. ..
... . ... . ...
... ... ... .....
. .
.........
... ...
... ... . ... .....
..
. .........
... ...
.
.
... .... ...... .......... .
... ... . ..
..... . ............ ..
...
...
... ... ... .....
.....
......... ...
... ... ... ..... .........
......... ...
... ... ..... ......... ..
...
...
...
...
...
...
...
...
.....
.
.....
.....
D ..... . .
... .
...
....................
... ..... ...................... ................
... ... ..... ............ ........................ .........
... ... ... ..... ............. . .. .........
...
...
... ...
. ..... .
.. .... .... ............. ..
. ....... ................ .........
... ... ................ .........
... ... .. ...... .... .....
... .... .. . ...
. .... ............... .......... ........... ................. .........
.........
.... ... ... ............ ..... ....
. .. ..... ...
. .........
..... .. .. .. ... .. . .. ... .........
..... ... . .... ..
.. .......... .... .....
.......... ..... ... ..... ..... ..
. . . .........
....... .................. ...
. .. ... ..... ...... ..
. .........
.........
.
........................ . ..... ......... ............... . .
................ ........................................................ .... ... .........
....... .......... ... ........................................................ .................. .. .........
B ............ ............
............ .........
..... ........ .......... ....
...
. ........
..
..... ................................
.. ..... .. . ....... .
.
.
.
........................................................
..... ... .. . .
...
...
...
...
................................................
.........
.........
.........
R(R0 )
.. .. . ....
....... .
. ..
..... ........... ......... ... ...... ........... ...........
.....
.....
.....
..
E .. . ......
... .................. ..
......................................................... ........................................................................................................................................................................................................................................................................................................
...................... ............ ..
..... ... . .
C .....
.....
.....
...
....
...
Q ...
.
...
.....
..... ...
... ...
.....
..... ... ...
..... ... ..
.
.....
..... ...
.. ...
.....
..... ..... ...
..... ... ...
..... ... ...
..... ..
..... ... ...
..... .. ...
........ ..
....... ..
........
.

P
RD DC RC
Since the triangles RDC and RCA are similar, we have RC
= CA
= RA
. Thus using (4)
 2  2  2
RD RD · RA RC DC 2ED
= = = = . (5)
RA RA2 RA CA AE

Using the similar triangles ABR0 and EDR0 , we have R0 D/R0 B = ED/AB. Using the
similar triangles DBR0 and EAR0 we have R0 A/R0 B = EA/DB. Thus using (3) and (4),
2
R0 D

ED · DB 2ED
= = . (6)
R0 A EA · AB AE
It follows from (5) and (6) that R = R0 .

4
 Solutions of APMO 2014

Problem 1. For a positive integer m denote by S(m) and P (m) the sum and product,
respectively, of the digits of m. Show that for each positive integer n, there exist positive
integers a1 , a2 , . . . , an satisfying the following conditions:
S(a1 ) < S(a2 ) < · · · < S(an ) and S(ai ) = P (ai+1 ) (i = 1, 2, . . . , n).
(We let an+1 = a1 .) (Problem Committee of the Japan Mathematical Olympiad Foundation)
Solution. Let k be a sufficiently large positive integer. Choose for each i = 2, 3, . . . , n,
ai to be a positive integer among whose digits the number 2 appears exactly k + i − 2 times
and the number 1 appears exactly 2k+i−1 − 2(k + i − 2) times, and nothing else. Then, we
have S(ai ) = 2k+i−1 and P (ai ) = 2k+i−2 for each i, 2 ≤ i ≤ n. Then, we let a1 be a positive
integer among whose digits the number 2 appears exactly k + n − 1 times and the number
1 appears exactly 2k − 2(k + n − 1) times, and nothing else. Then, we see that a1 satisfies
S(a1 ) = 2k and P (a1 ) = 2k+n−1 . Such a choice of a1 is possible if we take k to be large
enough to satisfy 2k > 2(k + n − 1) and we see that the numbers a1 , . . . , an chosen this way
satisfy the given requirements.

Problem 2. Let S = {1, 2, . . . , 2014}. For each non-empty subset T ⊆ S, one of its
members is chosen as its representative. Find the number of ways to assign representatives
to all non-empty subsets of S so that if a subset D ⊆ S is a disjoint union of non-empty
subsets A, B, C ⊆ S, then the representative of D is also the representative of at least one
of A, B, C. (Warut Suksompong, Thailand)
Solution. Answer: 108 · 2014!.
For any subset X let r(X) denotes the representative of X. Suppose that x1 = r(S).
First, we prove the following fact:
If x1 ∈ X and X ⊆ S, then x1 = r(X).
If |X| ≤ 2012, then we can write S as a disjoint union of X and two other subsets of S,
which gives that x1 = r(X). If |X| = 2013, then let y ∈ X and y 6= x1 . We can write X as
a disjoint union of {x1 , y} and two other subsets. We already proved that r({x1 , y}) = x1
(since |{x1 , y}| = 2 < 2012) and it follows that y 6= r(X) for every y ∈ X except x1 . We
have proved the fact.
Note that this fact is true and can be proved similarly, if the ground set S would contain
at least 5 elements.
There are 2014 ways to choose x1 = r(S) and for x1 ∈ X ⊆ S we have r(X) = x1 . Let
S1 = S \ {x1 }. Analogously, we can state that there are 2013 ways to choose x2 = r(S1 )
and for x2 ∈ X ⊆ S1 we have r(X) = x2 . Proceeding similarly (or by induction), there
are 2014 · 2013 · · · 5 ways to choose x1 , x2 , . . . , x2010 ∈ S so that for all i = 1, 2 . . . , 2010,
xi = r(X) for each X ⊆ S \ {x1 , . . . , xi−1 } and xi ∈ X.
We are now left with four elements Y = {y1 , y2 , y3 , y4 }. There are 4 ways to choose r(Y ).
Suppose that y1 = r(Y ). Then we clearly have y1 = r({y1 , y2 }) = r({y1 , y3 }) = r({y1 , y4 }).
The only subsets whose representative has not been assigned yet are {y1 , y2 , y3 }, {y1 , y2 , y4 },
{y1 , y3 , y4 }, {y2 , y3 , y4 }, {y2 , y3 }, {y2 , y4 }, {y3 , y4 }. These subsets can be assigned in any way,
hence giving 34 · 23 more choices.

1
 In conclusion, the total number of assignments is 2014 · 2013 · · · 4 · 34 · 23 = 108 · 2014!.

Problem 3. Find all positive integers n such that for any integer k there exists an
integer a for which a3 + a − k is divisible by n. (Warut Suksompong, Thailand)
Solution. Answer: All integers n = 3b , where b is a nonnegative integer.
We are looking for integers n such that the set A = {a3 + a | a ∈ Z} is a complete residue
system by modulo n. Let us call this property by (*). It is not hard to see that n = 1
satisfies (*) and n = 2 does not.
If a ≡ b (mod n), then a3 + a ≡ b3 + b (mod n). So n satisfies (*) iff there are no
a, b ∈ {0, . . . , n − 1} with a 6= b and a3 + a ≡ b3 + b (mod n).
First, let us prove that 3j satisfies (*) for all j ≥ 1. Suppose that a3 + a ≡ b3 + b (mod 3j )
for a 6= b. Then (a − b)(a2 + ab + b2 + 1) ≡ 0 (mod 3j ). We can easily check mod 3 that
a2 + ab + b2 + 1 is not divisible by 3.
Next note that if A is not a complete residue system modulo integer r, then it is also not
a complete residue system modulo any multiple of r. Hence it remains to prove that any
prime p > 3 does not satisfy (*).
If p ≡ 1 (mod 4), there exists b such that b2 ≡ −1 (mod p). We then take a = 0 to
obtain the congruence a3 + a ≡ b3 + b (mod p).
Suppose now that p ≡ 3 (mod 4). We will prove that there are integers a, b 6≡ 0 (mod p)
such that a2 + ab + b2 ≡ −1 (mod p). Note that we may suppose that a 6≡ b (mod p), since
otherwise if a ≡ b (mod p) satisfies a2 + ab + b2 + 1 ≡ 0 (mod p), then (2a)2 + (2a)(−a) +
a2 + 1 ≡ 0 (mod p) and 2a 6≡ −a (mod p). Letting c be the inverse of b modulo p (i.e.
bc ≡ 1 (mod p)), the relation is equivalent to (ac)2 + ac + 1 ≡ −c2 (mod p). Note that −c2
can take on the values of all non-quadratic residues modulo p. If we can find an integer x
such that x2 + x + 1 is a non-quadratic residue modulo p, the values of a and c will follow
immediately. Hence we focus on this latter task.
Note that if x, y ∈ {0, . . . , p − 1} = B, then x2 + x + 1 ≡ y 2 + y + 1 (mod p) iff p divides
x + y + 1. We can deduce that x2 + x + 1 takes on (p + 1)/2 values as x varies in B. Since
there are (p − 1)/2 non-quadratic residues modulo p, the (p + 1)/2 values that x2 + x + 1
take on must be 0 and all the quadratic residues.
Let C be the set of quadratic residues modulo p and 0, and let y ∈ C. Suppose that
y ≡ z 2 (mod p) and let z ≡ 2w + 1 (mod p) (we can always choose such w). Then y + 3 ≡
4(w2 + w + 1) (mod p). From the previous paragraph, we know that 4(w2 + w + 1) ∈ C.
This means that y ∈ C =⇒ y + 3 ∈ C. Unless p = 3, the relation implies that all elements
of B are in C, a contradiction. This concludes the proof.

Problem 4. Let n and b be positive integers. We say n is b-discerning if there exists a

set consisting of n different positive integers less than b that has no two different subsets U
and V such that the sum of all elements in U equals the sum of all elements in V .
(a) Prove that 8 is a 100-discerning.
(b) Prove that 9 is not 100–discerning.
(Senior Problems Committee of the Australian Mathematical Olympiad Committee)
Solution.
(a) Take S = {3, 6, 12, 24, 48, 95, 96, 97}, i.e.

S = {3 · 2k : 0 ≤ k ≤ 5} ∪ {3 · 25 − 1, 3 · 25 + 1}.

2
 As k ranges between 0 to 5, the sums obtained from the numbers 3 · 2k are 3t, where
1 ≤ t ≤ 63. These are 63 numbers that are divisible by 3 and are at most 3 · 63 = 189.
Sums of elements of S are also the numbers 95 + 97 = 192 and all the numbers that
are sums of 192 and sums obtained from the numbers 3 · 2k with 0 ≤ k ≤ 5. These are 64
numbers that are all divisible by 3 and at least equal to 192. In addition, sums of elements
of S are the numbers 95 and all the numbers that are sums of 95 and sums obtained from
the numbers 3 · 2k with 0 ≤ k ≤ 5. These are 64 numbers that are all congruent to −1 mod
3.
Finally, sums of elements of S are the numbers 97 and all the numbers that are sums of
97 and sums obtained from the numbers 3 · 2k with 0 ≤ k ≤ 5. These are 64 numbers that
are all congruent to 1 mod 3.
Hence there are at least 63 + 64 + 64 + 64 = 255 different sums from elements of S. On
the other hand, S has 28 − 1 = 255 non-empty subsets. Therefore S has no two different
subsets with equal sums of elements. Therefore, 8 is 100-discerning.
(b) Suppose that 9 is 100-discerning. Then there is a set S = {s1 , . . . , s9 }, si < 100 that
has no two different subsets with equal sums of elements. Assume that 0 < s1 < · · · < s9 <
100.
Let X be the set of all subsets of S having at least 3 and at most 6 elements and let Y
be the set of all subsets of S having exactly 2 or 3 or 4 elements greater than s3 .
The set X consists of
       
9 9 9 9
+ + + = 84 + 126 + 126 + 84 = 420
3 4 5 6

subsets of S. The set in X with the largest sums of elements is {s4 , . . . , s9 } and the smallest
sums is in {s1 , s2 , s3 }. Thus the sum of the elements of each of the 420 sets in X is at least
s1 + s2 + s3 and at most s4 + · · · + s9 , which is one of (s4 + · · · + s9 ) − (s1 + s2 + s3 ) + 1 integers.
From the pigeonhole principle it follows that (s4 + · · · + s9 ) − (s1 + s2 + s3 ) + 1 ≥ 420, i.e.,

(s4 + · · · + s9 ) − (s1 + s2 + s3 ) ≥ 419. (1)

6



the number of subsets6
in Y . Observe that {s4 , . . . , s9 } has 2
Now let us calculate
6
2-element subsets, 3 3-element subsets and 4 4-element subsets, while {s1 , s2 , s3 } has
exactly 8 subsets. Hence the number of subsets of S in Y equals
     
6 6 6
8 + + = 8(15 + 20 + 15) = 400.
2 3 4

The set in Y with the largest sum of elements is {s1 , s2 , s3 , s6 , s7 , s8 , s9 } and the smallest
sum is in {s4 , s5 }. Again, by the pigeonhole principle it follows that (s1 + s2 + s3 + s6 + s7 +
s8 + s9 ) − (s4 + s5 ) + 1 ≥ 400, i.e.,

(s1 + s2 + s3 + s6 + s7 + s8 + s9 ) − (s4 + s5 ) ≥ 399. (2)

Adding (1) and (2) yields 2(s6 + s7 + s8 + s9 ) ≥ 818, so that s9 + 98 + 97 + 96 ≥

s9 + s8 + s7 + s6 ≥ 409, i.e. s9 ≥ 118, a contradiction with s9 < 100. Therefore, 9 is not
100-discerning.

3
 Problem 5. Circles ω and Ω meet at points A and B. Let M be the midpoint of the
arc AB of circle ω (M lies inside Ω). A chord M P of circle ω intersects Ω at Q (Q lies inside
ω). Let `P be the tangent line to ω at P , and let `Q be the tangent line to Ω at Q. Prove
that the circumcircle of the triangle formed by the lines `P , `Q , and AB is tangent to Ω.
(Ilya Bogdanov, Russia and Medeubek Kungozhin, Kazakhstan)
Solution. Denote X = AB ∩ `P , Y = AB ∩ `Q , and Z = `P ∩ `Q . Without loss of
generality we have AX < BX. Let F = M P ∩ AB.

`Q
`P

X Z

YY
YY
D
D
D
D

A
A
A
A
P
S

Q
F
M
Ω

B
B
B

Denote by R the second point of intersection of P Q and Ω; by S the point of Ω such that
SR k AB; and by T the point of Ω such that RT k `P . Since M is the midpoint of arc AB,
the tangent `M at M to ω is parallel to AB, so ∠(AB, P M ) = ∠(P M, `P ). Therefore we
have ∠P RT = ∠M P X = ∠P F X = ∠P RS. Thus the point Q is the midpoint of the
arc T QS of Ω, hence ST k `Q . So the corresponding sides of the triangles RST and XY Z
are parallel, and there exist a homothety h mapping RST to XY Z.
Let D be the second point of intersection of XR and Ω. We claim that D is the center of
the homothety h; since D ∈ Ω, this implies that the circumcircles of triangles RST and XY Z
are tangent, as required. So, it remains to prove this claim. In order to do this, it suffices to
show that D ∈ SY .
By ∠P F X = ∠XP F we have XF 2 = XP 2 = XA · XB = XD · XR. Therefore,
XF XR
XD
= XF , so the triangles XDF and XF R are similar, hence ∠DF X = ∠XRF = ∠DRQ =
∠DQY ; thus the points D, Y , Q, and F are concyclic. It follows that ∠Y DQ = ∠Y F Q =
∠SRQ = 180◦ − ∠SDQ which means exactly that the points Y , D, and S are collinear, with
D between S and Y .

4
 Solutions of APMO 2015

Problem 1. Let ABC be a triangle, and let D be a point on side BC. A line through
D intersects side AB at X and ray AC at Y . The circumcircle of triangle BXD intersects the
circumcircle ω of triangle ABC again at point Z 6= B. The lines ZD and ZY intersect ω again
at V and W , respectively. Prove that AB = V W .
Solution. Suppose XY intersects ω at points P and Q, where Q lies between X and Y . We
will show that V and W are the reflections of A and B with respect to the perpendicular bisector
of P Q. From this, it follows that AV W B is an isosceles trapezoid and hence AB = V W .
First, note that

∠BZD = ∠AXY = ∠AP Q + ∠BAP = ∠AP Q + ∠BZP,

so ∠AP Q = ∠P ZV = ∠P QV , and hence V is the reflection of A with respect to the perpen-

dicular bisector of P Q.
Now, suppose W 0 is the reflection of B with respect to the perpendicular bisector of P Q,
and let Z 0 be the intersection of Y W 0 and ω. It suffices to show that B, X, D, Z 0 are concyclic.
Note that

∠Y DC = ∠P DB = ∠P CB + ∠QP C = ∠W 0 P Q + ∠QP C = ∠W 0 P C = ∠Y Z 0 C.

So D, C, Y , Z 0 are concyclic. Next, ∠BZ 0 D = ∠CZ 0 B − ∠CZ 0 D = 180◦ − ∠BXD and due to
the previous concyclicity we are done.
Alternative solution 1. Using cyclic quadrilaterals BXDZ and ABZV in turn, we have
∠ZDY = ∠ZBA = ∠ZCY. So ZDCY is cyclic.
Using cyclic quadrilaterals ABZC and ZDCY in turn, we have ∠AZB = ∠ACB = ∠W ZV
(or 180◦ − ∠W ZV if Z lies between W and C).
So AB = V W because they subtend equal (or supplementary) angles in ω. 
Alternative solution 2. Using cyclic quadrilaterals BXDZ and ABZV in turn, we have
∠ZDY = ∠ZBA = ∠ZCY. So ZDCY is cyclic.
Using cyclic quadrilaterals BXDZ and ABZV in turn, we have ∠DXA = ∠V ZB =
180◦ − BAV. So XD k AV .
Using cyclic quadrilaterals ZDCY and BCW Z in turn, we have ∠Y DC = ∠Y ZC =
∠W BC. So XD k BW .
Hence BW k AV which implies that AV W B is an isosceles trapezium with AB = V W . 
Problem 2. Let S = {2, 3, 4, . . .} denote the set of integers that are greater than or equal
to 2. Does there exist a function f : S → S such that

f (a)f (b) = f (a2 b2 ) for all a, b ∈ S with a 6= b?

Solution. We prove that there is no such function. For arbitrary elements a and b of S,
choose an integer c that is greater than both of them. Since bc > a and c > b, we have

f (a4 b4 c4 ) = f (a2 )f (b2 c2 ) = f (a2 )f (b)f (c).

Furthermore, since ac > b and c > a, we have

f (a4 b4 c4 ) = f (b2 )f (a2 c2 ) = f (b2 )f (a)f (c).

Comparing these two equations, we find that for all elements a and b of S,
f (a2 ) f (b2 )
f (a2 )f (b) = f (b2 )f (a) =⇒ = .
f (a) f (b)

1
It follows that there exists a positive rational number k such that

f (a2 ) = kf (a), for all a ∈ S. (1)

Substituting this into the functional equation yields

f (a)f (b)
f (ab) = , for all a, b ∈ S with a 6= b. (2)
k
Now combine the functional equation with equations (1) and (2) to obtain

f (a)f (a5 ) f (a)f (a)f (a4 ) f (a)f (a)f (a2 )

f (a)f (a2 ) = f (a6 ) = = = , for all a ∈ S.
k k2 k
It follows that f (a) = k for all a ∈ S. Substituting a = 2 and b = 3 into the functional equation
yields k = 1, however 1 6∈ S and hence we have no solutions.
Problem 3. A sequence of real numbers a0 , a1 , . . . is said to be good if the following three
conditions hold.

(i) The value of a0 is a positive integer.

ai
(ii) For each non-negative integer i we have ai+1 = 2ai + 1 or ai+1 = .
ai + 2
(iii) There exists a positive integer k such that ak = 2014.

Find the smallest positive integer n such that there exists a good sequence a0 , a1 , . . . of real
numbers with the property that an = 2014.
Answer: 60.
Solution. Note that
ai + ai + 2 2(ai + 1)
ai+1 + 1 = 2(ai + 1) or ai+1 + 1 = = .
ai + 2 ai + 2
Hence
1 1 1 1 ai + 2 1 1 1
= · or = = · + .
ai+1 + 1 2 ai + 1 ai+1 + 1 2(ai + 1) 2 ai + 1 2
Therefore,
k
1 1 1 X εi
= k· + , (1)
ak + 1 2 a0 + 1 i=1 2k−i+1

where εi = 0 or 1. Multiplying both sides by 2k (ak + 1) and putting ak = 2014, we get

k
!
2015 X
2k = + 2015 · εi · 2i−1 ,
a0 + 1 i=1

where εi = 0 or 1. Since gcd(2, 2015) = 1, we have a0 + 1 = 2015 and a0 = 2014. Therefore,

k
!
X
2k − 1 = 2015 · εi · 2i−1 ,
i=1

where εi = 0 or 1. We now need to find the smallest k such that 2015|2k − 1. Since 2015 =
5 · 13 · 31, from the Fermat little theorem we obtain 5|24 − 1, 13|212 − 1 and 31|230 − 1. We also
have lcm[4, 12, 30] = 60, hence 5|260 − 1, 13|260 − 1 and 31|260 − 1, which gives 2015|260 − 1.

2
But 5 - 230 − 1 and so k = 60 is the smallest positive integer such that 2015|2k − 1. To conclude,
the smallest positive integer k such that ak = 2014 is when k = 60.
Alternative solution 1. Clearly all members of the sequence are positive rational numbers.
ai+1 − 1 2ai+1
For each positive integer i, we have ai = or ai = . Since ai > 0 we deduce
2 1 − ai+1
that 
 ai+1 − 1 if ai+1 > 1

2

ai = 2a i+1
if ai+1 < 1.


1 − ai+1


Thus ai is uniquely determined from ai+1 . Hence starting from ak = 2014, we simply run the
sequence backwards until we reach a positive integer. We compute as follows.
2014 2013 2011 2007 1999 1983 1951 1887 1759 1503 991 1982 1949 1883 1751 1487 959 1918 1821 1627
1
, 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 , 512 , 1024 , 33 , 66 , 132 , 264 , 528 , 1056 , 97 , 194 , 388 ,

1239 463 926 1852 1689 1363 711 1422 829 1658 1301 587 1174 333 666 1332 649 1298 581 1162
, , , , , , , , , , , , , , , , , , ,
776 1552 1089 163 326 652 1304 593 1186 357 714 1428 841 1682 1349 683 1366 717 1434 853
,

309 618 1236 457 914 1828 1641 1267 519 1038 61
, , , , , , , , , , , 122 , 244 , 488 , 976 , 1952 , 1889
1706 1397 779 1558 1101 187 374 748 1496 977 1954 1893 1771 1527 1039 63
, 1763 , 1511 , 1007 , 2014
126 252 504 1008 1
.

There are 61 terms in the above list. Thus k = 60. 

Alternative solution 1 is quite computationally intensive. Calculating the first few terms
indicates some patterns that are easy to prove. This is shown in the next solution.
m0
Alternative solution 2. Start with ak = where m0 = 2014 and n0 = 1 as in alternative
n0
mi
solution 1. By inverting the sequence as in alternative solution 1, we have ak−i = for i ≥ 0
ni
where
(mi − ni , 2ni ) if mi > ni

(mi+1 , ni+1 ) =
(2mi , ni − mi ) if mi < ni .
Easy inductions show that mi + ni = 2015, 1 ≤ mi , ni ≤ 2014 and gcd(mi , ni ) = 1 for
i ≥ 0. Since a0 ∈ N+ and gcd(mk , nk ) = 1, we require nk = 1. An easy induction shows that
(mi , ni ) ≡ (−2i , 2i ) (mod 2015) for i = 0, 1, . . . , k.
Thus 2k ≡ 1 (mod 2015). As in the official solution, the smallest such k is k = 60. This
yields nk ≡ 1 (mod 2015). But since 1 ≤ nk , mk ≤ 2014, it follows that a0 is an integer. 
Problem 4. Let n be a positive integer. Consider 2n distinct lines on the plane, no two
of which are parallel. Of the 2n lines, n are colored blue, the other n are colored red. Let B be
the set of all points on the plane that lie on at least one blue line, and R the set of all points
on the plane that lie on at least one red line. Prove that there exists a circle that intersects B
in exactly 2n − 1 points, and also intersects R in exactly 2n − 1 points.
Solution. Consider a line ` on the plane and a point P on it such that ` is not parallel to
any of the 2n lines. Rotate ` about P counterclockwise until it is parallel to one of the 2n lines.
Take note of that line and keep rotating until all the 2n lines are met. The 2n lines are now
ordered according to which line is met before or after. Say the lines are in order `1 , . . . , `2n .
Clearly there must be k ∈ {1, . . . , 2n − 1} such that `k and `k+1 are of different colors.
Now we set up a system of X– and Y – axes on the plane. Consider the two angular bisectors
of `k and `k+1 . If we rotate `k+1 counterclockwise, the line will be parallel to one of the bisectors
before the other. Let the bisector that is parallel to the rotation of `k+1 first be the X–axis,
and the other the Y –axis. From now on, we will be using the directed angle notation: for lines
s and s0 , we define ∠(s, s0 ) to be a real number in [0, π) denoting the angle in radians such
that when s is rotated counterclockwise by ∠(s, s0 ) radian, it becomes parallel to s0 . Using this

3
notation, we notice that there is no i = 1, . . . , 2n such that ∠(X, li ) is between ∠(X, `k ) and
∠(X, `k+1 ).
Because the 2n lines are distinct, the set S of all the intersections between `i and `j (i 6= j)
is a finite set of points. Consider a rectangle with two opposite vertices lying on `k and the
other two lying on `k+1 . With respect to the origin (the intersection of `k and `k+1 ), we can
enlarge the rectangle as much as we want, while all the vertices remain on the lines. Thus,
there is one of these rectangles R which contains all the points in S in its interior. Since each
side of R is parallel to either X– or Y – axis, R is a part of the four lines x = ±a, y = ±b.
where a, b > 0.

Y
lk+1 lk
b
M
N
−a a X

−b

Consider the circle C tangent to the right of the x = a side of the rectangle, and to both `k
and `k+1 . We claim that this circle intersects B in exactly 2n − 1 points, and also intersects R
in exactly 2n − 1 points. Since C is tangent to both `k and `k+1 and the two lines have different
colors, it is enough to show that C intersects with each of the other 2n − 2 lines in exactly 2
points. Note that no two lines intersect on the circle because all the intersections between lines
are in S which is in the interior of R.
Consider any line L among these 2n − 2 lines. Let L intersect with `k and `k+1 at the points
M and N , respectively (M and N are not necessarily distinct). Notice that both M and N
must be inside R. There are two cases:
(i) L intersects R on the x = −a side once and another time on x = a side;
(ii) L intersects y = −b and y = b sides.
However, if (ii) happens, ∠(`k , L) and ∠(L, `k+1 ) would be both positive, and then ∠(X, L)
would be between ∠(X, `k ) and ∠(X, `k+1 ), a contradiction. Thus, only (i) can happen. Then
L intersects C in exactly two points, and we are done.

Alternative solution. By rotating the diagram we can ensure that no line is vertical. Let
`1 , `2 , . . . , `2n be the lines listed in order of increasing gradient. Then there is a k such that lines
`k and `k+1 are oppositely coloured. By rotating our coordinate system and cyclicly relabelling
our lines we can ensure that `1 , `2 , . . . , `2n are listed in order of increasing gradient, `1 and `2n
are oppositely coloured, and no line is vertical.
Let D be a circle centred at the origin and of sufficiently large radius so that

• All intersection points of all pairs of lines lie strictly inside D; and

• Each line `i intersects D in two points Ai and Bi say, such that Ai is on the right semicircle
(the part of the circle in the positive x half plane) and Bi is on the left semicircle.

Note that the anticlockwise order of the points Ai , Bi around D is A1 , A2 , . . . , An , B1 , B2 , . . . , Bn .

4
(If Ai+1 occurred before Ai then rays ri and ri+1 (as defined below) would intersect outside D.)
r2n
r2n−1

B1 A2n
A2n−1
B2 C
B2n−1 A2
B2n A1

r2
r1

For each i, let ri be the ray that is the part of the line `i starting from point Ai and that
extends to the right. Let C be any circle tangent to r1 and r2n , that lies entirely to the right
of D. Then C intersects each of r2 , r3 , . . . , r2n−1 twice and is tangent to r1 and r2n . Thus C has
the required properties. 
Problem 5. Determine all sequences a0 , a1 , a2 , . . . of positive integers with a0 ≥ 2015
such that for all integers n ≥ 1:
(i) an+2 is divisible by an ;
(ii) |sn+1 − (n + 1)an | = 1, where sn+1 = an+1 − an + an−1 − · · · + (−1)n+1 a0 .
Answer: There are two families of answers:
(a) an = c(n + 2)n! for all n ≥ 1 and a0 = c + 1 for some integer c ≥ 2014, and
(b) an = c(n + 2)n! for all n ≥ 1 and a0 = c − 1 for some integer c ≥ 2016.
Solution. Let {an }∞ n=0 be a sequence of positive integers satisfying the given conditions.
We can rewrite (ii) as sn+1 = (n + 1)an + hn , where hn ∈ {−1, 1}. Substituting n with n − 1
yields sn = nan−1 + hn−1 , where hn−1 ∈ {−1, 1}. Note that an+1 = sn+1 + sn , therefore there
exists δn ∈ {−2, 0, 2} such that
an+1 = (n + 1)an + nan−1 + δn . (1)
We also have |s2 − 2a1 | = 1, which yields a0 = 3a1 − a2 ± 1 ≤ 3a1 , and therefore a1 ≥ a30 ≥ 671.
Substituting n = 2 in (1), we find that a3 = 3a2 + 2a1 + δ2 . Since a1 |a3 , we have a1 |3a2 + δ2 ,
and therefore a2 ≥ 223. Using (1), we obtain that an ≥ 223 for all n ≥ 0.
Lemma 1: For n ≥ 4, we have an+2 = (n + 1)(n + 4)an .
Proof. For n ≥ 3 we have
an = nan−1 + (n − 1)an−2 + δn−1 > nan−1 + 3. (2)
By applying (2) with n substituted by n − 1 we have for n ≥ 4,
an = nan−1 + (n − 1)an−2 + δn−1 < nan−1 + (an−1 − 3) + δn−1 < (n + 1)an−1 . (3)
Using (1) to write an+2 in terms of an and an−1 along with (2), we obtain that for n ≥ 3,
an+2 = (n + 3)(n + 1)an + (n + 2)nan−1 + (n + 2)δn + δn+1
< (n + 3)(n + 1)an + (n + 2)nan−1 + 3(n + 2)
< (n2 + 5n + 5)an .

5
Also for n ≥ 4,

an+2 = (n + 3)(n + 1)an + (n + 2)nan−1 + (n + 2)δn + δn+1

> (n + 3)(n + 1)an + nan
= (n2 + 5n + 3)an .

Since an |an+2 , we obtain that an+2 = (n2 + 5n + 4)an = (n + 1)(n + 4)an , as desired. 
(n + 1)(n + 3)
Lemma 2: For n ≥ 4, we have an+1 = n+2 an .
Proof. Using the recurrence an+3 = (n + 3)an+2 + (n + 2)an+1 + δn+2 and writing an+3 ,
an+2 in terms of an+1 , an according to Lemma 1 we obtain

(n + 2)(n + 4)an+1 = (n + 3)(n + 1)(n + 4)an + δn+2 .

(n + 1)(n + 3)
Hence n + 4|δn+2 , which yields δn+2 = 0 and an+1 = n+2 an , as desired. 
(n + 1)(n + 3)
Suppose there exists n ≥ 1 such that an+1 6= n+2 an . By Lemma 2, there exist a
(m + 2)(m + 4)
greatest integer 1 ≤ m ≤ 3 with this property. Then am+2 = m+3 am+1 . If δm+1 = 0,
(m + 1)(m + 3)
we have am+1 = m+2 am , which contradicts our choice of m. Thus δm+1 6= 0.
Clearly m + 3|am+1 . Write am+1 = (m + 3)k and am+2 = (m + 2)(m + 4)k. Then (m +
1)am + δm+1 = am+2 − (m + 2)am+1 = (m + 2)k. So, am |(m + 2)k − δm+1 . But am also divides
am+2 = (m + 2)(m + 4)k. Combining the two divisibility conditions, we obtain am |(m + 4)δm+1 .
Since δm+1 6= 0, we have am |2m + 8 ≤ 14, which contradicts the previous result that an ≥ 223
for all nonnegative integers n.
(n + 1)(n + 3)
So, an+1 = n+2 an for n ≥ 1. Substituting n = 1 yields 3|a1 . Letting a1 = 3c,
we have by induction that an = n!(n + 2)c for n ≥ 1. Since |s2 − 2a1 | = 1, we then get
a0 = c ± 1, yielding the two families of solutions. By noting that (n + 2)n! = n! + (n + 1)!,
we have sn+1 = c(n + 2)! + (−1)n (c − a0 ). Hence both families of solutions satisfy the given
conditions.

6
 Solutions of APMO 2016

Problem 1. We say that a triangle ABC is great if the following holds: for any point
D on the side BC, if P and Q are the feet of the perpendiculars from D to the lines AB and
AC, respectively, then the reflection of D in the line P Q lies on the circumcircle of the triangle
ABC.
Prove that triangle ABC is great if and only if ∠A = 90◦ and AB = AC.
Solution. For every point D on the side BC, let D0 be the reflection of D in the line P Q.
We will first prove that if the triangle satisfies the condition then it is isosceles and right-angled
at A.
Choose D to be the point where the angle bisector from A meets BC. Note that P and Q
lie on the rays AB and AC respectively. Furthermore, P and Q are reflections of each other
in the line AD, from which it follows that P Q ⊥ AD. Therefore, D0 lies on the line AD and
we may deduce that either D0 = A or D0 is the second point of the angle bisector at A and
the circumcircle of ABC. However, since AP DQ is a cyclic quadrilateral, the segment P Q
intersects the segment AD. Therefore, D0 lies on the ray DA and therefore D0 = A. By angle
chasing we obtain

∠P D0 Q = ∠P DQ = 180◦ − ∠BAC,
and since D0 = A we also know ∠P D0 Q = ∠BAC. This implies that ∠BAC = 90◦ .
Now we choose D to be the midpoint of BC. Since ∠BAC = 90◦ , we can deduce that
DQP is the medial triangle of triangle ABC. Therefore, P Q||BC from which it follows that
DD0 ⊥ BC. But the distance from D0 to BC is equal to both the circumradius of triangle
ABC and to the distance from A to BC. This can only happen if A = D0 . This implies that
ABC is isosceles and right-angled at A.

We will now prove that if ABC is isosceles and right-angled at A then the required property
in the problem holds. Let D be any point on side BC. Then D0 P = DP and we also have
DP = BP . Hence, D0 P = BP and similarly D0 Q = CQ. Note that AP DQD0 is cyclic
with diameter P Q. Therefore, ∠AP D0 = ∠AQD0 , from which we obtain ∠BP D0 = ∠CQD0 .
So triangles D0 P B and D0 QC are similar. It follows that ∠P D0 Q = ∠P D0 C + ∠CD0 Q =
0 0
∠P D0 C + ∠BD0 P = ∠BD0 C and D0 P = D 0 B . So we also obtain that triangles D0 P Q and
DQ DC
D0 BC are similar. But since DP Q and D0 P Q are congruent, we may deduce that ∠BD0 C =
∠P D0 Q = ∠P DQ = 90◦ . Therefore, D0 lies on the circle with diameter BC, which is the
circumcircle of triangle ABC.

Problem 2. A positive integer is called fancy if it can be expressed in the form

1
 2a1 + 2a2 + · · · + 2a100 ,
where a1 , a2 , . . . , a100 are non-negative integers that are not necessarily distinct.
Find the smallest positive integer n such that no multiple of n is a fancy number.
Answer: The answer is n = 2101 − 1.
Solution. Let k be any positive integer less than 2101 − 1. Then k can be expressed
in binary notation using at most 100 ones, and therefore there exists a positive integer r and
non-negative integers a1 , a2 , . . . , ar such that r ≤ 100 and k = 2a1 + · · · + 2ar . Notice that for
a positive integer s we have:

2s k = 2a1 +s + 2a2 +s + · · · + 2ar−1 +s + (1 + 1 + 2 + · · · + 2s−1 )2ar

= 2a1 +s + 2a2 +s + · · · + 2ar−1 +s + 2ar + 2ar + · · · + 2ar +s−1 .

This shows that k has a multiple that is a sum of r + s powers of two. In particular, we
may take s = 100 − r ≥ 0, which shows that k has a multiple that is a fancy number.
We will now prove that no multiple of n = 2101 − 1 is a fancy number. In fact we will prove
a stronger statement, namely, that no multiple of n can be expressed as the sum of at most
100 powers of 2.
For the sake of contradiction, suppose that there exists a positive integer c such that cn is
the sum of at most 100 powers of 2. We may assume that c is the smallest such integer. By
repeatedly merging equal powers of two in the representation of cn we may assume that

cn = 2a1 + 2a2 + · · · + 2ar

where r ≤ 100 and a1 < a2 < . . . < ar are distinct non-negative integers. Consider the following
two cases:

• If ar ≥ 101, then 2ar − 2ar −101 = 2ar −101 n. It follows that 2a1 + 2a2 + · · · + 2ar−1 + 2ar −101
would be a multiple of n that is smaller than cn. This contradicts the minimality of c.

• If ar ≤ 100, then {a1 , . . . , ar } is a proper subset of {0, 1, . . . , 100}. Then

n ≤ cn < 20 + 21 + · · · + 2100 = n.

This is also a contradiction.

From these contradictions we conclude that it is impossible for cn to be the sum of at most
100 powers of 2. In particular, no multiple of n is a fancy number.

Problem 3. Let AB and AC be two distinct rays not lying on the same line, and let ω
be a circle with center O that is tangent to ray AC at E and ray AB at F . Let R be a point
on segment EF . The line through O parallel to EF intersects line AB at P . Let N be the
intersection of lines P R and AC, and let M be the intersection of line AB and the line through
R parallel to AC. Prove that line M N is tangent to ω.
Solution. We present two approaches. The first one introduces an auxiliary point and
studies similarities in the figure. The second one reduces the problem to computations involving
a particular exradius of a triangle. The second approach has two variants.
Solution 1.

2
 Let the line through N tangent to ω at point X 6= E intersect AB at point M 0 . It suffices
to show that M 0 R k AC, since this would yield M 0 = M .
Suppose that the line P O intersects AC at Q and the circumcircle of AM 0 O at Y , respec-
tively. Then

∠AY M 0 = ∠AOM 0 = 90◦ − ∠M 0 OP.

By angle chasing we have ∠EOQ = ∠F OP = 90◦ − ∠AOF = ∠M 0 AO = ∠M 0 Y P and by
symmetry ∠EQO = ∠M 0 P Y . Therefore 4M 0 Y P ∼ 4EOQ.
On the other hand, we have

1
∠M 0 OP = ∠M 0 OF + ∠F OP = (∠F OX + ∠F OP + ∠EOQ) =
 2
1 180◦ − ∠XOE

∠XOE
= = 90◦ − .
2 2 2

Since we know that ∠AY M 0 and ∠M 0 OP are complementary this implies

∠XOE
∠AY M 0 = = ∠N OE.
2
Therefore, ∠AY M 0 and ∠N OE are congruent angles, and this means that A and N are
corresponding points in the similarity of triangles 4M 0 Y P and 4EOQ. It follows that

AM 0 NE NR
= = .
M 0P EQ RP
We conclude that M 0 R k AC, as desired.

Solution 2a.

3
 PR = PM0 .
As in Solution 1, we introduce point M 0 and reduce the problem to proving RN
M 0A
Menelaus theorem in triangle AN P with transversal line F RE yields
P R N E AF
· · = 1.
RN EA F P
F P = P R , so that it suffices to prove
Since AF = EA, we have N E RN
FP P M0
= 0 . (1)
NE MA
This is a computation regarding the triangle AM 0 N and its excircle opposite A. Indeed,
setting a = M 0 N , b = N A, c = M 0 A, s = a + 2b + c , x = s − a, y = s − b and z = s − c, then
r2
AE = AF = s, M 0 F = z and N E = y. From 4OF P ∼ 4AF O we have F P = sa , where
ra = OF is the exradius opposite A. Combining the following two standard formulas for the
area of a triangle

|AM 0 N |2 = xyzs (Heron’s formula) and |AM 0 N | = ra (s − a),

we have ra2 = yzs yz
x . Therefore, F P = x . We can now write everything in (1) in terms of x, y, z.
We conclude that we have to verify
yz
x z + yz
x
= ,
y x+y
which is easily seen to be true.
Note: Antoher approach using Menalaus theorem is to construct the tangent from M to
create a point N 0 in AC and then prove, using the theorem, that P , R and N 0 are collinear.
This also reduces to an algebraic identity.
Solution 2b.
As in Solution 1, we introduce point M 0 . Let the line through M 0 and parallel to AN
intersect EF at R0 . Let P 0 be the intersection of lines N R0 and AM . It suffices to show that
P 0 O k F E, since this would yield P = P 0 , and then R = R0 and M = M 0 . Hence it is enough
to prove that
AF AD
0
= , (2)
FP DO
where D is the intersection of AO and EF . Once again, this reduces to a computation regarding
the triangle AM 0 N and its excircle opposite A.
Let u = P 0 F and x, y, z, s as in Solution 2a. Note that since AE = AF and M 0 R0 k AE, we
0 0 0 R0
have M 0 R0 = M 0 F = z. Since M 0 R0 k AN , we have P M 0 =M
N A , that is,
PA
u+z z
= .
u+x+y+z x+z
From this last equation we obtain u = yz AF xs
x . Hence F P 0 = yz . Also, as in Solution 2a, we have
ra2 = yzs
x .
Finally, using similar triangles ODF , F DA and OF A, and the above equalities, we have

AD AD DF AF AF s2 s2 xs AF
= · = · = 2 = yzs = = 0
,
DO DF DO OF OF ra x yz F P
as required.

4
 Problem 4. The country Dreamland consists of 2016 cities. The airline Starways wants to
establish some one-way flights between pairs of cities in such a way that each city has exactly
one flight out of it. Find the smallest positive integer k such that no matter how Starways
establishes its flights, the cities can always be partitioned into k groups so that from any city
it is not possible to reach another city in the same group by using at most 28 flights.
Answer: 57
Solution. The flights established by Starways yield a directed graph G on 2016 vertices
in which each vertex has out-degree equal to 1.
We first show that we need at least 57 groups. For this, suppose that G has a directed cycle
of length 57. Then, for any two cities in the cycle, one is reachable from the other using at
most 28 flights. So no two cities in the cycle can belong to the same group. Hence, we need at
least 57 groups.
We will now show that 57 groups are enough. Consider another auxiliary directed graph H
in which the vertices are the cities of Dreamland and there is an arrow from city u to city v
if u can be reached from v using at most 28 flights. Each city has out-degree at most 28. We
will be done if we can split the cities of H in at most 57 groups such that there are no arrows
between vertices of the same group. We prove the following stronger statement.
Lemma: Suppose we have a directed graph on n ≥ 1 vertices such that each vertex has
out-degree at most 28. Then the vertices can be partitioned into 57 groups in such a way that
no vertices in the same group are connected by an arrow.
Proof: We apply induction. The result is clear for 1 vertex. Now suppose we have more
than one vertex. Since the out-degree of each vertex is at most 28, there is a vertex, say v, with
in-degree at most 28. If we remove the vertex v we obtain a graph with fewer vertices which
still satifies the conditions, so by inductive hypothesis we may split it into at most 57 groups
with no adjacent vertices in the same group. Since v has in-degree and out-degree at most 28,
it has at most 56 neighboors in the original directed graph. Therefore, we may add v back and
place it in a group in which it has no neighbors. This completes the inductive step.

Problem 5. Find all functions f : R+ → R+ such that

(z + 1)f (x + y) = f (xf (z) + y) + f (yf (z) + x), (3)

for all positive real numbers x, y, z.

Answer: The only solution is f (x) = x for all positive real numbers x.
Solution. The identity function f (x) = x clearly satisfies the functional equation. Now,
let f be a function satisfying the functional equation. Plugging x = y = 1 into (3) we get
2f (f (z) + 1) = (z + 1)(f (2)) for all z ∈ R+ . Hence, f is not bounded above.
Lemma. Let a, b, c be positive real numbers. If c is greater than 1, a/b and b/a, then the
system of linear equations

cu + v = a u + cv = b
has a positive real solution u, v.
Proof. The solution is
ca − b cb − a
u=2
v= 2 .
c −1 c −1
The numbers u and v are positive if the conditions on c above are satisfied.


5
 We will now prove that

f (a) + f (b) = f (c) + f (d) for all a, b, c, d ∈ R+ with a + b = c + d. (4)

Consider a, b, c, d ∈ R+ such that a + b = c + d. Since f is not bounded above, we can
choose a positive number e such that f (e) is greater than 1, a/b, b/a, c/d and d/c. Using the
above lemma, we can find u, v, w, t ∈ R+ satisfying

f (e)u + v = a, u + f (e)v = b
f (e)w + t = c, w + f (e)t = d.
Note that u + v = w + t since (u + v)(f (e) + 1) = a + b and (w + t)(f (e) + 1) = c + d.
Plugging x = u, y = v and z = e into (3) yields f (a) + f (b) = (e + 1)f (u + v). Similarly, we
have f (c) + f (d) = (e + 1)f (w + t). The claim follows immediately.
We then have

yf (x) = f (xf (y)) for all x, y ∈ R+ (5)

since by (3) and (4),
x x x x
(y + 1)f (x) = f f (y) + +f f (y) + = f (xf (y)) + f (x).
2 2 2 2
Now, let a = f (1/f (1)). Plugging x = 1 and y = 1/f (1) into (5) yields f (a) = 1. Hence
a = af (a) and f (af (a)) = f (a) = 1. Since af (a) = f (af (a)) by (5), we have f (1) = a = 1. It
follows from (5) that

f (f (y)) = y for all y ∈ R+ . (6)

Using (4) we have for all x, y ∈ R+ that

f (x + y) + f (1) = f (x) + f (y + 1), and

f (y + 1) + f (1) = f (y) + f (2).
Therefore

f (x + y) = f (x) + f (y) + b for all x, y ∈ R+ , (7)

where b = f (2) − 2f (1) = f (2) − 2. Using (5), (7) and (6), we get

4 + 2b = 2f (2) = f (2f (2)) = f (f (2) + f (2)) = f (f (2)) + f (f (2)) + b = 4 + b.

This shows that b = 0 and thus

f (x + y) = f (x) + f (y) for all x, y ∈ R+ .

In particular, f is strictly increasing.
We conclude as follows. Take any positive real number x. If f (x) > x, then f (f (x)) >
f (x) > x = f (f (x)), a contradiction. Similarly, it is not possible that f (x) < x. This shows
that f (x) = x for all positive real numbers x.


6
 Solutions of APMO 2017

Problem 1. We call a 5-tuple of integers arrangeable if its elements can be labeled a,

b, c, d, e in some order so that a − b + c − d + e = 29. Determine all 2017-tuples of integers
n1 , n2 , . . . , n2017 such that if we place them in a circle in clockwise order, then any 5-tuple of
numbers in consecutive positions on the circle is arrangeable.
Answer: n1 = · · · = n2017 = 29.
Solution. A valid 2017-tuple is n1 = · · · = n2017 = 29. We will show that it is the only
solution.
We first replace each number ni in the circle by mi := ni − 29. Since the condition a − b +
c − d + e = 29 can be rewritten as (a − 29) − (b − 29) + (c − 29) − (d − 29) + (e − 29) = 0, we
have that any five consecutive replaced integers in the circle can be labeled a, b, c, d, e in such
a way that a − b + c − d + e = 0. We claim that this is possible only when all of the mi ’s are 0
(and thus all of the original ni ’s are 29).
We work with indexes modulo 2017. Notice that for every i, mi and mi+5 have the same
parity. Indeed, this follows from mi ≡ mi+1 + mi+2 + mi+3 + mi+4 ≡ mi+5 (mod 2). Since
gcd(5, 2017) = 1, this implies that all mi ’s are of the same parity. Since m1 +m2 +m3 +m4 +m5
is even, all mi ’s must be even as well.
Suppose for the sake of contradiction that not all mi ’s are zero. Then our condition still
holds when we divide each number in the circle by 2. However, by performing repeated divisions,
we eventually reach a point where some mi is odd. This is a contradiction.

Problem 2. Let ABC be a triangle with AB < AC. Let D be the intersection point of
the internal bisector of angle BAC and the circumcircle of ABC. Let Z be the intersection
point of the perpendicular bisector of AC with the external bisector of angle ∠BAC. Prove
that the midpoint of the segment AB lies on the circumcircle of triangle ADZ.
Solution 1. Let N be the midpoint of AC. Let M be the intersection point of the
circumcircle of triangle ADZ and the segment AB. We will show that M is the midpoint of
AB. To do this, let D0 the reflection of D with respect to M . It suffices to show that ADBD0
is a parallelogram.
The internal and external bisectors of an angle in a triangle are perpendicular. This implies
that ZD is a diameter of the circumcircle of AZD and thus ∠ZM D = 90◦ . This means that
ZM is the perpendicular bisector of D0 D and thus ZD0 = ZD. By construction, Z is in the
perpendicular bisector of AC and thus ZA = ZC.
Now, let α be the angle ∠BAD = ∠DAC. In the cyclic quadrilateral AZDM we get
∠M ZD = ∠M AD = α, and thus ∠D0 ZD = 2α. By angle chasing we get

∠AZN = 90◦ − ∠ZAN = ∠DAC = α,

which implies that ∠AZC = 2α. Therefore,

∠D0 ZA = ∠D0 ZD − ∠AZD = 2α − ∠AZD = ∠AZC − ∠AZD = ∠DZC.

Combining ∠D0 ZA = ∠DZC, ZD0 = ZD and ZA = ZC, we obtain by the SAS criterion
that the triangles D0 ZA and DZC are congruent. In particular, D0 A = DC and ∠D0 AZ =
∠DCZ. From here DB = DC = D0 A.
Finally, let β = ∠ABC = ∠ADC. We get the first of the following equalities by the sum of
angles around point A and the second one by the sum of internal angles of quadrilateral AZCD

1
 360◦ = ∠D0 AZ + ∠ZAD + ∠DAB + ∠BAD0 = ∠D0 AZ + 90◦ + α + ∠BAD0
360◦ = ∠DCZ + ∠ZAD + ∠CZA + ∠ADC = ∠DCZ + 90◦ + 2α + β.
By canceling equal terms we conclude that ∠BAD0 = α + β. Also, ∠ABD = α + β.
Therefore, the segments D0 A and DB are parallel and have the same length. We conclude that
ADBD0 is a parallelogram. As the diagonals of a parallelogram intersect at their midpoints,
we obtain that M is the midpoint of AB as desired.


Variant of solution. The solution above is indirect in the sense that it assumes that M is
in the circumcircle of AZD and then shows that M is the midpoint of AB. We point out that
the same ideas in the solution can be used to give a direct solution. Here we present a sketch
on how to proceed in this manner.
Now we know that M is the midpoint of the side AB. We construct the point D0 in the
same way. Now we have directly that ADBD0 is a parallelogram and thus D0 A = DB = DC.
By construction ZA = ZC. Also, the two sums of angles equal to 360◦ in the previous solution
let us conclude that ∠D0 AZ = ∠DCZ. Once again, we use (differently) the SAS criterion and
obtain that the triangles D0 AZ and DCZ are congruent. Thus, D0 Z = DZ.
We finish the problem by noting that ZM is a median of the isosceles triangle D0 ZD, so it
is also a perpendicular bisector. This shows that ∠DM Z = 90◦ = ∠DAZ, and therefore M
lies in the circumcircle of DAZ.
Solution 2. We proceed directly. As above, we name

α = ∠DAC = ∠AZN = ∠CZN = ∠DCB.

Let L be the midpoint of the segment BC. Since M and N are midpoints of AB and AC, we
have that M N = CL and that the segment M N is parallel to BC. Thus, ∠AN M = ∠ACB.

2
Therefore, ∠ZN M = ∠ACB + 90◦ . Also, ∠DCZ = ∠DCB + ∠ACB + ∠ZCA = ∠ACB + 90◦ .
We conclude that ∠ZN M = ∠DCZ.
Now, the triangles ZN C and CLD are similar since ∠DCL = 90◦ = ∠CN Z and ∠DCL =
α = ∠CZN . We use this fact to obtain the following chain of equalities
CD CD CZ
= = .
MN CL ZN
We combine the equality above with ∠ZN M = ∠DCZ to conclude that the triangles
ZN M and ZCD are similar. In particular, ∠M ZN = ∠DZC and ZM ZD
ZN = ZC . Since we
also have ∠M ZD = ∠M ZN + ∠N ZD = ∠DZC + ∠N ZD = ∠N ZC, we conclude that the
triangles M ZD and N ZC are similar. This yields that ∠ZM D = 90◦ and therefore M is in
the circumcircle of triangle DAZ.

Solution 3. Let m be the perpendicular bisector of AD; thus m passes through the center
O of the circumcircle of triangle ABC. Since AD is the internal angle bisector of A and OM
and ON are perpendicular to AB and AC respectively, we obtain that OM and ON form equal
angles with AD. This implies that they are symmetric with respect to M .
Therefore, the line M O passes through the point Z 0 symmetrical to Z with respect to m.
Since ∠DAZ = 90◦ , then also ∠ADZ 0 = 90◦ . Moreover, since AZ = DZ 0 , we have that
∠AZZ 0 = ∠DZ 0 Z = 90◦ , so AZZ 0 D is a rectangle. Since ∠AM Z 0 = ∠AM O = 90◦ , we
conclude that M is in the circle with diameter AZ 0 , which is the circumcircle of the rectangle.
Thus M lies on the circumcircle of the triangle ADZ.
Problem 3. Let A(n) denote the number of sequences a1 ≥ a2 ≥ . . . ≥ ak of positive
integers for which a1 + · · · + ak = n and each ai + 1 is a power of two (i = 1, 2, . . . , k).
Let B(n) denote the number of sequences b1 ≥ b2 ≥ . . . ≥ bm of positive integers for which
b1 + · · · + bm = n and each inequality bj ≥ 2bj+1 holds (j = 1, 2, . . . , m − 1).
Prove that A(n) = B(n) for every positive integer n.
Solution. We say that a sequence a1 ≥ a2 ≥ . . . ≥ ak of positive integers has type A if
ai + 1 is a power of two for i = 1, 2, . . . , k. We say that a sequence b1 ≥ b2 ≥ . . . ≥ bm of
positive integer has type B if bj ≥ 2bj+1 for j = 1, 2, . . . , m − 1.
Recall that the binary representation of a positive integer expresses it as a sum of distinct
powers of two in a unique way. Furthermore, we have the following formula for every positive
integer N

2N − 1 = 2N −1 + 2N −2 + · · · + 21 + 20 .
Given a sequence a1 ≥ a2 ≥ . . . ≥ ak of type A, use the preceding formula to express each
term as a sum of powers of two. Write these powers of two in left-aligned rows, in decreasing
order of size. By construction, ai is the sum of the numbers in the ith row. For example, we
obtain the following array when we start with the type A sequence 15, 15, 7, 3, 3, 3, 1.

8 4 2 1
8 4 2 1
4 2 1
2 1
2 1
2 1
1
27 13 5 2

3
 Define the sequence b1 , b2 , . . . , bn by setting bj to be the sum of the numbers in the jth
column of the array. For example, we obtain the sequence 27, 13, 5, 2 from the array above.
We now show that this new sequence has type B. This is clear from the fact that each column
in the array contains at least as many entries as the column to the right of it and that each
number larger than 1 in the array is twice the number to the right of it. Furthermore, it is
clear that a1 + a2 + · · · + ak = b1 + b2 + · · · + bm , since both are equal to the sum of all the
entries in the array.
We now show that we can do this operation backwards. Suppose that we are given a type
B sequence b1 ≥ b2 ≥ . . . ≥ bm . We construct an array inductively as follows:

• We fill bm left-aligned rows with the numbers 2m−1 , 2m−2 , . . . , 21 , 20 .

• Then we fill bm−1 − 2bm left aligned rows with the numbers 2m−2 , 2m−3 , . . . , 21 , 20 .
• Then we fill bm−2 − 2bm−1 left aligned rows with the numbers 2m−3 , 2m−4 , . . . , 21 , 20 , and
so on.
• In the last step we fill b1 − 2b2 left-aligned rows with the number 1.

For example, if we start with the type B sequence 27, 13, 5, 2, we obtain once again the array
above. We define the sequence a1 , a2 , . . . , ak by setting ai to be the sum of the numbers in the
ith row of the array. By construction, this sequence has type A. Furthermore, it is clear that
a1 + · · · + ak = b1 + · · · + bm , since once again both sums are equal to the sum of all the entries
in the array.
We have defined an operation that starts with a sequence of type A, produces an array
whose row sums are given by the sequence, and outputs a sequence of type B corresponding
to the column sums. We have also defined an operation that starts with a sequence of type
B, produces an array whose column sums are given by the sequence, and outputs a sequence
of type A corresponding to the row sums. The arrays produced in both cases comprise left-
aligned rows of the form 2N −1 , 2N −2 , . . . , 21 , 20 , with non-increasing lengths. Let us refer to
arrays obeying these properties as marvelous.
To show that these two operations are inverses of each other, it then suffices to prove that
marvelous arrays are uniquely defined by either their row sums or their column sums. The
former is obviously true and the latter arises from the observation that each step in the above
inductive algorithm was forced in order to create a marvelous array with the prescribed column
sums.
Thus, we have produced a bijection between the sequences of type A with sum n and the
sequences of type B with sum n. So we can conclude that A(n) = B(n) for every positive
integer n.

Remark The solution above provides a bijection between type A and type B sequences via
an algorithm. There are alternative ways to provide such a bijection. For example, given the
numbers a1 ≥ . . . ≥ ak we may define the bi ’s as
X  ai + 1 
bj = .
i
2j
Conversely, given the numbers b1 ≥ . . . ≥ bm , one may define the ai ’s by taking, as in the
solution, bm numbers equal to 2m − 1, bm−1 − 2bm numbers equal to 2m−1 − 1, . . ., and b1 − 2b2
numbers equal to 21 − 1. One now needs to verify that these maps are mutually inverse.
k
Problem 4. Call a rational number r powerful if r can be expressed in the form pq
for some relatively prime positive integers p, q and some integer k > 1. Let a, b, c be positive

4
rational numbers such that abc = 1. Suppose there exist positive integers x, y, z such that
ax + by + cz is an integer. Prove that a, b, c are all powerful.
Solution. Let a = ab 1 , b = ab 2 , where gcd(a1 , b1 ) = gcd(a2 , b2 ) = 1. Then c = ab11 ba22 . The
1 2
condition that ax + by + cz is an integer becomes

a1x+z az2 by2 + az1 ay+z x x+z y+z

2 b1 + b1 b 2
∈ Z,
az1 az2 bx1 by2

which can be restated as

az1 az2 bx1 by2 | ax+z z y z y+z x x+z y+z

1 a2 b 2 + a1 a2 b 1 + b 1 b 2 . (1)

In particular, az1 divides the right-hand side. Since it divides the first and second terms in the
sum, we conclude that az1 | b1x+z by+z z y+z
2 . Since gcd(a1 , b1 ) = 1, we have a1 | b2 .

Let p be a prime that divides a1 . Let m, n ≥ 1 be integers such that pn ka1 (i.e. pn |a1
but pn+1 - a1 ) and pm kb2 . The fact that az1 | b2y+z implies nz ≤ m(y + z). Since gcd(a1 , b1 ) =
gcd(a2 , b2 ) = 1, we have p does not divide b1 and does not divide a2 . Thus

pnz kaz1 ay+z x

2 b1 and p
m(y+z) x+z y+z
kb1 b2 . (2)

On the other hand, (1) implies that

pnz+my | az1 a2y+z bx1 + bx+z y+z

1 b2 . (3)

If nz < m(y + z), then (2) gives pnz kaz1 a2y+z bx1 + bx+z y+z
1 b2 , which contradicts (3). Thus
y+z
nz = m(y + z) so n is divisible by k := gcd(z, y + z)
> 1. Thus each exponent in the prime
decomposition of a1 must be divisible by k. Hence a1 is a perfect k-power which means a is
powerful. Similarly, b and c are also powerful.

Problem 5. Let n be a positive integer. A pair of n-tuples (a1 , . . . , an ) and (b1 , . . . , bn )
with integer entries is called an exquisite pair if

|a1 b1 + · · · + an bn | ≤ 1.
Determine the maximum number of distinct n-tuples with integer entries such that any two
of them form an exquisite pair.
Answer: The maximum is n2 + n + 1.
Solution. First, we construct an example with n2 + n + 1 n-tuples, each two of them
forming an exquisite pair. In the following list, ∗ represents any number of zeros as long as the
total number of entries is n.

• (∗)

• (∗, 1, ∗)

• (∗, −1, ∗)

• (∗, 1, ∗, 1, ∗)

• (∗, 1, ∗, −1, ∗)

5
 For example, for n = 2 we have the tuples (0, 0), (0,
0), (0, −1), (−1, 0), (1, 1), (1, −1).

1), (1,
The total number of such tuples is 1 + n + n + n2 + n2 = n2 + n + 1. For any two of them,
at most two of the products ai bi are non-zero. The only case in which two of them are non-zero
is when we take a sequence (∗, 1, ∗, 1, ∗) and a sequence (∗, 1, ∗, −1, ∗) with zero entries in the
same places. But in this case one ai bi is 1 and the other −1. This shows that any two of these
sequences form an exquisite pair.
Next, we claim that among any n2 + n + 2 tuples, some two of them do not form an exquisite
pair. We begin with lemma.
Lemma. Given 2n + 1 distinct non-zero n-tuples of real numbers, some two of them
(a1 , . . . , an ) and (b1 , . . . , bn ) satisfy a1 b1 + · · · + an bn > 0.
Proof of Lemma. We proceed by induction. The statement is easy for n = 1 since for every
three non-zero numbers there are two of them with the same sign. Assume that the statement
is true for n − 1 and consider 2n + 1 tuples with n entries. Since we are working with tuples of
real numbers, we claim that we may assume that one of the tuples is a = (0, 0, . . . , 0, −1). Let
us postpone the proof of this claim for the moment.
If one of the remaining tuples b has a negative last entry, then a and b satisfy the desired
condition. So we may assume all the remaining tuples has a non-negative last entry. Now, from
each tuple remove the last number. If two n-tuples b and c yield the same (n − 1)-tuple, then

b1 c1 + · · · + bn−1 cn−1 + bn cn = b21 + · · · + b2n−1 + bn cn > 0,

and we are done. The remaining case is that all the n-tuples yield distinct (n − 1)-tuples. Then
at most one of them is the zero (n − 1)-tuple, and thus we can use the inductive hypothesis on
2n − 1 of them. So we find b and c for which

(b1 c1 + · · · + bn−1 cn−1 ) + bn cn > 0 + bn cn > 0.

The only thing that we are left to prove is that in the inductive step we may assume that
one of the tuples is a = (0, 0, . . . , 0, −1). Fix one of the tuples x = (x1 , . . . , xn ). Set a real
number ϕ for which tan ϕ = x x1 . Change each tuple a = (a , a , . . . , a ) (including x), to the
2 1 2 n
tuple
(a1 cos ϕ − a2 sin ϕ, a1 sin ϕ + a2 cos ϕ, a3 , a4 , . . . , an ).
A straightforward calculation shows that the first coordinate of the tuple x becomes 0, and
that all the expressions of the form a1 b1 + · · · + an bn are preserved. We may iterate this process
until all the entries of x except for the last one are equal to 0. We finish by multiplying all the
entries in all the tuples by a suitable constant that makes the last entry of x equal to −1. This
preserves the sign of all the expressions of the form a1 b1 + · · · + an bn .

We proceed to the proof of our claim. Let A be a set of non-zero tuples among which any
two form an exquisite pair. It suffices to prove that |A| ≤ n2 + n. We can write A as a disjoint
union of subsets A1 ∪ A2 ∪ . . . ∪ An , where Ai is the set of tuples in A whose last non-zero
entry appears in the ith position. We will show that |Ai | ≤ 2i, which will finish our proof since
2 + 4 + · · · + 2n = n2 + n.
Proceeding by contradiction, suppose that |Ai | ≥ 2i + 1. If Ai has three or more tuples
whose only non-zero entry is in the ith position, then for two of them this entry has the same
sign.
P Since the tuples are different and their entries are integers, this yields two tuples for which
| ai bi | ≥ 2, a contradiction. So there are at most two such tuples. We remove them from Ai .
Now, for each of the remaining tuples a, if it has a positive ith coordinate, we keep a as
it is. If it has a negative ith coordinate, we replace it with the opposite tuple −a with entries
with opposite signs. This does not changes the exquisite pairs condition.

6
 After making the necessary changes, we have two cases. The first case is that there are two
tuples a and b that have the same first i − 1 coordinates and thus

a1 b1 + · · · + ai−1 bi−1 = a21 + · · · + a2i−1 > 0,

and thus is at least 1 (the entries are integers). The second case is that no two tuples have the
same first i − 1 coordinates, but then by the Lemma we find two tuples a and b for which

a1 b1 + · · · + ai−1 bi−1 ≥ 1.

In any case, we obtain

a1 b1 + · · · + ai−1 bi−1 + ai bi ≥ 2.
This yields a final contradiction to the exquisite pair hypothesis.


7
 Solutions of APMO 2018

Problem 1. Let H be the orthocenter of the triangle ABC. Let M and N be the
midpoints of the sides AB and AC, respectively. Assume that H lies inside the quadrilateral
BM N C and that the circumcircles of triangles BM H and CN H are tangent to each other.
The line through H parallel to BC intersects the circumcircles of the triangles BM H and CN H
in the points K and L, respectively. Let F be the intersection point of M K and N L and let J
be the incenter of triangle M HN . Prove that F J = F A.
Solution.
Lemma 1. In a triangle ABC, let D be the intersection of the interior angle bisector at A
with the circumcircle of ABC, and let I be the incenter of 4ABC. Then

DI = DB = DC.

Proof.
∠BAC B
b
∠DBI = + = ∠DIB ⇒ DI = DB.
2 2
Analogously DI = DC.
We start solving the problem. First we state some position considerations. Since there is
an arc of the circumcircle of BHM outside the triangle ABC, it must happen that K and N
lie on opposite sides of AM . Similarly, L and M lie on opposite sides of AN . Also, K and L
lie on the same side of M N , and opposite to A. Therefore, F lies inside the triangle AM N .
Now, since H is the orthocenter of 4ABC and the circumcircles of BM H and CN H are
tangent we have

∠ABH = 90◦ − ∠BAC = ∠ACH ⇒ ∠M HN = ∠M BH + ∠N CH = 180◦ − 2∠BAC. (1)

So ∠M BH = ∠M KH = ∠N CH = ∠N LH = 90◦ − ∠BAC and, since M N kKL, we have

∠F M N = ∠F N M = 90◦ − ∠BAC ⇒ ∠M F N = 2∠BAC. (2)

The relations (1) and (2) yield that the quadrilateral M F N H is cyclic, with the vertices
in this order around the circumference. Since F M = F N , ∠M F N = 2∠BAC and F is the
correct side of M N we have that the point F is the circumcenter of triangle AM N , and thus
F A = F M = F N.

1
 Since the quadrilateral M F N H is cyclic, F M = F N and H lies on the correct side of
M N , we have that H, J and F are collinear. According to Lemma 1, F J = F M = F N . So
F J = F A.

Solution 2: According to Solution 1, we have ∠M HN = 180◦ − 2∠BAC and since the

point J is the incenter of 4M HN , we have ∠M JN = 90◦ + 12 ∠M HN = 180◦ − ∠BAC. So
the quadrilateral AM JN is cyclic.
According to Solution 1, the point F is the circumcenter of 4AM N . So F J = F A.

Problem 2. Let f (x) and g(x) be given by

1 1 1 1
f (x) = + + + ··· +
x x−2 x−4 x − 2018
and
1 1 1 1
g(x) = + + + ··· + .
x−1 x−3 x−5 x − 2017
Prove that
|f (x) − g(x)| > 2
for any non-integer real number x satisfying 0 < x < 2018.
Solution 1 There are two cases: 2n − 1 < x < 2n and 2n < x < 2n + 1. Note that
f (2018 − x) = −f (x) and g(2018 − x) = −g(x), that is, a half turn about the point (1009, 0)
preserves the graphs of f and g. So it suffices to consider only the case 2n − 1 < x < 2n.
Let d(x) = g(x) − f (x). We will show that d(x) > 2 whenever 2n − 1 < x < 2n and
n ∈ {1, 2, . . . , 1009}.
For any non-integer x with 0 < x < 2018, we have
   
1 1 1 1
d(x + 2) − d(x) = − + − > 0 + 0 = 0.
x+1 x+2 x − 2018 x − 2017

Hence it suffices to prove d(x) > 2 for 1 < x < 2. Since x < 2, it follows that x − 2i 1
−1 >
1 for i = 2, 3, . . . , 1008. We also have 1
x − 2i x − 2018 < 0. Hence it suffices to prove the following

2
for 1 < x < 2.
1 1 1 1
+ − − >2
x − 1 x − 3 x x − 2
 
1 1 1 1
⇔ + + − >2
x−1 2−x x−3 x
1 3
⇔ + > 2.
(x − 1)(2 − x) x(x − 3)

By the GM − HM inequality (alternatively, by considering the maximum of the quadratic

(x − 1)(2 − x)) we have
 2
1 1 2
· > = 4.
x−1 2−x (x − 1) + (2 − x)

To find a lower bound for x(x 3− 3) , note that x(x − 3) < 0 for 1 < x < 2. So we seek an upper
bound for x(x − 3). From the shape of the quadratic, this occurs at x = 1 or x = 2, both of
which yield x(x 3− 3) > − 32 .
It follows that d(x) > 4 − 32 > 2, as desired.
Solution 2
As in Solution 1, we may assume 2n − 1 < x < 2n for some 1 ≤ n ≤ 1009. Let d(x) =
f (x) − g(x), and note that
1009
1 X 1
d(x) = +
x m=1 (x − 2m)(x − 2m + 1)

We split the sum into three parts: the terms before m = n, after m = n, and the term m = n.
The first two are
n−1
X 1
0≤
m=1
(x − 2m)(x − 2m + 1)
n−1 n−1 1008
X 1 X 1 X 1 1
≤ = ≤ − ,
m=1
(2n − 1 − 2m)(2n − 2m) i=1
(2i)(2i − 1) i=1
2i − 1 2i

1009
X 1
0≤
m=n+1
(2m − x)(2m − 1 − x)
1009 1009−n 1008
X 1 X 1 X 1 1
≤ = ≤ − .
m=n+1
(2m − 2n + 1)(2m − 2n) i=1
(2i + 1)(2i) i=1
2i 2i + 1

When we add the two sums the terms telescope and we are left with
X 1 1
0≤ ≤1− < 1,
1≤m≤1009,m6=n
(x − 2m)(x − 2m + 1) 2017

For the term m = n, we write

0 < −(x − 2n)(x − 2n + 1) = 0.25 − (x − 2n + 0.5)2 ≤ 0.25,

3
whence
1
−4 ≥ .
(x − 2n)(x − 2n + 1)
Finally, x1 < 1 since x > 2n − 1 ≥ 1. Combining these we get

1009
1 X 1
d(x) = + < 1 + 1 − 4 < −2.
x m=1 (x − 2m)(x − 2m + 1)

Solution 3
First notice that
1 1 1 1 1
f (x) − g(x) = − + − ··· − + .
x x−1 x−2 x − 2017 x − 2018
As in Solution 1, we may deal only with the case 2n < x < 2n + 1. Then x − 2k + 1 and
x − 2k never differ in sign for any integer k. Then
1 1 1
− + = > 0 for k = 1, 2, . . . , n − 1, n + 2, . . . , 1009.
x − 2k + 1 x − 2k (x − 2k + 1)(x − 2k)
 2
1 1 1 2
− = ≥ = 4,
x − 2n x − 2n − 1 (x − 2n)(2n + 1 − x) x − 2n + 2n + 1 − x

Therefore, summing all inequalities and collecting the remaining terms we find f (x)−g(x) >
1 > 4 − 1 = 3 for 0 < x < 1 and, for n > 0,
4+ x− 2

1 1 1
f (x) − g(x) > − +4+
x x − 2n + 1 x − 2n − 2
1 1 1
= − +4−
x x − 2n + 1 2n + 2 − x
1 1 1
> − +4−
x 2n − 2n + 1 2n + 2 − 2n − 1
1
= 2 + > 2.
x

Problem 3. A collection of n squares on the plane is called tri-connected if the following

criteria are satisfied:
(i) All the squares are congruent.

(ii) If two squares have a point P in common, then P is a vertex of each of the squares.

(iii) Each square touches exactly three other squares.

How many positive integers n are there with 2018 ≤ n ≤ 3018, such that there exists a collection
of n squares that is tri-connected?
Answer: 501
Solution. We will prove that there is no tri-connected collection if n is odd, and that
tri-connected collections exist for all even n ≥ 38. Since there are 501 even numbers in the
range from 2018 to 3018, this yields 501 as the answer.

4
 For any two different squares A and B, let us write A ∼ B to mean that square A touches
square B. Since each square touches exactly three other squares, and there are n squares in
total, the total number of instances of A ∼ B is 3n. But A ∼ B if and only if B ∼ A. Hence
the total number of instances of A ∼ B is even. Thus 3n and hence also n is even.
We now construct tri-connected collections for each even n in the range. We show two
Construction 1 The idea is to use the following two configurations. Observe that in each
configuration every square is related to three squares except for the leftmost and rightmost
squares which are related to two squares. Note that the configuration on the left is of variable
length. Also observe that multiple copies of the configuration on the right can be chained
together to end around corners.

Putting the above two types of configurations together as in the following figure yields a
tri-connected collection for every even n ≥ 38.

Construction 2 Consider a regular 4n−gon A1 A2 · · · A4n , and make 4n squares on the

outside of the 4n−gon with one side being on the 4n−gon. Reflect squares sharing sides
A4m+2 A4m+3 , A4m+3 A4m+4 across line A4m+2 A4m+4 , for 0 ≤ m ≤ n − 1. This will produce a
tri-connected set of 6n squares, as long as the squares inside the 4n−gon do not intersect.
When n ≥ 4, this will be true. The picture for n = 24 is as follows:

To treat the other cases, consider the following gadget

5
 Y

Two squares touch 3 other squares, and the squares containing X, Y touch 2 other squares.
Take the 4n−gon from above, and break it into two along the line A1 A2n , moving the two
parts away from that line. Do so until the gaps can be exactly filled by inserting two copies of
the above figure, so that the vertices X, Y touch the two vertices which used to be A1 in one
instance, and the two vertices which used to be A2n in the other.
This gives us a valid configuration for 6n + 8 squares, n ≥ 4. Finally, if we had instead spread
the two parts out more and inserted two copies of the above figure into each gap, we would get
6n + 16 for n ≥ 4, which finishes the proof for all even numbers at least 36.

Problem 4. Let ABC be an equilateral triangle. From the vertex A we draw a ray
towards the interior of the triangle such that the ray reaches one of the sides of the triangle.
When the ray reaches a side, it then bounces off following the law of reflection, that is, if it
arrives with a directed angle α, it leaves with a directed angle 180◦ − α. After n bounces, the
ray returns to A without ever landing on any of the other two vertices. Find all possible values
of n.
Answer: All n ≡ 1, 5 mod 6 with the exception of 5 and 17
Solution. Consider an equilateral triangle AA1 A2 of side length m and triangulate it with
unitary triangles. See the figure. To each of the vertices that remain after the triangulation we
can assign a pair of coordinates (a, b) where a, b are non-negative integers, a is the number of
edges we travel in the AA1 direction and b is the number of edges we travel in the AA2 direction
to arrive to the vertex, (we have A = (0, 0), A1 = (m, 0) and A2 = (0, m)). The unitary triangle
with vertex A will be our triangle ABC, (B = (1, 0), C = (0, 1)). We can obtain every unitary
triangle by starting with ABC and performing reflections with respect to a side (the vertex
(1, 1) is the reflection of A with respect to BC, the vertex (0, 2) is the reflection of B = (1, 0)
with respect to the side formed by C = (1, 0) and (1, 1), and so on).
When we reflect a vertex (a, b) with respect to a side of one of the triangles, the congruence
of a−b is preserved modulo 3. Furthermore, an induction argument shows that any two vertices
(a, b) and (a0 , b0 ) with a − b ≡ a0 − b0 mod 3 can be obtained from each other by a series of such
reflections. Therefore, the set of vertices V that result from the reflections of A will be those
of the form (a, b) satisfying a ≡ b mod 3. See the green vertices in the figure.
Now, let U be the set of vertices u that satisfy that the line segment between u and A
does not pass through any other vertex. A pair (a, b) is in U if and only if gcd(a, b) = 1, since
otherwise for d = gcd(a, b) we have that the vertex (a/d, b/d) also lies on the line segment
between u and A.
Observe that the rays that come out from A and eventually return to A are those that come
out towards a vertex in V ∩ U (they would be in V to be able to come back to A and in U
so that they do not reach a vertex beforehand). In the diagram, a ray toward one such vertex
(a, b) will intersect exactly (a − 1) + (b − 1) + (a + b − 1) = 2(a + b) − 3 lines: a − 1 of them
parallel to AB, b − 1 parallel to AC and a + b − 1 parallel to BC. Therefore, in the triangle
ABC the ray will bounce 2(a + b) − 3 times before returning to A. So we want to find all

6
n = 2(a + b) − 3 where a ≡ b mod 3 and gcd(a, b) = 1.
If a + b is a multiple of 3 then we cannot satisfy both conditions simultaneously, therefore n
is not a multiple of 3. We also know that n is odd. Therefore n ≡ 1, 5, 7, 11 mod 12. Note that
the pair (1, 3k + 1) satisfies the conditions and we can create n = 2(3k + 2) − 3 = 6k + 1 for
all k ≥ 0 (this settles the question for n ≡ 1, 7 mod 12). For n ≡ 5 mod 12 consider the pair
(3k − 1, 3k + 5) when k is even or (3k − 4, 3k + 8) when k is odd. This gives us all the integers
of the form 12k + 5 for k ≥ 2. For 11 mod 12, take the pairs (3k − 1, 3k + 2) (with k ≥ 1),
which yield all positive integers of the form 12k − 1.
Finally, to discard 5 and 17 note that the only pairs (a, b) that are solutions to 2(a+b)−3 = 5
or 2(a + b) − 3 = 17 with the same residue mod 3 in this range are the non-relatively prime
pairs (2, 2), (2, 8) and (5, 5).

Problem 5. Find all polynomials P (x) with integer coefficients such that for all real
numbers s and t, if P (s) and P (t) are both integers, then P (st) is also an integer.
Answer: P (x) = xn + k, −xn + k for n a non-negative integer and k an integer.
Solution 1: P (x) = xn + k, −xn + k for n a non-negative integer and k an integer.
Notice that if P (x) is a solution, then so is P (x) + k and −P (x) + k for any integer k, so
we may assume that P the leading coefficient of P (x) is positive and that P (0) = 0, i.e., we can
assume that P (x) = ni=1 ai xi with an >P 0. We are going to prove that P (x) = xn in this case.
Let p be a large prime such that p > ni=1 |ai |. Because P has a positive leading coefficient
and p is large enough, we can find t ∈ R such that P (t) = p. Denote the greatest common
divisor of the polynomial P (x) − p and P (2x) − P (2t) as f (x), and t is a root of it, so f is a
non-constant polynomial. Notice that P (2t) is an integer by using the hypothesis for s = 2 and
t. Since P (x) − p and P (2x) − P (2t) are polynomials with integer coefficients, f can be chosen
as a polynomial with rational coefficients.
In the following, we will prove that f is the same as P (x) − p up to a constant multiplier.
Say P (x) − p = f (x)g(x), where f and g are non-constant polynomials. By Gauss’s lemma, we
can get f1 , g1 with P (x) − p = f1 (x)g1 (x) where f1 is a scalar multiple of f and g1 is a scalar
multiple of g and one of f1 , g1 has constant term ±1 (this is because −p = P (0) − p = f (0)g(0)
with p prime). So P (x) − p has at least one root r with absolute value not greater than 1 (using

7
Vieta, the product of the roots of the polynomial with constant term ±1 is ±1), but
n
X n
X
i
|P (r) − p| = ai r − p > p − |ai | > 0,
i=1 i=1

hence we get a contradiction!

Therefore f is a constant multiple of P (x) − p, so P (2x) − P (2t) is a constant multiple
of P (x) − p because they both have the same degree. By comparing leading coefficients we
get that P (2x) − P (2t) = 2n (P (x) − p). Comparing the rest of the coefficients we get that
P (x) = an xn . If we let a = b = (1/an )1/n , then P (a) = P (b) = 1, so P (ab) must also be an
integer. But P (ab) = a1n . Therefore an = 1 and the proof is complete.
Pn
Solution 2: Assume P (x) = i=0 ai xi . Consider the following system of equations

a0 = P (0)
n n−1
an t + an−1 t + · · · + a0 = P (t)
n n n−1 n−1
2 an t + 2 an−1 t + · · · + a0 = P (2t)
..
.
n n n−1 n−1
n an t + n an−1 t + · · · + a0 = P (nt).

viewing ak tk as variables. Note that if P (t) is an integer, then by the hypothesis all the terms
on the right hand side of the equations are integers as well. By using Cramer’s rule, we can get
that ak tk = D/M , where D is an integer and M is the following determinant

1 0 0 ··· 0
1 1 1 ··· 1
1 2 4 ··· 2n 6= 0.
.. .. .. ..
. . . .
1 n n2 · · · nn
Thus, if we let r be the smallest positive index such that ar 6= 0, we can express each t ∈ R
with P (t) ∈ Z in the form ( m0 )1/r for some integer m, and where M 0 = M × ar is a constant.
M
We can choose L large enough such that P |R≥L is injective, and for any larger N , the growth
order of the number of values in the form ( m0 )1/r is N r , while the growth order of the number
M
of integers in [P (L), P (N )] is N n , so r = n. Therefore P (x) is of the form an xn + k. The
problem can be finished as in Solution 1.

8
 Solutions of APMO 2019

Problem 1. Let Z+ be the set of positive integers. Determine all functions f : Z+ → Z+

such that a2 + f (a)f (b) is divisible by f (a) + b for all positive integers a and b.
Answer: The answer is f (n) = n for all positive integers n.
Clearly, f (n) = n for all n ∈ Z+ satisfies the original relation. We show some possible
approaches to prove that this is the only possible function.
Solution. First we perform the following substitutions on the original relation:

1. With a = b = 1, we find that f (1) + 1 | f (1)2 + 1, which implies f (1) = 1.

2. With a = 1, we find that b + 1 | f (b) + 1. In particular, b ≤ f (b) for all b ∈ Z+ .
3. With b = 1, we find that f (a) + 1 | a2 + f (a), and thus f (a) + 1 | a2 − 1. In particular,
f (a) ≤ a2 − 2 for all a ≥ 2.

Now, let p be any odd prime. Substituting a = p and b = f (p) in the original relation, we
find that 2f (p)|p2 + f (p)f (f (p)). Therefore, f (p)|p2 . Hence the possible values of f (p) are 1, p
and p2 . By (2) above, f (p) ≥ p and by (3) above f (p) ≤ p2 − 2. So f (p) = p for all primes p.
Substituting a = p into the original relation, we find that b + p | p2 + pf (b). However, since
(b + p)(f (b) + p − b) = p2 − b2 + bf (b) + pf (b), we have b + p | bf (b) − b2 . Thus, for any fixed b
this holds for arbitrarily large primes p and therefore we must have bf (b) − b2 = 0, or f (b) = b,
as desired.

Solution 2: As above, we have relations (1)-(3). In (2) and (3), for b = 2 we have 3|f (2)+1
and f (2) + 1|3. These imply f (2) = 2.
Now, using a = 2 we get 2 + b|4 + 2f (b). Let f (b) = x. We have

1+x≡0 (mod b + 1)
4 + 2x ≡ 0 (mod b + 2).

From the first equation x ≡ b (mod b + 1) so x = b + (b + 1)t for some integer t ≥ 0. Then

0 ≡ 4 + 2x ≡ 4 + 2(b + (b + 1)t) ≡ 4 + 2(−2 − t) ≡ −2t (mod b + 2).

Also t ≤ b − 2 because 1 + x|b2 − 1 by (3).

If b + 2 is odd, then t ≡ 0 (mod b + 2). Then t = 0, which implies f (b) = b.
If b + 2 is even, then t ≡ 0 (mod (b + 2)/2). Then t = 0 or t = (b + 2)/2. But if t 6= 0,
then by definition (b + 4)/2 = (1 + t) = (x + 1)/(b + 1) and since x + 1|b2 − 1, then (b + 4)/2
divides b − 1. Therefore b + 4|10 and the only possibility is b = 6. So for even b, b 6= 6 we have
f (b) = b.
Finally, by (2) and (3), for b = 6 we have 7|f (6) + 1 and f (6) + 1|35. This means f (6) = 6
or f (6) = 34. The later is discarded as, for a = 5, b = 6, we have by the original equation that
11|5(5 + f (6)). Therefore f (n) = n for every positive integer n.

Solution 3: We proceed by induction. As in Solution 1, we have f (1) = 1. Suppose that

f (n − 1) = n − 1 for some integer n ≥ 2.
With the substitution a = n and b = n − 1 in the original relation we obtain that f (n) +
n − 1|n2 + f (n)(n − 1). Since f (n) + n − 1|(n − 1)(f (n) + n − 1), then f (n) + n − 1|2n − 1.
With the substitution a = n − 1 and b = n in the original relation we obtain that 2n −
1|(n − 1)2 + (n − 1)f (n) = (n − 1)(n − 1 + f (n)). Since (2n − 1, n − 1) = 1, we deduce that
2n − 1|f (n) + n − 1.

1
 Therefore, f (n) + n − 1 = 2n − 1, which implies the desired f (n) = n.

Problem 2. Let m be a fixed positive integer. The infinite sequence {an }n≥1 is defined in
the following way: a1 is a positive integer, and for every integer n ≥ 1 we have
(
a2n + 2m if an < 2m
an+1 =
an /2 if an ≥ 2m .

For each m, determine all possible values of a1 such that every term in the sequence is an
integer.
Answer: The only value of m for which valid values of a1 exist is m = 2. In that case, the
only solutions are a1 = 2` for ` ≥ 1.
Solution. Suppose that for integers m and a1 all the terms of the sequence are integers.
For each i ≥ 1, write the ith term of the sequence as ai = bi 2ci where bi is the largest odd
divisor of ai (the “odd part” of ai ) and ci is a nonnegative integer.
Lemma 1. The sequence b1 , b2 , . . . is bounded above by 2m .
Proof. Suppose this is not the case and take an index i for which bi > 2m and for which ci is
minimal. Since ai ≥ bi > 2m , we are in the second case of the recursion. Therefore, ai+1 = ai /2
and thus bi+1 = bi > 2m and ci+1 = ci − 1 < ci . This contradicts the minimality of ci .
Lemma 2. The sequence b1 , b2 , . . . is nondecreasing.
Proof. If ai ≥ 2m , then ai+1 = ai /2 and thus bi+1 = bi . On the other hand, if ai < 2m , then

ai+1 = a2i + 2m = b2i 22ci + 2m ,

and we have the following cases:

• If 2ci > m, then ai+1 = 2m (b2i 22ci −m + 1), so bi+1 = b2i 22ci −m + 1 > bi .

• If 2ci < m, then ai+1 = 22ci (b2i + 2m−2ci ), so bi+1 = b2i + 2m−2ci > bi .
b2i +1
• If 2ci = m, then ai+1 = 2m+1 · 2
, so bi+1 = (b2i + 1)/2 ≥ bi since b2i + 1 ≡ 2 (mod 4).

By combining these two lemmas we obtain that the sequence b1 , b2 , . . . is eventually constant.
Fix an index j such that bk = bj for all k ≥ j. Since an descends to an /2 whenever an ≥ 2m ,
there are infinitely many terms which are smaller than 2m . Thus, we can choose an i > j such
that ai < 2m . From the proof of Lemma 2, ai < 2m and bi+1 = bi can happen simultaneously
only when 2ci = m and bi+1 = bi = 1. By Lemma 2, the sequence b1 , b2 , . . . is constantly 1 and
thus a1 , a2 , . . . are all powers of two. Tracing the sequence starting from ai = 2ci = 2m/2 < 2m ,

2m/2 → 2m+1 → 2m → 2m−1 → 22m−2 + 2m .

Note that this last term is a power of two if and only if 2m − 2 = m. This implies that m
must be equal to 2. When m = 2 and a1 = 2` for ` ≥ 1 the sequence eventually cycles through
2, 8, 4, 2, . . .. When m = 2 and a1 = 1 the sequence fails as the first terms are 1, 5, 5/2.

Solution 2: Let m be a positive integer and suppose that {an } consists only of positive
integers. Call a number small if it is smaller than 2m and large otherwise. By the recursion,

2
after a small number we have a large one and after a large one we successively divide by 2 until
we get a small one.
First, we note that {an } is bounded. Indeed, a1 turns into a small number after a finite
number of steps. After this point, each small number is smaller than 2m , so each large number
is smaller than 22m + 2m . Now, since {an } is bounded and consists only of positive integers, it
is eventually periodic. We focus only on the cycle.
Any small number an in the cycle can be writen as a/2 for a large, so an ≥ 2m−1 , then
an+1 ≥ 22m−2 + 2m = 2m−2 (4 + 2m ), so we have to divide an+1 at least m − 1 times by 2 until
we get a small number. This means that an+m = (a2n + 2m )/2m−1 , so 2m−1 |a2n , and therefore
2d(m−1)/2e | an for any small number an in the cycle. On the other hand, an ≤ 2m − 1, so
an+1 ≤ 22m − 2m+1 + 1 + 2m ≤ 2m (2m − 1), so we have to divide an+1 at most m times by
two until we get a small number. This means that after an , the next small number is either
N = am+n = (a2n /2m−1 ) + 2 or am+n+1 = N/2. In any case, 2d(m−1)/2e divides N .
If m is odd, then x2 ≡ −2 (mod 2d(m−1)/2e ) has a solution x = an /2(m−1)/2 . If (m − 1)/2 ≥
2 ⇐⇒ m ≥ 5 then x2 ≡ −2 (mod 4), which has no solution. So if m is odd, then m ≤ 3.
If m is even, then 2m−1 | a2n =⇒ 2d(m−1)/2e | an ⇐⇒ 2m/2 | an . Then if an = 2m/2 x,
2x ≡ −2 (mod 2m/2 ) ⇐⇒ x2 ≡ −1 (mod 2(m/2)−1 ), which is not possible for m ≥ 6. So if m
2

is even, then m ≤ 4.
The cases m = 1, 2, 3, 4 are handed manually, checking the possible small numbers in the
cycle, which have to be in the interval [2m−1 , 2m ) and be divisible by 2d(m−1)/2e :

• For m = 1, the only small number is 1, which leads to 5, then 5/2.

• For m = 2, the only eligible small number is 2, which gives the cycle (2, 8, 4). The only
way to get to 2 is by dividing 4 by 2, so the starting numbers greater than 2 are all
numbers that lead to 4, which are the powers of 2.

• For m = 3, the eligible small numbers are 4 and 6; we then obtain 4, 24, 12, 6, 44, 22, 11, 11/2.

• For m = 4, the eligible small numbers are 8 and 12; we then obtain 8, 80, 40, 20, 10, . . . or
12, 160, 80, 40, 20, 10, . . ., but in either case 10 is not an elegible small number.

Problem 3. Let ABC

be a scalene triangle with circumcircle Γ. Let M be the midpoint of BC. A variable point P
is selected in the line segment AM . The circumcircles of triangles BP M and CP M intersect
Γ again at points D and E, respectively. The lines DP and EP intersect (a second time) the
circumcircles to triangles CP M and BP M at X and Y , respectively. Prove that as P varies,
the circumcircle of 4AXY passes through a fixed point T distinct from A.
Solution. Let N be the radical center of the circumcircles of triangles ABC, BM P and
CM P . The pairwise radical axes of these circles are BD, CE and P M , and hence they concur
at N . Now, note that in directed angles:

∠M CE = ∠M P E = ∠M P Y = ∠M BY.

3
 It follows that BY is parallel to CE, and analogously that CX is parallel to BD. Then, if L
is the intersection of BY and CX, it follows that BN CL is a parallelogram. Since BM = M C
we deduce that L is the reflection of N with respect to M , and therefore L ∈ AM . Using power
of a point from L to the circumcircles of triangles BP M and CP M , we have

LY · LB = LP · LM = LX · LC.
Hence, BY XC is cyclic. Using the cyclic quadrilateral we find in directed angles:

∠LXY = ∠LBC = ∠BCN = ∠N DE.

Since CX k BN , it follows that XY k DE.
Let Q and R be two points in Γ such that CQ, BR, and AM are all parallel. Then in
directed angles:

∠QDB = ∠QCB = ∠AM B = ∠P M B = ∠P DB.

Then D, P, Q are collinear. Analogously E, P, R are collinear. From here we get ∠P RQ =
∠P DE = ∠P XY , since XY and DE are parallel. Therefore QRY X is cyclic. Let S be the
radical center of the circumcircle of triangle ABC and the circles BCY X and QRY X. This
point lies in the lines BC, QR and XY because these are the radical axes of the circles. Let
T be the second intersection of AS with Γ. By power of a point from S to the circumcircle of
ABC and the circle BCXY we have

SX · SY = SB · SC = ST · SA.

4
 Therefore T is in the circumcircle of triangle AXY . Since Q and R are fixed regardless of
the choice of P , then S is also fixed, since it is the intersection of QR and BC. This implies
T is also fixed, and therefore, the circumcircle of triangle AXY goes through T 6= A for any
choice of P .

Now we show an alternative way to prove that BCXY and QRXT are cyclic.
Solution 2. Let the lines DP and EP meet the circumcircle of ABC again at Q and R,
respectively. Then ∠DQC∠DBC = ∠DP M , so QC k P M . Similarly, RB k P M .

Now, ∠QCB = ∠P M B = ∠P XC = ∠(QX, CX), which is half of the arc QC in the

circumcircle ωC of QXC. So ωC is tangent to BS; analogously, ωB , the circumcicle of RY B,
is also tangent to BC. Since BR k CQ, the inscribed trapezoid BRQC is isosceles, and by
symmetry QR is also tangent to both circles, and the common perpendicular bisector of BR
and CQ passes through the centers of ωB and ωC . Since M B = M C and P M k BR k CQ, the
line P M is the radical axis of ωB and ωC .
However, P M is also the radical axis of the circumcircles γB of P M B and γC of P M C.
Let CX and P M meet at Z. Let p(K, ω) denote the power of a point K with respect to a
circumference ω. We have

p(Z, γB ) = p(Z, γC ) = ZX · ZC = p(Z, ωB ) = p(Z, ωC ).

Point Z is thus the radical center of γB , γC , ωB , ωC . Thus, the radical axes BY, CX, P M meet
at Z. From here,

ZY · ZB = ZC · ZX ⇒ BCXY cyclic
P Y · P R = P X · P Q ⇒ QRXT cyclic.

We may now finish as in Solution 1.

Problem 4. Consider a 2018 × 2019 board with integers in each unit square. Two unit
squares are said to be neighbours if they share a common edge. In each turn, you choose some
unit squares. Then for each chosen unit square the average of all its neighbours is calculated.
Finally, after these calculations are done, the number in each chosen unit square is replaced by
the corresponding average. Is it always possible to make the numbers in all squares become
the same after finitely many turns?
Answer: No

5
 Solution. Let n be a positive integer relatively prime to 2 and 3. We may study the whole
process modulo n by replacing divisions by 2, 3, 4 with multiplications by the corresponding
inverses modulo n. If at some point the original process makes all the numbers equal, then the
process modulo n will also have all the numbers equal. Our aim is to choose n and an initial
configuration modulo n for which no process modulo n reaches a board with all numbers equal
modulo n. We split this goal into two lemmas.
Lemma 1. There is a 2 × 3 board that stays constant modulo 5 and whose entries are not
all equal.
Proof. Here is one such a board:

The fact that the board remains constant regardless of the choice of squares can be checked
square by square.

Lemma 2. If there is an r × s board with r ≥ 2, s ≥ 2, that stays constant modulo 5, then

there is also a kr × ls board with the same property.
Proof. We prove by a case by case analysis that repeateadly reflecting the r × s with respect
to an edge preserves the property:
• If a cell had 4 neighbors, after reflections it still has the same neighbors.
• If a cell with a had 3 neighbors b, c, d, we have by hypothesis that a ≡ 3−1 (b + c + d) ≡
2(b + c + d) (mod 5). A reflection may add a as a neighbor of the cell and now
4−1 (a + b + c + d) ≡ 4(a + b + c + d) ≡ 4a + 2a ≡ a (mod 5)

• If a cell with a had 2 neighbors b, c, we have by hypothesis that a ≡ 2−1 (b + c) ≡ 3(b + c)

(mod 5). If the reflections add one a as neighbor, now
3−1 (a + b + c) ≡ 2(3(b + c) + b + c) ≡ 8(b + c) ≡ 3(b + c) ≡ a (mod 5)

• If a cell with a had 2 neighbors b, c, we have by hypothesis that a ≡ 2−1 (b + c) (mod 5).
If the reflections add two a’s as neighbors, now
4−1 (2a + b + c) ≡ (2−1 a + 2−1 a) ≡ a (mod 5)

In the three cases, any cell is still preserved modulo 5 after an operation. Hence we can fill
in the kr × ls board by k × l copies by reflection.
Since 2|2018 and 3|2019, we can get through reflections the following board:

6
By the lemmas above, the board is invariant modulo 5, so the answer is no.

Problem 5. Determine all the functions f : R → R such that

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

for all real number x and y.

Answer: The possible functions are f (x) = 0 for all x and f (x) = x2 for all x.
Solution. By substituting x = y = 0 in the given equation of the problem, we obtain that
f (0) = 0. Also, by substituting y = 0, we get f (x2 ) = f (f (x)) for any x.
Furthermore, by letting y = 1 and simplifying, we get

2f (x) = f (x2 + f (1)) − f (x2 ) − f (1),

from which it follows that f (−x) = f (x) must hold for every x.
Suppose now that f (a) = f (b) holds for some pair of numbers a, b. Then, by letting y = a
and y = b in the given equation, comparing the two resulting identities and using the fact that
f (a2 ) = f (f (a)) = f (f (b)) = f (b2 ) also holds under the assumption, we get the fact that

f (a) = f (b) ⇒ f (ax) = f (bx) for any real number x. (1)

Consequently, if for some a 6= 0, f (a) = 0, then we see that, for any x, f (x) = f (a · xa ) =
f (0 · xa ) = f (0) = 0, which gives a trivial solution to the problem.
In the sequel, we shall try to find a non-trivial solution for the problem. So, let us assume
from now on that if a 6= 0 then f (a) 6= 0 must hold. We first note that since f (f (x)) = f (x2 )
for all x, the right-hand side of the given equation equals f (x2 ) + f (y 2 ) + 2f (xy), which is
invariant if we interchange x and y. Therefore, we have

f (x2 ) + f (y 2 ) + 2f (xy) = f (x2 + f (y)) = f (y 2 + f (x)) for every pair x, y. (2)

Next, let us show that for any x, f (x) ≥ 0 must hold. Suppose, on the contrary, f (s) = −t2
holds for some pair s, t of non-zero real numbers. By setting x = s, y = t in the right hand
side of (2), we get f (s2 + f (t)) = f (t2 + f (s)) = f (0) = 0,√ so f (t) = −s2 . We also have
f (t2 ) = f (−t2 ) = f (f (s)) = f (s2 ). By applying (2) with x = s2 + t2 and y = s, we obtain
√
f (s2 + t2 ) + 2f (s · s2 + t2 ) = 0,
√
and similarly, by applying (2) with x = s2 + t2 and y = t, we obtain
√
f (s2 + t2 ) + 2f (t · s2 + t2 ) = 0.

Consequently, we obtain √ √
f (s · s2 + t2 ) = f (t · s2 + t2 ).
√ √ √
By applying (1) with a = s s2 + t2 , b = t s2 + t2 and x = 1/ s2 + t2 , we obtain f (s) =
f (t) = −s2 , from which it follows that

0 = f (s2 + f (s)) = f (s2 ) + f (s2 ) + 2f (s2 ) = 4f (s2 ),

a contradiction to the fact s2 > 0. Thus we conclude that for all x 6= 0, f (x) > 0 must be
satisfied.
Now, we show the following fact

k > 0, f (k) = 1 ⇔ k = 1. (3)

7
 Let k > 0 for which f (k) = 1. We have f (k 2 ) = f (f√ (k)) = f (1), so by (1), f (1/k) = f (k) =
1, so we may assume k ≥ 1. By applying (2) with x = k 2 − 1 and y = k, and using f (x) ≥ 0,
we get
√
f (k 2 − 1 + f (k)) = f (k 2 − 1) + f (k 2 ) + 2f (k k 2 − 1) ≥ f (k 2 − 1) + f (k 2 ).

This simplifies to 0 ≥ f (k 2 − 1) ≥ 0, so k 2 − 1 = 0 and thus k = 1.

Next we focus√ on showing f (1) = 1. If f (1) = m ≤ 1, then we may proceed as above
by setting x = 1 − m and y = 1 to get m = 1. If f (1) = m ≥ 1, now we √ note that
2 2
f (m) = f (f (1)) = f (1 ) = f (1) = m ≤ m . We may then proceed as above with x = m2 − m
and y = 1 to show m2 = m and thus m = 1.
We are now ready to finish. Let x > 0 and m = f (x). Since f (f (x)) = f (x2 ), then f (x2 ) =
f (m). But by (1), f (m/x2 ) = 1. Therefore m = x2 . For x < 0, we have f (x) = f (−x) = f (x2 )
as well. Therefore, for all x, f (x) = x2 .

Solution 2 After proving that f (x) > 0 for x 6= 0 as in the previous solution, we may also
proceed as follows. We claim that f is injective on the positive real numbers. Suppose that
a > b > 0 satisfy f (a) = f (b). Then by setting x = 1/b in (1) we have f (a/b) = f (1). Now,
by induction on n and iteratively setting x = a/b in (1) we get f ((a/b)n ) = 1 for any positive
integer n.
n
p Now, let m = f (1) and n be a positive integer such that (a/b) > m. By setting x =
n
(a/b) − m and y = 1 in (2) we obtain that
p
f ((a/b)n − m + f (1)) = f ((a/b)n − m) + f (12 ) + 2f ( (a/b)n − m)) ≥ f ((a/b)n − m) + f (1).

Since f ((a/b)n ) = f (1), this last equation simplifies to f ((a/b)n − m) ≤ 0 and thus m =
(a/b)n . But this is impossible since m is constant and a/b > 1. Thus, f is injective on the
positive real numbers. Since f (f (x)) = f (x2 ), we obtain that f (x) = x2 for any real value x.

8
 APMO 2020 Solution

1. Let Γ be the circumcircle of ∆ABC. Let D be a point on the side BC. The tangent to Γ at A intersects
the parallel line to BA through D at point E. The segment CE intersects Γ again at F . Suppose
B, D, F, E are concyclic. Prove that AC, BF, DE are concurrent.
Solution 1 From the conditions, we have

∠CBA = 180◦ − ∠EDB = 180◦ − ∠EF B

= 180◦ − ∠EF A − ∠AF B
= 180◦ − ∠CBA − ∠ACB = ∠BAC.

Let P be the intersection of AC and BF . Then we have

∠P AE = ∠CBA = ∠BAC = ∠BF C.

This implies A, P, F, E are concyclic. It follows that

∠F P E = ∠F AE = ∠F BA,

and hence AB and EP are parallel. So E, P, D are collinear, and the result follows.
Solution 2
Let E 0 be any point on the extension of EA. From ∠AED = ∠E 0 AB = ∠ACD, points A, D, C, E are
concyclic.

1
 Let P be the intersection of BF and DE. From ∠AF P = ∠ACB = ∠AEP , the points A, P, F, E are
concyclic. In addition, from ∠EP A = ∠EF A = ∠DBA, points A, B, D, P are concyclic.
By considering the radical centre of (BDF E), (AP F E) and (BDP A), we find that the lines BD, AP, EF
are concurrent at C. The result follows.

2. Show that r = 2 is the largest real number r which satisfies the following condition:
If a sequence a1 , a2 , . . . of positive integers fulfills the inequalities
p
an ≤ an+2 ≤ a2n + ran+1

for every positive integer n, then there exists a positive integer M such that an+2 = an for every n ≥ M .

Solution 1. First, let us assume that r > 2, and take a positive integer a ≥ 1/(r − 2).
Then, if we let an = a + bn/2c for n = 1, 2, . . ., the sequence an satisfies the inequalities
s  
p
2
p
2 2
1
an + ran+1 ≥ an + ran ≥ an + 2 + an ≥ an + 1 = an+2 ,
a

but since an+2 > an for any n, we see that r does not satisfy the condition given in the problem.
Now we show that r = 2 does satisfy the condition of the problem. Suppose a1 , a2 , . . . is a sequence of
positive integers satisfying the inequalities given in the problem, and there exists a positive integer m
for which am+2 > am is satisfied.
By induction we prove the following assertion:
(†) am+2k ≤ am+2k−1 = am+1 holds for every positive integer k.
The truth of (†) for k = 1 follows from the inequalities below

2am+2 − 1 = a2m+2 − (am+2 − 1)2 ≤ a2m + 2am+1 − (am+2 − 1)2 ≤ 2am+1 .

Let us assume that (†) holds for some positive integer k. From

a2m+1 ≤ a2m+2k+1 ≤ a2m+2k−1 + 2am+2k ≤ a2m+1 + 2am+1 < (am+1 + 1)2 ,

it follows that am+2k+1 = am+1 must hold. Furthermore, since am+2k ≤ am+1 , we have

a2m+2k+2 ≤ a2m+2k + 2am+2k+1 ≤ a2m+1 + 2am+1 < (am+1 + 1)2 ,

2
 from which it follows that am+2k+2 ≤ am+1 , which proves the assertion (†).
We can conclude that for the value of m with which we started our argument above, am+2k+1 = am+1
holds for every positive integer k. Therefore, in order to finish the proof, it is enough to show that
am+2k becomes constant after some value of k. Since every am+2k is a positive integer less than or
equal to am+1 , there exists k = K for which am+2K takes the maximum value. By the monotonicity
of am+2k , it then follows that am+2k = am+2K for all k ≥ K.
Solution 2
We only give an alternative proof of the assertion (†) in solution 1. Let {an } be a sequence satisfying
the inequalities given in the problem. We will use the following key observations:
(a) If an+1 ≤ an for some n ≥ 1, then
p p
an ≤ an+2 ≤ a2n + 2an+1 < a2n + 2an + 1 = an + 1,

hence an = an+2 .
(b) If an ≤ an+1 for some n ≥ 1, then
p q
an ≤ an+2 ≤ a2n + 2an+1 < a2n+1 + 2an+1 + 1 = an+1 + 1,

hence an ≤ an+2 ≤ an+1 .

Now let m be a positive integer such that am+2 > am . By the observations above, we must have
am < am+2 ≤ am+1 . Thus the assertion (†) is true for k = 1. Assume that the assertion holds for some
positive integer k. Using observation (a), we get am+2k+1 = am+2k−1 = am+1 . Thus am+2k ≤ am+2k+1 ,
and then using observation (b), we get am+2k+2 ≤ am+2k+1 = am+1 , which proves the assertion (†).
3. Determine all positive integers k for which there exist a positive integer m and a set S of positive
integers such that any integer n > m can be written as a sum of distinct elements of S in exactly k
ways.
Solution:
We claim that k = 2a for all a ≥ 0.
Let A = {1, 2, 4, 8, . . . } and B = N\A. For any set T , let s(T ) denote the sum of the elements of T .
(If T is empty, we let s(T ) = 0.)
We first show that any positive integer k = 2a satisfies the desired property. Let B 0 be a subset of
B with a elements, and let S = A ∪ B 0 . Recall that any nonnegative integer has a unique binary
representation. Hence, for any integer t > s(B 0 ) and any subset B 00 ⊆ B 0 , the number t − s(B 00 ) can
be written as a sum of distinct elements of A in a unique way. This means that t can be written as a
sum of distinct elements of B 0 in exactly 2a ways.
Next, assume that some positive integer k satisfies the desired property for a positive integer m ≥ 2
and a set S. Clearly, S is infinite.
Lemma: For all sufficiently large x ∈ S, the smallest element of S larger than x is 2x.
Proof of Lemma: Let x ∈ S with x > 3m, and let x < y < 2x. We will show that y 6∈ S. Suppose
first that y > x + m. Then y − x can be written as a sum of distinct elements of S not including x in
k ways. If y ∈ S, then y can be written as a sum of distinct elements of S in at least k + 1 ways, a
contradiction. Suppose now that y ≤ x + m. We consider z ∈ (2x − m, 2x). Similarly as before, z − x
can be written as a sum of distinct elements of S not including x or y in k ways. If y ∈ S, then since
m < z − y < x, z − y can be written as a sum of distinct elements of S not including x or y. This
means that z can be written as a sum of distinct elements of S in at least k + 1 ways, a contradiction.
We now show that 2x ∈ S; assume for contradiction that this is not the case. Observe that 2x can be
written as a sum of distinct elements of S including x in exactly k − 1 ways. This means that 2x can
also be written as a sum of distinct elements of S not including x. If this sum includes any number
less than x − m, then removing this number, we can write some number y ∈ (x + m, 2x) as a sum of
distinct elements of S not including x. Now if y = y 0 + x where y 0 ∈ (m, x) then y 0 can be written as

3
 a sum of distinct elements of S including x in exactly k ways. Therefore y can be written as a sum of
distinct elements of S in at least k + 1 ways, a contradiction. Hence the sum only includes numbers
in the range [x − m, x). Clearly two numbers do not suffice. On the other hand, three such numbers
sum to at least 3(x − m) > 2x, a contradiction. 
From the Lemma, we have that S = T ∪ U , where T is finite and U = {x, 2x, 4x, 8x, . . . } for some
positive integer x. Let y be any positive integer greater than s(T ). For any subset T 0 ⊆ T , if
y − s(T 0 ) ≡ 0 (mod x), then y − s(T 0 ) can be written as a sum of distinct elements of U in a unique
way; otherwise y − s(T 0 ) cannot be written as a sum of distinct elements of U . Hence the number of
ways to write y as a sum of distinct elements of S is equal to the number of subsets T 0 ⊆ T such that
s(T 0 ) ≡ y (mod x). Since this holds for all y, for any 0 ≤ a ≤ x − 1 there are exactly k subsets T 0 ⊆ T
such that s(T 0 ) ≡ a (mod x). This means that there are kx subsets of T in total. But the number of
subsets of T is a power of 2, and therefore k is a power of 2, as claimed.
Solution 2. We give an alternative proof of the first half of the lemma in the Solution 1 above.
Qr
Let s1 < s2 < · · · be the elements of S. For any positive integer r, define Ar (x) = n=1 (1 + xsn ).
For each n such that m ≤ n < sr+1 , all k ways of writing n as a sum of elements of S must only use
s1 , . . . , sr , so the coefficient of xn in Ar (x) is k. Similarly the number of ways of writing sr+1 as a sum
of elements of S without using sr+1 is exactly k − 1. Hence the coefficient of xsr+1 in Ar (x) is k − 1.
Fix a t such that st > 2(m + 1). Write

At−1 (x) = u(x) + k xm+1 + · · · + xst −1 + xst v(x)

for some u(x), v(x) where u(x) is of degree at most m.

Note that
At+1 (x) = At−1 (x) + xst At−1 (x) + xst+1 At−1 (x) + xst +st+1 At−1 (x).

If st+1 + m + 1 < 2st , we can find the term xst+1 +m+1 in xst At−1 (x) and in xst+1 At−1 (x). Hence the
coefficient of xst+1 +m+1 in At+1 (x) is at least 2k, which is impossible. So st+1 ≥ 2st − (m + 1) >
st + m + 1.
Now
At (x) = At−1 (x) + xst u(x) + k(xst +m+1 + · · · x2st −1 ) + x2st v(x).

Recall that the coefficent of xst+1 in At (x) is k − 1. But if st + m + 1 < st+1 < s2t , then the coefficient
of xst+1 in At (x) is at least k, which is a contradiction. Therefore st+1 ≥ 2st .
4. Let Z denote the set of all integers. Find all polynomials P (x) with integer coefficients that satisfy the
following property:
For any infinite sequence a1 , a2 , . . . of integers in which each integer in Z appears exactly once, there
exist indices i < j and an integer k such that ai + ai+1 + · · · + aj = P (k).
Solution:
Part 1: All polynomials with deg P = 1 satisfy the given property.
Suppose P (x) = cx + d, and assume without loss of generality that c > d ≥ 0. Denote si = a1 + a2 +
· · · + ai (mod c). It suffices to show that there exist indices i and j such that j − i ≥ 2 and sj − si ≡ d
(mod c).
Consider c + 1 indices e1 , e2 , . . . , ec+1 > 1 such that ael ≡ d (mod c). By the pigeonhole principle,
among the n + 1 pairs (se1 −1 , se1 ), (se2 −1 , se2 ), . . . , (sen+1 −1 , sen+1 ), some two are equal, say (sm−1 , sm )
and (sn−1 , sn ). We can then take i = m − 1 and j = n.
Part 2: All polynomials with deg P 6= 1 do not satisfy the given property.
Lemma: If deg P 6= 1, then for any positive integers A, B, and C, there exists an integer y with |y| > C
such that no value in the range of P falls within the interval [y − A, y + B].
Proof of Lemma: The claim is immediate when P is constant or when deg P is even since P is bounded
from below. Let P (x) = an xn + · · · + a1 x + a0 be of odd degree greater than 1, and assume without

4
 loss of generality that an > 0. Since P (x + 1) − P (x) = an nxn−1 + . . . , and n − 1 > 0, the gap between
P (x) and P (x + 1) grows arbitrarily for large x. The claim follows. 
Suppose deg P 6= 1. We will inductively construct a sequence {ai } such that for any indices i < j and
any integer k it holds that ai + ai+1 + · · · + aj 6= P (k). Suppose that we have constructed the sequence
up to ai , and m is an integer with smallest magnitude yet to appear in the sequence. We will add two
more terms to the sequence. Take ai+2 = m. Consider all the new sums of at least two consecutive
terms; each of them contains ai+1 . Hence all such sums are in the interval [ai+1 − A, ai+1 + B] for fixed
constants A, B. The lemma allows us to choose ai+1 so that all such sums avoid the range of P .
Alternate Solution for Part 1: Again, suppose P (x) = cx+d, and assume without loss of generality
that c > d ≥ 0. Let Si = {aj + aj+1 + · · · + ai (mod c) | j = 1, 2, . . . , i}. Then Si+1 = {si + ai+1
(mod c) | si ∈ Si } ∪ {ai+1 (mod c)}. Hence |Si+1 | = |Si | or Si+1 = |Si | + 1, with the former occuring
exactly when 0 ∈ Si . Since |Si | ≤ c, the latter can only occur finitely many times, so there exists I
such that 0 ∈ Si for all i ≥ I. Let t > I be an index with at ≡ d (mod c). Then we can find a sum of
at least two consecutive terms ending at at and congruent to d (mod c).
Alternate Construction when P (x) is constant or of even degree
If P (x) is of even degree, then P is bounded from below or from above. In case of P is constant
or bounded from above, then there exists a positive integer c such that P (x) < c. Let {ai } be the
sequence
0, 1, −1, 2, 3, −2, 4, 5, −3, · · ·
which is given by a3n+1 = 2n, a3n+2 = 2n + 1, a3n+3 = −(n + 1) for all n ≥ 0. Notice that for
any i < j we have ai + · · · + aj ≥ 0 . Then for the sequence {bn } defined by bn = an + c, clearly
bi + · · · + bj ≥ (ai + · · · + aj ) + 2c > c which is out side the range of P (x).
Now if P is bounded from below, there exist a positive integer c such that P (x) > −c. In this case,
take bn to be bn = −an − c. Then for all i < j we have bi + · · · + bj ≤ −(a1 + · · · an ) − 2c < −c which
is again out side the range of P (x).

5. Let n ≥ 3 be a fixed integer. The number 1 is written n times on a blackboard. Below the blackboard,
there are two buckets that are initially empty. A move consists of erasing two of the numbers a and b,
replacing them with the numbers 1 and a + b, then adding one stone to the first bucket and gcd(a, b)
stones to the second bucket. After some finite number of moves, there are s stones in the first bucket and
t stones in the second bucket, where s and t are positive integers. Find all possible values of the ratio st .

Solution:
The answer is the set of all rational numbers in the interval [1, n − 1). First, we show that no other
numbers are possible. Clearly the ratio is at least 1, since for every move, at least one stone is added
to the second bucket. Note that the number s of stones in the first bucket is always equal to p − n,
where p is the sum of the numbers on the blackboard. We will assume that the numbers are written
in a row, and whenever two numbers a and b are erased, a + b is written in the place of the number on
the right. Let a1 , a2 , ..., an be the numbers on the blackboard from left to right, and let

q = 0 · a1 + 1 · a2 + · · · + (n − 1)an .

Since each number ai is at least 1, we always have

n(n − 1) n(n − 1)
q ≤ (n − 1)p − (1 + · · · + (n − 1)) = (n − 1)p − = (n − 1)s + .
2 2
Also, if a move changes ai and aj with i < j, then t changes by gcd(ai , aj ) ≤ ai and q increases by

(j − 1)ai − (i − 1)(ai − 1) ≥ iai − (i − 1)(ai − 1) ≥ ai .

Hence q − t never decreases. We may assume without loss of generality that the first move involves the
rightmost 1. Then immediately after this move, q = 0 + 1 + · · · + (n − 2) + (n − 1) · 2 = (n+2)(n−1)
2 and

5
t = 1. So after that move, we always have
(n + 2)(n − 1)
t≤q+1−
2
n(n − 1) (n + 2)(n − 1)
≤ (n − 1)s + − +1
2 2
= (n − 1)s − (n − 2) < (n − 1)s.
t t
Hence, s < n − 1. So s must be a rational number in [1, n − 1).

After a single move, we have st = 1, so it remains to prove that st can be any rational number in
(1, n − 1). We will now show by induction on n that for any positive integer a, it is possible to reach
a situation where there are n − 1 occurrences of 1 on the board and the number an−1 , with t and s
equal to an−2 (a − 1)(n − 1) and an−1 − 1, respectively. For n = 2, this is clear as there is only one
possible move at each step, so after a − 1 moves s and t will both be equal to a − 1. Now assume
that the claim is true for n − 1, where n > 2. Call the algorithm which creates this situation using
n − 1 numbers algorithm A. Then to reach the situation for size n, we apply algorithm A, to create
the number an−2 . Next, apply algorithm A again and then add the two large numbers, repeat until
we get the number an−1 . Then algorithm A was applied a times and the two larger numbers were
added a − 1 times. Each time the two larger numbers are added, t increases by an−2 and each time
algorithm A is applied, t increases by an−3 (a − 1)(n − 2). Hence, the final value of t is

t = (a − 1)an−2 + a · an−3 (a − 1)(n − 2) = an−2 (a − 1)(n − 1).

This completes the induction.

Now we can choose 1 and the large number b times for any positive integer b, and this will add b stones
to each bucket. At this point we have

t an−2 (a − 1)(n − 1) + b
= .
s an−1 − 1 + b
So we just need to show that for any rational number pq ∈ (1, n − 1), there exist positive integers a and
b such that
p an−2 (a − 1)(n − 1) + b
=
q an−1 − 1 + b
Rearranging, we see that this happens if and only if

qan−2 (a − 1)(n − 1) − p(an−1 − 1)

b= .
p−q
If we choose a ≡ 1 (mod p−q), then this will be an integer, so we just need to check that the numerator
is positive for sufficiently large a.

qan−2 (a − 1)(n − 1) − p(an−1 − 1) > qan−2 (a − 1)(n − 1) − pan−1

= an−2 (a(q(n − 1) − p) − (n − 1)) ,

which is positive for sufficiently large a since q(n − 1) − p > 0.

Alternative solution for the upper bound. Rather than starting with n occurrences of 1, we may
start with infinitely many 1s, but we are restricted to having at most n − 1 numbers which are not
equal to 1 on the board at any time. It is easy to see that this does not change the problem. Note
also that we can ignore the 1 we write on the board each move, so the allowed move is to rub off two
numbers and write their sum. We define the width and score of a number on the board as follows.
Colour that number red, then reverse every move up to that point all the way back to the situation
when the numbers are all 1s. Whenever a red number is split, colour the two replacement numbers

6
red. The width of the original number is equal to the maximum number of red integers greater than 1
which appear on the board at the same time. The score of the number is the number of stones which
were removed from the second bucket during these splits. Then clearly the width of any number is
at most n − 1. Also, t is equal to the sum of the scores of the final numbers. We claim that if a
number p > 1 has a width of at most w, then its score is at most (p − 1)w. We will prove this by
strong induction on p. If p = 1, then clearly p has a score of 0, so the claim is true. If p > 1, then p
was formed by adding two smaller numbers a and b. Clearly a and b both have widths of at most w.
Moreover, if a has a width of w, then at some point in the reversed process there will be w numbers
in the set {2, 3, 4, ...} that have split from a, and hence there can be no such numbers at this point
which have split from b. Between this point and the final situation, there must always be at least one
number in the set {2, 3, 4, ...} that split from a, so the width of b is at most w − 1. Therefore, a and b
cannot both have widths of w, so without loss of generality, a has width at most w and b has width at
most w − 1. Then by the inductive hypothesis, a has score at most (a − 1)w and b has score at most
(b − 1)(w − 1). Hence, the score of p is at most

(a − 1)w + (b − 1)(w − 1) + gcd(a, b) ≤ (a − 1)w + (b − 1)(w − 1) + b

= (p − 1)w + 1 − w
≤ (p − 1)w.

This completes the induction.

Now, since each number p in the final configuration has width at most (n − 1), it has score less than
(n − 1)(p − 1). Hence the number t of stones in the second bucket is less than the sum over the values
of (n − 1)(p − 1), and s is equal to the sum of the the values of (p − 1). Therefore, st < n − 1.

7
 APMO 2021 Solution

1. Prove that for each real number r > 2, there are exactly two or three positive real numbers x satisfying
the equation x2 = rbxc.
Note: bxc denotes the largest integer less than or equal to x
Solution Let r > 2 be a real number. Let x be a positive real number such that x2 = rbxc with
bxc = k. Since x > 0 and x2 = rk, we also have k > 0. From k ≤ x < k + 1, we get k 2 ≤ x2 = rk <
k 2 + 2k + 1 ≤ k 2 + 3k, hence k ≤ r < k + 3, or r − 3 < k ≤ r. There are at most three positive integers
in the interval (r − 3, r]. Thus there are at most three possible values for k. Consequently, there are
at most three positive solutions to the given equation.
Now suppose that k is a positive
√ p in the interval [r − 2, r]. There √
integer are at least two such positive
integer. Observe that k ≤ rk ≤ (k + 2)k < k + 1 and so rk = √ rb rkc. We conclude that the
2
equation x = rbxc has at least two positive solutions, namely x = rk with k ∈ [r − 2, r].
2. For a polynomial P and a positive integer n, define Pn as the number of positive integer pairs (a, b)
such that a < b ≤ n and |P (a)| − |P (b)| is divisible by n.
Determine all polynomial P with integer coefficients such that for all positive integers n, Pn ≤ 2021.
Solution There are two possible families of solutions:
• P (x) = x + d, for some integer d ≥ −2022.
• P (x) = −x + d, for some integer d ≤ 2022.

Suppose P satisfies the problem conditions. Clearly P cannot be a constant polynomial. Notice that
a polynomial P satifies the conditions if and only if −P also satisfies them. Hence, we may assume
the leading coefficient of P is positive. Then, there exists positive integer M such that P (x) > 0 for
x ≥ M.
Lemma 1. For any positive integer n, the integers P (1), P (2), . . . , P (n) leave pairwise distinct re-
mainders upon division by n.

Proof. Assume for contradiction that this is not the case. Then, for some 1 ≤ y < z ≤ n, there exists
0 ≤ r ≤ n − 1 such that P (y) ≡ P (z) ≡ r (mod n). Since P (an + b) ≡ P (b) (mod n) for all a, b
integers, we have P (an + y) ≡ P (an + z) ≡ r (mod n) for any integer a. Let A be a positive integer
such that An ≥ M , and let k be a positive integer such that k > 2A + 2021. Each of the 2(k − A)
integers P (An + y), P (An + z), P ((A + 1)n + y), P ((A + 1)n + z), . . . , P ((k − 1)n + y), P ((k − 1)n + z)
leaves one of the k remainders
r, n + r, 2n + r, . . . , (k − 1)n + r
upon division by kn. This implies that at least 2(k − A) − k = k − 2A (possibly overlapping) pairs
leave the same remainder upon division by kn. Since k − 2A > 2021 and all of the 2(k − A) integers
are positive, we find more than 2021 pairs a, b with a < b ≤ kn for which |P (b)| − |P (a)| is divisible by
kn - hence, Pkn > 2021, a contradiction.

1
 Next, we show that P is linear. Assume that this is not the case, i.e., deg P ≥ 2. Then we
can find a positive integer k such that P (k) − P (1) ≥ k. This means that among the integers
P (1), P (2), . . . , P (P (k) − P (1)), two of them, namely P (k) and P (1), leave the same remainder upon
division by P (k) − P (1) - contradicting the lemma (by taking n = P (k) − P (1)). Hence, P must be
linear.
We can now write P (x) = cx + d with c > 0. We prove that c = 1 by two ways.
Solution 1 If c ≥ 2, then P (1) and P (2) leave the same remainder upon division by c, contradicting
the Lemma. Hence c = 1.


 
3
Solution 2 Suppose c ≥ 2. Let n be a positive integer such that n > 2cM , n 1 − > 2022 and
  2c
3n 3n n 
2c|n. Notice that for any positive integers i such that + i < n, P +i −P + i = n.
  2c 2c 2c
n 3n
Hence, + i, + i satifies the condition in the question for all positive integers i such that
2c 2c
3n
+ i < n. Hence, Pn > 2021, a contradiction. Then, c = 1.
2c


If d ≤ −2023, then there are at least 2022 pairs a < b such that P (a) = P (b), namely (a, b) =
(1, −2d − 1), (2, −2d − 2), ..., (−d − 1, −d + 1). This implies that d ≥ −2022.
Finally, we verify that P (x) = x + d satisfies the condition for any d ≥ −2022. Fix a positive integer
n. Note that ||P (b)| − |P (a)|| < n for all positive integers a < b ≤ n, so the only pairs a, b for which
|P (b)| − |P (a)| could be divisible by n are those for which |P (a)| = |P (b)|. When d ≥ −2022, there are
indeed at most 2021 such pairs.

3. Let ABCD be a cyclic convex quadrilateral and Γ be its circumcircle. Let E be the intersection of the
diagonals AC and BD, let L be the center of the circle tangent to sides AB, BC, and CD, and let M
be the midpoint of the arc BC of Γ not containing A and D. Prove that the excenter of triangle BCE
opposite E lies on the line LM .
Solution 1
Let L be the intersection of the bisectors of ∠ABC and ∠BCD. Let N be the E-excenter of 4BCE.
Let ∠BAC = ∠BDC = α, ∠DBC = β and ∠ACB = γ.
We have the following:
1 1 1 1 1
∠CBL = ∠ABC = 90◦ − α − γ and ∠BCL = 90◦ − α − β,
2 2 2 2 2
◦ 1 ◦ 1
∠CBN = 90 − β and ∠BCN = 90 − γ,
2 2
◦ 1 ◦ 1
∠M BL = ∠M BC + ∠CBL = 90 − γ and ∠M CL = 90 − β,
2 2
◦ 1
∠LCN = ∠LBN = 180 − (α + β + γ) .
2

Applying the sine rule to 4M BL and 4M CL we obtain

MB MC sin ∠BLM sin ∠CLM
= = = .
ML ML sin ∠M BL sin ∠M CL
It follows that
sin ∠BLM sin ∠M BL cos(γ/2)
= = . (1)
sin ∠CLM sin ∠M CL cos(β/2)

2
 Now
sin ∠BLM sin ∠LCN sin ∠N BC cos(γ/2) sin(90◦ − 12 β)
· · = · = 1.
sin ∠M LC sin ∠N CB sin ∠N BL cos(β/2) sin(90◦ − 12 γ)

Hence LM, BN, CN are concurrent and therefore L, M, N are collinear.

Alternative proof
We proceed similarly as above until the equation (1).
We use the following lemma.
sin α sin γ
Lemma: If π > α, β, γ, δ > 0, α + β = γ + δ < π, and sin β = sin δ , then α = γ and β = δ.
sin(θ−β) sin(θ−δ)
Proof of Lemma: Let θ = α + β = γ + δ. Then sin β = sin δ .

⇐⇒ sin(θ − β) sin δ = sin(θ − δ) sin β

⇐⇒ (sin θ cos β − sin β cos θ) sin δ = (sin θ cos δ − sin δ cos θ) sin β
⇐⇒ sin θ cos β sin δ = sin θ cos δ sin β
⇐⇒ sin θ sin(β − δ) = 0
Since 0 < θ < π, then sin θ 6= 0. Therefore, sin(β − δ) = 0, and we must have β = δ.
Applying the sine rule to 4N BL and 4N CL we obtain
NB sin ∠BLN
= ,
NL sin ∠LBN
NC sin ∠CLN
= .
NL sin ∠LCN
Since ∠LBN = ∠LCN , it follows that
sin ∠BLN NB sin ∠BCN cos(γ/2) sin ∠BLM
= = = = .
sin ∠CLN NC sin ∠CBN cos(β/2) sin ∠CLM

By the lemma, it is concluded that ∠BLM = ∠BLN and ∠CLM = ∠CLN . Therefore, L, M, N are
collinear.
Solution 2
Denote by N the excenter of triangle BCE opposite E. Since BL bisects ∠ABC, we have ∠CBL =
∠ABC 1
. Since M is the midpoint of arc BC, we have ∠M BC = (∠M BC + ∠M CB) It follows by
2 2
angle chasing that
1
∠M BL = ∠M BC + ∠CBL = (∠M BC + ∠M CB + ∠ABC)
2
1 ∠BCE
= (∠M BA + ∠M CB) = 90◦ − = ∠BCN.
2 2
Denote by X and Y the second intersections of lines BM and CM with the circumcircle of BCL,
respectively. Since ∠M BC = ∠M CB, we have BC k XY . It suffices to show that BN k XL and
CN k Y L. Indeed, from this it follows that 4BCN ∼ 4XY L, and therefore a homothety with center
M that maps B to X and C to Y also maps N to L, implying that N lies on the line LM .
By symmetry, it suffices to show that CN k Y L, which is equivalent to showing that ∠BCN = ∠XY L.
But we have ∠BCN = ∠M BL = ∠XBL = ∠XY L, completing the proof.

4. Given a 32 × 32 table, we put a mouse (facing up) at the bottom left cell and a piece of cheese at
several other cells. The mouse then starts moving. It moves forward except that when it reaches a
piece of cheese, it eats a part of it, turns right, and continues moving forward. We say that a subset
of cells containing cheese is good if, during this process, the mouse tastes each piece of cheese exactly
once and then falls off the table. Show that:

3
 (a) No good subset consists of 888 cells.
(b) There exists a good subset consisting of at least 666 cells.
Solution.

(a) For the sake of contradiction, assume a good subset consisting of 888 cells exists. We call those
cheese-cells and the other ones gap-cells. Observe that since each cheese-cell is visited once, each
gap-cell is visited at most twice (once vertically and once horizontally). Define a finite sequence s
whose i-th element is C if the i-th step of the mouse was onto a cheese-cell, and G if it was onto a
gap-cell. By assumption, s contains 888 C’s. Note that s does not contain a contiguous block of
4 (or more) C’s. Hence s contains at least 888/3 = 296 such C-blocks and thus at least 295 G’s.
But since each gap-cell is traversed at most twice, this implies there are at least d295/2e = 148
gap-cells, for a total of 888 + 148 = 1036 > 322 cells, a contradiction.
(b) Let Li , Xi be two 2i × 2i tiles that allow the mouse to “turn left” and “cross”, respectively. In
detail, the “turn left” tiles allow the mouse to enter at its bottom left cell facing up and to leave
at its bottom left cell facing left. The “cross” tiles allow the mouse to enter at its top right facing
down and leave at its bottom left facing left, while also to enter at its bottom left facing up and
leave at its top right facing right.

(a) Basic tiles (b) Inductive construction (c) 16 × 16

Li+1 Xi+1

L1 X1 Li Li Li Xi

Xi Li Xi Li

Note that given two 2i × 2i tiles Li , Xi we can construct larger 2i+1 × 2i+1 tiles Li+1 , Xi+1
inductively as shown on in (b). The construction works because the path intersects itself (or the
other path) only inside the smaller X-tiles where it works by induction.
For a tile T , let |T | be the number of pieces of cheese in it. By straightforward induction,
|Li | = |Xi | + 1 and |Li+1 | = 4 · |Li | − 1. From the initial condition |L1 | = 3. We now easily
compute |L2 | = 11, |L3 | = 43, |L4 | = 171, and |L5 | = 683. Hence we get the desired subset.

Another proof of (a).

Let XN be the largest possible density of cheese-cells in a good subset on an N ×N table. We will show
that XN ≤ 4/5 + o(1). Specifically, this gives X32 ≤ 817/1024. We look at the (discrete analogue) of
the winding number of the trajectory of the mouse. Since the mouse enters and leaves the table, for
every 4 right turns in its trajectory there has to be a self-crossing. But each self-crossing requires a
different empty square, hence XN ≤ 4/5.

5. Determine all functions f : Z → Z such that f (f (a) − b) + bf (2a) is a perfect square for all integers a
and b.
Solution 1.
There are two families of functions which satisfy the condition:
(
0 if n is even, and
(1) f (n) =
any perfect square if n is odd
(2) f (n) = n2 , for every integer n.

4
It is straightforward to verify that the two families of functions are indeed solutions. Now, suppose
that f is any function which satisfies the condition that f (f (a) − b) + bf (2a) is a perfect square for
every pair (a, b) of integers. We denote this condition by (*). We will show that f must belong to
either Family (1) or Family (2).
Claim 1. f (0) = 0 and f (n) is a perfect square for every integer n.
Proof. Plugging (a, b) → (0, f (0)) in (*) shows that f (0)(f (0) + 1) = z 2 for some integer z. Thus,
(2f (0) + 1 − 2z)(2f (0) + 1 + 2z) = 1. Therefore, f (0) is either -1 or 0.
Suppose, for sake of contradiction, that f (0) = −1. For any integer a, plugging (a, b) → (a, f (a)) implies
that f (a)f (2a) − 1 is a square. Thus, for each a ∈ Z, there exists x ∈ Z such that f (a)f (2a) = x2 + 1
This implies that any prime divisor of f (a) is either 2 or is congruent to 1 (mod 4), and that 4 - f (a),
for every a ∈ Z.
Plugging (a, b) → (0, 3) in (*) shows that f (−4) − 3 is a square. Thus, there is y ∈ Z such that
f (−4) = y 2 + 3. Since 4 - f (−4), we note that f (−4) is a positive integer congruent to 3 (mod 4),
but any prime dividing f (−4) is either 2 or is congruent to 1 (mod 4). This gives a contradiction.
Therefore, f (0) must be 0.
For every integer n, plugging (a, b) → (0, −n) in (*) shows that f (n) is a square.
Replacing b with f (a) − b, we find that for all integers a and b,

f (b) + (f (a) − b)f (2a) is a square. (**)

Now, let S be the set of all integers n such that f (n) = 0. We have two cases:

• Case 1: S is unbounded from above.

We claim that f (2n) = 0 for any integer n. Fix some integer n, and let k ∈ S with k > f (n).
Then, plugging (a, b) 7→ (n, k) in (**) gives us that f (k) + (f (n) − k)f (2n) = (f (n) − k)f (2n) is
a square. But f (n) − k < 0 and f (2n) is a square by Claim 1. This is possible only if f (2n) = 0.
In summary, f (n) = 0 whenever n is even and Claim 1 shows that f (n) is a square whenever n is
odd.
• Case 2: S is bounded from above.
Let T be the set of all integers n such that f (n) = n2 . We show that T is unbounded from above.
In fact, we show that p+12 ∈ T for all primes p big enough.
Fix a prime number p big enough, and let n = p+1 2 . Plugging (a, b) 7→ (n, 2n) in (**) shows us
that f (2n)(f (n) − 2n + 1) is a square for any integer n. For p big enough, we have 2n 6∈ S, so
f (2n) is a non-zero square. As a result, when p is big enough, f (n) and f (n) − 2n + 1 = f (n) − p
are both squares. Writing f (n) = k 2 and f (n) − p = m2 for some k, m ≥ 0, we have

(k + m)(k − m) = k 2 − m2 = p =⇒ k + m = p, k − m = 1 =⇒ k = n, m = n − 1.

Thus, f (n) = k 2 = n2 , giving us n = p+1

2 ∈ T.
Next, for all k ∈ T and n ∈ Z, plugging (a, b) 7→ (n, k) in (**) shows us that k 2 + (f (n) − k)f (2n)
is a square. But that means (2k − f (2n))2 − (f (2n)2 − 4f (n)f (2n)) = 4(k 2 + (f (n) − k)f (2n)) is
also a square. When k is large enough, we have |f (2n)2 − 4f (n)f (2n)| + 1 < |2k − f (2n)|. As a
result, we must have f (2n)2 = 4f (n)f (2n) and thus f (2n) ∈ {0, 4f (n)} for all integers n.
Finally, we prove that f (n) = n2 for all integers n. Fix n, and take k ∈ T big enough such that
2k 6∈ S. Then, we have f (k) = k 2 and f (2k) = 4f (k) = 4k 2 . Plugging (a, b) 7→ (k, n) to (**)
shows us that f (n) + (k 2 − n)4k 2 = (2k 2 − n)2 + (f (n) − n2 ) is a square. Since T is unbounded
from above, we can take k ∈ T such that 2k 6∈ S and also |2k 2 − n| > |f (n) − n2 |. This forces
f (n) = n2 , giving us the second family of solution.

Another approach of Case 1.

Claim 2. One of the following is true.

5
 (i) For every integer n, f (2n) = 0.
(ii) There exists an integer K > 0 such that for every integer n ≥ K, f (n) > 0.
Proof. Suppose that there exists an integer α 6= 0 such that f (2α) > 0. We claim that for every integer
n ≥ f (α) + 1, we have f (n) > 0.
For every n ≥ f (α) + 1, plugging (a, b) → (α, f (α) − n) in (*) shows that f (n) + (f (α) − n)f (2α) is a
square, and in particular, is non-negative. Hence, f (n) ≥ (n − f (α))f (2α) > 0, as desired.
If f belongs to Case (i), Claim 1 shows that f belongs to Family (1).
If f belongs to Case (ii), then S is bounded from above. From Case 2 we get f (n) = n2 .

6
 APMO 2022 Solution

1. Find all pairs (a, b) of positive integers such that a3 is a multiple of b2 and b − 1 is a multiple of a − 1.
Note: An integer n is said to be a multiple of an integer m if there is an integer k such that n = km.
Solution
Solution 1.1
By inspection, we see that the pairs (a, b) with a = b are solutions, and so too are the pairs (a, 1). We
will see that these are the only solutions.
• Case 1. Consider the case b < a. Since b − 1 is a multiple of a − 1, it follows that b = 1. This
yields the second set of solutions described above.
• Case 2. This leaves the case b ≥ a. Since the positive integer a3 is a multiple of b2 , there is a
positive integer c such that a3 = b2 c.
Note that a ≡ b ≡ 1 modulo a − 1. So we have

1 ≡ a3 = b2 c ≡ c (mod a − 1).

If c < a, then we must have c = 1, hence, a3 = b2 . So there is a positive integer d such that
a = d2 and b = d3 . Now a − 1 | b − 1 yields d2 − 1 | d3 − 1. This implies that d + 1 | d(d + 1) + 1,
which is impossible.
If c ≥ a, then b2 c ≥ b2 a ≥ a3 = b2 c. So there’s equality throughout, implying a = c = b. This
yields the first set of solutions described above.
Therefore, the solutions described above are the only solutions.

Solution 1.2
We will start by showing that there are positive integers x, c, d such that a = x2 cd and b = x3 c. Let
g = gcd(a, b) so that a = gd and b = gx for some coprime d and x. Then, b2 | a3 is equivalent to
g 2 x2 | g 3 d3 , which is equivalent to x2 | gd3 . Since x and d are coprime, this implies x2 | g. Hence,
g = x2 c for some c, giving a = x2 cd and b = x3 c as required.
Now, it remains to find all positive integers x, c, d satisfying

x2 cd − 1 | x3 c − 1.

That is, x3 c ≡ 1 (mod x2 cd − 1). Assuming that this congruence holds, it follows that d ≡ x3 cd ≡ x
(mod x2 cd − 1). Then, either x = d or x − d ≥ x2 cd − 1 or d − x ≥ x2 cd − 1.
• If x = d then b = a.
• If x − d ≥ x2 cd − 1, then x − d ≥ x2 cd − 1 ≥ x − 1 ≥ x − d. Hence, each of these inequalities must
in fact be an equality. This implies that x = c = d = 1, which implies that a = b = 1.
• If d − x ≥ x2 cd − 1, then d − x ≥ x2 cd − 1 ≥ d − 1 ≥ d − x. Hence, each of these inequalities must
in fact be an equality. This implies that x = c = 1, which implies that b = 1.
Hence the only solutions are the pairs (a, b) such that a = b or b = 1. These pairs can be checked to
satisfy the given conditions.

1
 

Solution 1.3
All answers are (n, n) and (n, 1) where n is any positive integer. They all clearly work.
To show that these are all solutions, note that we can easily eliminate the case a = 1 or b = 1. Thus,
assume that a, b 6= 1 and a 6= b. By the second divisibility, we see that a − 1 | b − a. However,
gcd(a, b) | b − a and a − 1 is relatively prime to gcd(a, b). This implies that (a − 1) gcd(a, b) | b − a,
b−1
which implies gcd(a, b) − 1.
a−1
b−1
The last relation implies that gcd(a, b) < , since the right-hand side are positive. However, due
a−1
to the first divisibility,
gcd(a, b)3 = gcd(a3 , b3 ) ≥ gcd(b2 , b3 ) = b2 .
Combining these two inequalities, we get that
2 b−1 b
b3 < <2 .
a−1 a
1 3
This implies a < 2b 3 . However, b2 | a3 gives b ≤ a 2 . This forces
3 1 √
a < 2(a 2 ) 3 = 2 a =⇒ a < 4.

Extracting a = 2, 3 by hand yields no additional solution.

2. Let ABC be a right triangle with ∠B = 90◦ . Point D lies on the line CB such that B is between D
and C. Let E be the midpoint of AD and let F be the second intersection point of the circumcircle of
4ACD and the circumcircle of 4BDE. Prove that as D varies, the line EF passes through a fixed
point.

2
 Solution
Solution 2.1
Let the line EF intersect the line BC at P and the circumcircle of 4ACD at G distinct from F . We
will prove that P is the fixed point.
First, notice that 4BED is isosceles with EB = ED. This implies ∠EBC = ∠EDP .
Then, ∠DAG = ∠DF G = ∠EBC = ∠EDP which implies AG k DC. Hence, AGCD is an isosceles
trapezoid.
∼ 4DEP and AG = DP .
Also, AG k DC and AE = ED. This implies 4AEG =
Since B is the foot of the perpendicular from A onto the side CD of the isosceles trapezoid AGCD,
we have P B = P D + DB = AG + DB = BC, which does not depend on the choice of D. Hence, the
initial statement is proven.
Solution 2.2
Set up a coordinate system where BC is along the positive x-axis, BA is along the positive y-axis,
and B is the origin. Take A = (0, a), B = (0, 0), C = (c, 0), D = (−d, 0) where a, b, c, d > 0. Then
E = (− d2 , a2 ). The general equation of a circle is

x2 + y 2 + 2f x + 2gy + h = 0 (1)

Substituting the coordinates of A, D, C into (1) and solving for f, g, h, we find that the equation of the
circumcircle of 4ADC is
cd
x2 + y 2 + (d − c)x + ( − a)y − cd = 0. (2)
a
Similarly, the equation of the circumcircle of 4BDE is
d2 a
x2 + y 2 + dx + ( − )y = 0. (3)
2a 2

Then (3)−(2) gives the equation of the line DF which is

a2 + d2 − 2cd
cx + y + cd = 0. (4)
2a
Solving (3) and (4) simultaneously, we get

c(d2 − a2 − 2cd)
 
2ac(c − d)
F = 2 2
, 2 ,
a + (d − 2c) a + (d − 2c)2
and the other solution D = (−d, 0).
From this we obtain the equation of the line EF which is ax + (d − 2c)y + ac = 0. It passes through
P (−c, 0) which is independent of d.
3. Find all positive integers k < 202 for which there exists a positive integer n such that
n n o  2n  
kn

k
+ + ··· + = ,
202 202 202 2
where {x} denote the fractional part of x.
Note: {x} denotes the real number k with 0 ≤ k < 1 such that x − k is an integer.
Solution
Denote the equation in the problem statement as (*), and note that it is equivalent  to the
 condition
in
that the average of the remainders when dividing n, 2n, . . . , kn by 202 is 101. Since is invariant
202
in each residue class modulo 202 for each 1 ≤ i ≤ k, it suffices to consider 0 ≤ n < 202.

3
  
in
If n = 0, so is , meaning that (*) does not hold for any k. If n = 101, then it can be checked
202
that (*) is satisfied if and only if k = 1. From now on, we will assume that 101 - n.
   
in in in
For each 1 ≤ i ≤ k, let ai = = − . Rewriting (*) and multiplying the equation by
202 202 202
202, we find that

n(1 + 2 + . . . + k) − 202(a1 + a2 + . . . + ak ) = 101k.

Equivalently, letting z = a1 + a2 + . . . + ak ,

nk(k + 1) − 404z = 202k.

Since n is not divisible by 101, which is prime, it follows that 101 | k(k + 1). In particular, 101 | k or
101 | k + 1. This means that k ∈ {100, 101, 201}. We claim that all these values of k work.

• If k = 201, we may choose n = 1. The remainders when dividing n, 2n, . . . , kn by 202 are 1, 2,
. . . , 201, which have an average of 101.
• If k = 100, we may choose n = 2. The remainders when dividing n, 2n, . . . , kn by 202 are 2, 4,
. . . , 200, which have an average of 101.
• If k = 101, we may choose n = 51. To see this, note that the first four remainders are 51, 102, 153,
2, which have an average of 77. The next four remainders (53, 104, 155, 4) are shifted upwards
from the first four remainders by 2 each, and so on, until the 25th set of the remainders (99,
150, 201, 50) which have an average of 125. Hence, the first 100 remainders have an average of
77 + 125
= 101. The 101th remainder is also 101, meaning that the average of all 101 remainders
2
is 101.

In conclusion, all values k ∈ {1, 100, 101, 201} satisfy the initial condition.

4. Let n and k be positive integers. Cathy is playing the following game. There are n marbles and k
boxes, with the marbles labelled 1 to n. Initially, all marbles are placed inside one box. Each turn,
Cathy chooses a box and then moves the marbles with the smallest label, say i, to either any empty
box or the box containing marble i + 1. Cathy wins if at any point there is a box containing only
marble n.
Determine all pairs of integers (n, k) such that Cathy can win this game.
Solution
We claim Cathy can win if and only if n ≤ 2k−1 .

First, note that each non-empty box always contains a consecutive sequence of labeled marbles. This
is true since Cathy is always either removing from or placing in the lowest marble in a box. As a
consequence, every move made is reversible.

Next, we prove by induction that Cathy can win if n = 2k−1 . The base case of n = k = 1 is trivial.
Assume a victory can be obtained for m boxes and 2m−1 marbles. Consider the case of m + 1 boxes
and 2m marbles. Cathy can first perform a sequence of moves so that only marbles 2m−1 , . . . , 2m are
left in the starting box, while keeping one box, say B, empty. Now move the marble 2m−1 to box B,
then reverse all of the initial moves while treating B as the starting box. At the end of that, we will
have marbles 2m−1 + 1, . . . , 2m in the starting box, marbles 1, 2, . . . , 2m−1 in box B, and m − 1 empty
boxes. By repeating the original sequence of moves on marbles 2m−1 + 1, . . . , 2m , using the m boxes
that are not box B, we can reach a state where only marble 2m remains in the starting box. Therefore

4
 a victory is possible if n = 2k−1 or smaller.

We now prove by induction that Cathy loses if n = 2k−1 + 1. The base case of n = 2 and k = 1 is
trivial. Assume a victory is impossible for m boxes and 2m−1 +1 marbles. For the sake of contradiction,
suppose that victory is possible for m + 1 boxes and 2m + 1 marbles. In a winning sequence of moves,
consider the last time a marble 2m−1 + 1 leaves the starting box, call this move X. After X, there
cannot be a time when marbles 1, . . . , 2m−1 + 1 are all in the same box. Otherwise, by reversing these
moves after X and deleting marbles greater than 2m−1 + 1, it gives us a winning sequence of moves
for 2m−1 + 1 marbles and m boxes (as the original starting box is not used here), contradicting the
inductive hypothesis. Hence starting from X, marbles 1 will never be in the same box as any marbles
greater than or equal to 2m−1 + 1.

Now delete marbles 2, . . . , 2m−1 and consider the winning moves starting from X. Marble 1 would only
move from one empty box to another, while blocking other marbles from entering its box. Thus we
effectively have a sequence of moves for 2m−1 + 1 marbles, while only able to use m boxes. This again
contradicts the inductive hypothesis. Therefore, a victory is not possible if n = 2k−1 + 1 or greater.

5. Let a, b, c, d be real numbers such that a2 + b2 + c2 + d2 = 1. Determine the minimum value of

(a − b)(b − c)(c − d)(d − a) and determine all values of (a, b, c, d) such that the minimum value is
achieved.
Solution
1
The minimum value is − . There are eight equality cases in total. The first one is
8
√ √ √ √ !
1 3 1 3 1 3 1 3
+ ,− − , − ,− + .
4 4 4 4 4 4 4 4

Cyclic shifting all the entries give three more quadruples. Moreover, flipping the sign ((a, b, c, d) →
(−a, −b, −c, −d)) all four entries in each of the four quadruples give four more equality cases.
Solution 5.1
Since the expression is cyclic, we could WLOG a = max{a, b, c, d}. Let

S(a, b, c, d) = (a − b)(b − c)(c − d)(d − a)

Note that we have given (a, b, c, d) such that S(a, b, c, d) = − 81 . Therefore, to prove that S(a, b, c, d) ≥
− 18 , we just need to consider the case where S(a, b, c, d) < 0.
• Exactly 1 of a − b, b − c, c − d, d − a is negative.
Since a = max{a, b, c, d}, then we must have d − a < 0. This forces a > b > c > d. Now, let us
write
S(a, b, c, d) = −(a − b)(b − c)(c − d)(a − d)
Write a − b = y, b − c = x, c − d = w for some positive reals w, x, y > 0. Plugging to the original
condition, we have

(d + w + x + y)2 + (d + w + x)2 + (d + w)2 + d2 − 1 = 0 (∗)

and we want to prove that wxy(w + x + y) ≤ 81 . Consider the expression (∗) as a quadratic in d:

4d2 + d(6w + 4x + 2y) + ((w + x + y)2 + (w + x)2 + w2 − 1) = 0

5
 Since d is a real number, then the discriminant of the given equation has to be non-negative, i.e.
we must have

4 ≥ 4((w + x + y)2 + (w + x)2 + w2 ) − (3w + 2x + y)2

= (3w2 + 2wy + 3y 2 ) + 4x(w + x + y)
≥ 8wy + 4x(w + x + y)
= 4(x(w + x + y) + 2wy)

However, AM-GM gives us

 2
1 x(w + x + y) + 2wy 1
wxy(w + x + y) ≤ ≤
2 2 8

This proves S(a, b, c, d) ≥ − 18 for any a, b, c, d ∈ R such that a > b > c > d. Equality holds if and
only if w = y, x(w + x + y) = 2wy and wxy(w + x + y) = 81 . Solving these equations gives us
1
w4 = 16 which forces w = 12 since w > 0. Solving for x gives us x(x + 1) = 12 , and we will get
√ √
x = − 2 + 23 as x > 0. Plugging back gives us d = − 41 − 43 , and this gives us
1

√ √ √ √ !
1 3 1 3 1 3 1 3
(a, b, c, d) = + ,− + , − ,− −
4 4 4 4 4 4 4 4

Thus, any cyclic permutation of the above solution will achieve the minimum equality.
• Exactly 3 of a − b, b − c, c − d, d − a are negative Since a = max{a, b, c, d}, then a − b has to
be positive. So we must have b < c < d < a. Now, note that

S(a, b, c, d) = (a − b)(b − c)(c − d)(d − a)

= (a − d)(d − c)(c − b)(b − a)
= S(a, d, c, b)

Now, note that a > d > c > b. By the previous case, S(a, d, c, b) ≥ − 81 , which implies that

1
S(a, b, c, d) = S(a, d, c, b) ≥ −
8
as well. Equality holds if and only if
√ √ √ √ !
1 3 1 3 1 3 1 3
(a, b, c, d) = + ,− − , − ,− +
4 4 4 4 4 4 4 4

and its cyclic permutation.

Solution 5.2
1
The minimum value is − . There are eight equality cases in total. The first one is
8
√ √ √ √ !
1 3 1 3 1 3 1 3
+ ,− − , − ,− + .
4 4 4 4 4 4 4 4

Cyclic shifting all the entries give three more quadruples. Moreover, flipping the sign ((a, b, c, d) →
(−a, −b, −c, −d)) all four entries in each of the four quadruples give four more equality cases. We then
begin the proof by the following optimization:
Claim 1. In order to get the minimum value, we must have a + b + c + d = 0.

6
 a+b+c+d
Proof. Assume not, let δ = 4 and note that

(a − δ)2 + (b − δ)2 + (c − δ)2 + (d − δ)2 < a2 + b2 + c2 + d2 ,

so by shifting by δ and scaling, we get an even smaller value of (a − b)(b − c)(c − d)(d − a).

The key idea is to substitute the variables

x = ac + bd
y = ab + cd
z = ad + bc,

so that the original expression is just (x − y)(x − z). We also have the conditions x, y, z ≥ −0.5 because
of:

2x + (a2 + b2 + c2 + d2 ) = (a + c)2 + (b + d)2 ≥ 0.

Moreover, notice that

−1
0 = (a + b + c + d)2 = a2 + b2 + c2 + d2 + 2(x + y + z) =⇒ x + y + z = .
2
Now, we reduce to the following optimization problem.
Claim 2. Let x, y, z ≥ −0.5 such that x + y + z = −0.5. Then, the minimum value of

(x − y)(x − z)

is −1/8. Moreover, the equality case occurs when x = −1/4 and {y, z} = {1/4, −1/2}.

Proof. We notice that

  
1 1 1 1
(x − y)(x − z) + = 2y + z + 2z + y + +
8 2 2 8
  
1 2 1 1
= (4y + 4z + 1) + y + z+ ≥ 0.
8 2 2
1 1
The last inequality is true since both y + and z + are not less than zero.
2 2
1 1
The equality in the last inequality is attained when either y + = 0 or z + = 0, and 4y + 4z + 1 = 0.
2 2
This system of equations give (y, z) = (1/4, −1/2) or (y, z) = (−1/2, 1/4) as the desired equality cases.

Note: We can also prove (the weakened) Claim 2 by using Lagrange Multiplier, as follows. We first
prove that, in fact, x, y, z ∈ [−0.5, 0.5]. This can be proved by considering that

−2x + (a2 + b2 + c2 + d2 ) = (a − c)2 + (b − d)2 ≥ 0.

We will prove the Claim 2, only that in this case, x, y, z ∈ [−0.5, 0.5]. This is already sufficient to prove
the original question. We already have the bounded domain [−0.5, 0.5]3 , so the global minimum must
occur somewhere. Thus, it suffices to consider two cases:
• If the global minimum lies on the boundary of [−0.5, 0.5]3 . Then, one of x, y, z must be −0.5 or
0.5. By symmetry between y and z, we split to a few more cases.

7
 – If x = 0.5, then y = z = −0.5, so (x − y)(x − z) = 1, not the minimum.
– If x = −0.5, then both y and z must be greater or equal to x, so (x − y)(x − z) ≥ 0, not the
minimum.
– If y = 0.5, then x = z = −0.5, so (x − y)(x − z) = 0, not the minimum.
– If y = −0.5, then z = −x, so

(x − y)(x − z) = 2x(x + 0.5),

which obtain the minimum at x = −1/4. This gives the desired equality case.
• If the global minimum lies in the interior (−0.5, 0.5)3 , then we apply Lagrange multiplier:

∂ ∂
(x − y)(x − z) = λ (x + y + z) =⇒ 2x − y − z = λ.
∂x ∂x
∂ ∂
(x − y)(x − z) = λ (x + y + z) =⇒ z − x = λ.
∂y ∂y
∂ ∂
(x − y)(x − z) = λ (x + y + z) =⇒ y − x = λ.
∂z ∂z
Adding the last two equations gives λ = 0, or x = y = z. This gives (x − y)(x − z) = 0, not the
minimum.
Having exhausted all cases, we are done.

8
 APMO 2023 – Problems and Solutions
Problem 1
Let n ≥ 5 be an integer. Consider n squares with side lengths 1, 2, . . . , n, respectively. The
squares are arranged in the plane with their sides parallel to the x and y axes. Suppose that
no two squares touch, except possibly at their vertices.
Show that it is possible to arrange these squares in a way such that every square touches exactly
two other squares.
Solution 1
Set aside the squares with sidelengths n − 3, n − 2, n − 1, and n and suppose we can split the
remaining squares into two sets A and B such that the sum of the sidelengths of the squares
in A is 1 or 2 units larger than the sum of the sidelengths of the squares in B.
String the squares of each set A, B along two parallel diagonals, one for each diagonal. Now
use the four largest squares along two perpendicular diagonals to finish the construction: one
will have sidelengths n and n − 3, and the other, sidelengths n − 1 and n − 2. If the sum of the
sidelengths of the squares in A is 1 unit larger than the sum of the sidelengths of the squares
in B, attach the squares with sidelengths n − 3 and n − 1 to the A-diagonal, and the other two
squares to the B-diagonal. The resulting configuration, in which the A and B-diagonals are
represented by unit squares, and the sidelengths ai of squares from A and bj of squares from B
are indicated within each square, follows:

n−3 a1 a2 a3 ··· ak n−2

n b1 b2 b3 ··· b` n−1

√ √
((n−3)+(n−2)) 2
√ √
(n+(n−1)) 2
Since (a1 + a2 + · · · + ak ) 2 + 2
= (b1 + b2 + · · · + b` + 2) 2 + 2
, this
case is done.
If the sum of the sidelengths of the squares in A is 1 unit larger than the sum of the sidelengths
of the squares in B, attach the squares with sidelengths n − 3 and n − 2 to the A-diagonal, and
the other two squares to the B-diagonal. The resulting configuration follows:

n−3 a1 a2 a3 ··· ak n−1

n b1 b2 b3 ··· b` n−2

1
 √ √ √ √
Since (a1 + a2 + · · · + ak ) 2 + ((n−3)+(n−1))
2
2
= (b 1 + b 2 + · · · + b ` + 1) 2 + (n+(n−2)) 2
2
, this
case is also done. √ √
((n−3)+n) 2 (2n−3) 2
In both cases, the distance between
√
the A-diagonal and the B-diagonal is 2
= 2
.
√ √
(a +b ) 2
Since ai , bj ≤ n − 4, i 2j < (2n−4)
2
2
< (2n−3)
2
2
, and therefore the A- and B-diagonals do
not overlap.
Finally, we prove that it is possible to split the squares of sidelengths 1 to n − 4 into two sets
A and B such that the sum of the sidelengths of the squares in A is 1 or 2 units larger than
the sum of the sidelengths of the squares in B. One can do that in several ways; we present
two possibilities:
ˆ Direct construction: Split the numbers from 1 to n−4 into several sets of four consecutive
numbers {t, t+1, t+2, t+3}, beginning with the largest numbers; put squares of sidelengths
t and t + 3 in A and squares of sidelengths t + 1 and t + 2 in B. Notice that t + (t + 3) =
(t + 1) + (t + 2). In the end, at most four numbers remain.

– If only 1 remains, put the corresponding square in A, so the sum of the sidelengths
of the squares in A is one unit larger that those in B;
– If 1 and 2 remains, put the square of sidelength 2 in A and the square of sidelength
1 in B (the difference is 1);
– If 1, 2, and 3 remains, put the squares of sidelengths 1 and 3 in A, and the square
of sidelength 2 in B (the difference is 2);
– If 1, 2, 3, and 4 remains, put the squares of sidelengths 2 and 4 in A, and the squares
of sidelengths 1 and 3 in B (the difference is 2).

ˆ Indirect construction: Starting with A and B as empty sets, add the squares of sidelengths
n − 4, n − 3, . . . , 2 to either A or B in that order such that at each stage the difference
between the sum of the sidelengths in A and the sum of the sidelengths of B is minimized.
By induction it is clear that after adding an integer j to one of the sets, this difference is
at most j. In particular, the difference is 0, 1 or 2 at the end. Finally adding the final 1
to one of the sets can ensure that the final difference is 1 or 2. If necessary, flip A and B.

Solution 2
Solve the problem by induction in n. Construct examples for n = 5, 6, 7, 8, 9, 10 (one can use
the constructions from the previous solution, for instance). For n > 10, set aside the six larger
squares and arrange them in the following fashion:

n n−5 n−2

n−3 n−4 n−1

2
By the induction hypothesis, one can arrange the remaining n − 6 squares away from the six
larger squares, so we are done.

3
Problem 2
σ(n)
Find all integers n satisfying n ≥ 2 and p(n)−1 = n, in which σ(n) denotes the sum of all positive
divisors of n, and p(n) denotes the largest prime divisor of n.
Answer: n = 6.
Solution
Let n = pα1 1 · . . . · pαk k be the prime factorization of n with p1 < . . . < pk , so that p(n) = pk and
σ(n) = (1 + p1 + · · · + pα1 1 ) . . . (1 + pk + · · · + pαk k ). Hence
k   Y k k   k  
σ(n) Y 1 1 1 Y 1 Y 1
pk −1 = = 1 + + · · · + αi < 1 = 1+ ≤ 1+ = k+1,
n i=1
pi pi i=1
1− pi i=1
pi − 1 i=1
i

that is, pk −1 < k +1, which is impossible for k ≥ 3, because in this case pk −1 ≥ 2k −2 ≥ k +1.
Then k ≤ 2 and pk < k + 2 ≤ 4, which implies pk ≤ 3.
If k = 1 then n = pα and σ(n) = 1 + p + · · · + pα , and in this case n - σ(n), which is not
possible. Thus k = 2, and n = 2α 3β with α, β > 0. If α > 1 or β > 1,
  
σ(n) 1 1
> 1+ 1+ = 2.
n 2 3

Therefore α = β = 1 and the only answer is n = 6.

Comment: There are other ways to deal with the case n = 2α 3β . For instance, we have
2α+2 3β = (2α+1 − 1)(3β+1 − 1). Since 2α+1 − 1 is not divisible by 2, and 3β+1 − 1 is not divisible
by 3, we have
( ( (
2α+1 − 1 = 3β 2α+1 − 1 = 3β 2α+1 = 4
⇐⇒ ⇐⇒ ,
3β+1 − 1 = 2α+2 3 · (2α+1 − 1) − 1 = 2 · 2α+1 3β = 3

and n = 2α 3β = 6.

4
Problem 3
Let ABCD be a parallelogram. Let W , X, Y , and Z be points on sides AB, BC, CD, and
DA, respectively, such that the incenters of triangles AW Z, BXW , CY X and DZY form a
parallelogram. Prove that W XY Z is a parallelogram.
Solution
Let the four incenters be I1 , I2 , I3 , and I4 with inradii r1 , r2 , r3 , and r4 respectively (in the
order given in the question). Without loss of generality, let I1 be closer to AB than I2 . Let the
acute angle between I1 I2 and AB (and hence also the angle between I3 I4 and CD) be θ. Then

r2 − r1 = I1 I2 sin θ = I3 I4 sin θ = r4 − r3 ,

which implies r1 + r4 = r2 + r3 . Similar arguments show that r1 + r2 = r3 + r4 . Thus we obtain

r1 = r3 and r2 = r4 .

A W B
I1
I2
Z
X
I4
I3

D Y C

Now let’s consider the possible positions of W , X, Y , Z. Suppose AZ 6= CX. Without loss of
generality assume AZ > CX. Since the incircles of AW Z and CY X are symmetric about the
centre of the parallelogram ABCD, this implies CY > AW . Using similar arguments, we have

CY > AW =⇒ BW > DY =⇒ DZ > BX =⇒ CX > AZ,

which is a contradiction. Therefore AZ = CX =⇒ AW = CY and W XY Z is a parallelogram.

Comment: There are several ways to prove that r1 = r3 and r2 = r4 . The proposer shows the
following three alternative approaches:
Using parallel lines: Let O be the centre of parallelogram ABCD and P be the centre of
parallelogram I1 I2 I3 I4 . Since AI1 and CI3 are angle bisectors, we must have AI1 k CI3 . Let
`1 be the line through O parallel to AI1 . Since AO = OC, `1 is halfway between AI1 and CI3 .
Hence P must lie on `1 .
Similarly, P must also lie on `2 , the line through O parallel to BI2 . Thus P is the intersection
of `1 and `2 , which must be O. So the four incentres and hence the four incircles must be
symmetric about O, which implies r1 = r3 and r2 = r4 .
Using a rotation: Let the bisectors of ∠DAB and ∠ABC meet at X and the bisectors of
∠BCD and ∠CDA meet at Y . Then I1 is on AX, I2 is on BX, I3 is on CY , and I4 is on DY .
Let O be the centre of ABCD. Then a 180 degree rotation about O takes 4AXB to 4CY D.
Under the same transformation I1 I2 is mapped to a parallel segment I10 I20 with I10 on CY and I20
on DY . Since I1 I2 I3 I4 is a parallelogram, I3 I4 = I1 I2 and I3 I4 k I1 I2 . Hence I10 I20 and I3 I4 are
parallel, equal length segments on sides CY , DY and we conclude that I10 = I3 , I20 = I4 . Hence
the centre of I1 I2 I3 I4 is also O and we establish that by rotational symmetry that r1 = r3 and
r2 = r4 .
Using congruent triangles: Let AI1 and BI2 intersect at E and let CI3 and DI4 intersect at
F . Note that 4ABE and 4CDF are congruent, since AB = CD and corresponding pairs of
angles are equal (equal opposite angles parallelogram ABCD are each bisected).

5
Since AI1 k CI3 and I1 I2 k I4 I3 , ∠I2 I1 E = ∠I4 I3 F . Similarly ∠I1 I2 E = ∠I3 I4 F . Furthermore
I1 I2 = I3 I4 . Hence triangles I2 I1 E and I4I3 F are also congruent.
Hence ABEI1 I2 and DCF I3 I4 are congruent. Therefore, the perpendicular distance from I1
to AB equals the perpendicular distance from I3 to CD, that is, r1 = r3 . Similarly r2 = r4 .

6
Problem 4
Let c > 0 be a given positive real and R>0 be the set of all positive reals. Find all functions
f : R>0 → R>0 such that

f ((c + 1)x + f (y)) = f (x + 2y) + 2cx for all x, y ∈ R>0 .

Answer: f (x) = 2x for all x > 0.

Solution 1
We first prove that f (x) ≥ 2x for all x > 0. Suppose, for the sake of contradiction, that
f (y) < 2y for some positive y. Choose x such that f ((c + 1)x + f (y)) and f (x + 2y) cancel out,
that is,
2y − f (y)
(c + 1)x + f (y) = x + 2y ⇐⇒ x = .
c
Notice that x > 0 because 2y − f (y) > 0. Then 2cx = 0, which is not possible. This
contradiction yields f (y) ≥ 2y for all y > 0.
Now suppose, again for the sake of contradiction, that f (y) > 2y for some y > 0. Define the
following sequence: a0 is an arbitrary real greater than 2y, and f (an ) = f (an−1 ) + 2cx, so that
(
(c + 1)x + f (y) = an
⇐⇒ x = an−1 − 2y and an = (c + 1)(an−1 − 2y) + f (y).
x + 2y = an−1

If x = an−1 − 2y > 0 then an > f (y) > 2y, so inductively all the substitutions make sense.
For the sake of simplicity, let bn = an − 2y, so bn = (c + 1)bn−1 + f (y) − 2y (∗). Notice that
x = bn−1 in the former equation, so f (an ) = f (an−1 ) + 2cbn−1 . Telescoping yields
n−1
X
f (an ) = f (a0 ) + 2c bi .
i=0
 
One can find bn from the recurrence equation (∗): bn = b0 + f (y)−2y c
(c + 1)n − f (y)−2y
c
, and
then
n−1   
X f (y) − 2y i f (y) − 2y
f (an ) = f (a0 ) + 2c b0 + (c + 1) −
c c
i=0 
f (y) − 2y
= f (a0 ) + 2 b0 + ((c + 1)n − 1) − 2n(f (y) − 2y).
c

Since f (an ) ≥ 2an = 2bn + 4y,

 
f (y) − 2y
f (a0 ) + 2 b0 + ((c + 1)n − 1) − 2n(f (y) − 2y) ≥ 2bn + 4y
c
 
f (y) − 2y f (y) − 2y
= 2 b0 + (c + 1)n − 2 ,
c c
which implies
 
f (y) − 2y f (y) − 2y
f (a0 ) + 2 ≥ 2 b0 + + 2n(f (y) − 2y),
c c
which is not true for sufficiently large n.
A contradiction is reached, and thus f (y) = 2y for all y > 0. It is immediate that this function
satisfies the functional equation.

7
Solution 2
After proving that f (y) ≥ 2y for all y > 0, one can define g(x) = f (x) − 2x, g : R>0 → R≥0 ,
and our goal is proving that g(x) = 0 for all x > 0. The problem is now rewritten as

g((c + 1)x + g(y) + 2y) + 2((c + 1)x + g(y) + 2y) = g(x + 2y) + 2(x + 2y) + 2cx
⇐⇒ g((c + 1)x + g(y) + 2y) + 2g(y) = g(x + 2y). (1)

This readily implies that g(x + 2y) ≥ 2g(y), which can be interpreted as z > 2y =⇒ g(z) ≥
2g(y), by plugging z = x + 2y.
Now we prove by induction that z > 2y =⇒ g(z) ≥ 2m · g(y) for any positive integer 2m. In
fact, since (c + 1)x + g(y) + 2y > 2y, g((c + 1)x + g(y) + 2y) ≥ 2m · g(y), and by (??),

g(x + 2y) ≥ 2m · g(y) + 2g(y) = 2(m + 1)g(y),

and we are done by plugging z = x + 2y again.

The problem now is done: if g(y) > 0 for some y > 0, choose a fixed z > 2y arbitrarily and
g(z)
and integer m such that m > 2g(y) . Then g(z) < 2m · g(y), contradiction.

8
Problem 5
There are n line segments on the plane, no three intersecting at a point, and each pair inter-
secting once in their respective interiors. Tony and his 2n − 1 friends each stand at a distinct
endpoint of a line segment. Tony wishes to send Christmas presents to each of his friends as
follows:
First, he chooses an endpoint of each segment as a “sink”. Then he places the present at the
endpoint of the segment he is at. The present moves as follows:

ˆ If it is on a line segment, it moves towards the sink.

ˆ When it reaches an intersection of two segments, it changes the line segment it travels on
and starts moving towards the new sink.

If the present reaches an endpoint, the friend on that endpoint can receive their present. Prove
Tony can send presents to exactly n of his 2n − 1 friends.
Solution 1
Draw a circle that encloses all the intersection points between line segments and extend all
line segments until they meet the circle, and then move Tony and all his friends to the circle.
Number the intersection points with the circle from 1 to 2n anticlockwise, starting from Tony
(Tony has number 1). We will prove that the friends eligible to receive presents are the ones
on even-numbered intersection points.
First part: at most n friends can receive a present.
The solution relies on a well-known result: the n lines determine regions inside the circle; then
it is possible to paint the regions with two colors such that no regions with a common (line)
boundary have the same color. The proof is an induction on n: the fact immediately holds for
n = 0, and the induction step consists on taking away one line `, painting the regions obtained
with n − 1 lines, drawing ` again and flipping all colors on exactly one half plane determined
by `.
Now consider the line starting on point 1. Color the regions in red and blue such that neigh-
boring regions have different colors, and such that the two regions that have point 1 as a vertex
are red on the right and blue on the left, from Tony’s point of view. Finally, assign to each
red region the clockwise direction and to each blue region the anticlockwise direction. Because
of the coloring, every boundary will have two directions assigned, but the directions are the
same since every boundary divides regions of different colors. Then the present will follow the
directions assigned to the regions: it certainly does for both regions in the beginning, and when
the present reaches an intersection it will keep bordering one of the two regions it was dividing.
To finish this part of the problem, consider the regions that share a boundary with the circle.
The directions alternate between outcoming and incoming, starting from 1 (outcoming), so all
even-numbered vertices are directed as incoming and are the only ones able to receive presents.
Second part: all even-numbered vertices can receive a present.
First notice that, since every two chords intersect, every chord separates the endpoints of each
of the other n − 1 chords. Therefore, there are n − 1 vertices on each side of every chord, and
each chord connects vertices k and k + n, 1 ≤ k ≤ n.
We prove a stronger result by induction in n: let k be an integer, 1 ≤ k ≤ n. Direct each
chord from i to i + n if 1 ≤ i ≤ k and from i + n to i otherwise; in other words, the sinks are
k + 1, k + 2, . . ., k + n. Now suppose that each chord sends a present, starting from the vertex
opposite to each sink, and all presents move with the same rules. Then k − i sends a present
to k + i + 1, i = 0, 1, . . . , n − 1 (indices taken modulo 2n). In particular, for i = k − 1, Tony,
in vertex 1, send a present to vertex 2k. Also, the n paths the presents make do not cross (but
they may touch.) More formally, for all i, 1 ≤ i ≤ n, if one path takes a present from k − i
to k + i + 1, separating the circle into two regions, all paths taking a present from k − j to
k + j + 1, j < i, are completely contained in one region, and all paths taking a present from

9
k − j to k + j + 1, j > i, are completely contained in the other region. For instance, possible1
paths for k = 3 and n = 5 follow:

10 1

9 2

8 3

7 4
6 5

The result is true for n = 1. Let n > 1 and assume the result is true for less chords. Consider
the chord that takes k to k + n and remove it. Apply the induction hypothesis to the remaining
n − 1 lines: after relabeling, presents would go from k − i to k + i + 2, 1 ≤ i ≤ n − 1 if the
chord were not there.
Reintroduce the chord that takes k to k+n. From the induction hypothesis, the chord intersects
the paths of the presents in the following order: the i-th path the chord intersects is the the
one that takes k − i to k + i, i = 1, 2, . . . , n − 1.

k+n k+n
k−n+1 k+n−1 k−n+1 k+n−1

.. ..
. .

k−3 k+3 k−3 k+3

k−2 k+2 k−2 k+2

k−1 k+1 k−1 k+1

k k
Paths without chord k → k + n Corrected paths with chord k → k + n

Then the presents cover the following new paths: the present from k will leave its chord and
take the path towards k + 1; then, for i = 1, 2, . . . , n − 1, the present from k − i will meet the
chord from k to k + n, move towards the intersection with the path towards k + i + 1 and go to
k + i + 1, as desired. Notice that the paths still do not cross. The induction (and the solution)
is now complete.
Solution 2
First part: at most n friends can receive a present.
Similarly to the first solution, consider a circle that encompasses all line segments, extend the
lines, and use the endpoints of the chords instead of the line segments, and prove that each
chord connects vertices k and k + n. We also consider, even in the first part, n presents leaving
from n outcoming vertices.
First we prove that a present always goes to a sink. If it does not, then it loops; let it first
enter the loop at point P after turning from chord a to chord b. Therefore after it loops once,
1
The paths do not depend uniquely on k and n; different chord configurations and vertex labelings may
change the paths.

10
it must turn to chord b at P . But P is the intersection of a and b, so the present should turn
from chord a to chord b, which can only be done in one way – the same way it came in first.
This means that some part of chord a before the present enters the loop at P is part of the
loop, which contradicts the fact that P is the first point in the loop. So no present enters a
loop, and every present goes to a sink.

P P

a b a b
There are no loops No two paths cross

The present paths also do not cross: in fact, every time two paths share a point P , intersection
of chords a and b, one path comes from a to b and the other path comes from b to a, and they
touch at P . This implies the following sequence of facts:

ˆ Every path divides the circle into two regions with paths connecting vertices within each
region.

ˆ All n presents will be delivered to n different persons; that is, all sinks receive a present.
This implies that every vertex is an endpoint of a path.

ˆ The number of chord endpoints inside each region is even, because they are connected
within their own region.

Now consider the path starting at vertex 1, with Tony. It divides the circle into two regions
with an even number of vertices in their interior. Then there is an even number of vertices
between Tony and the recipient of his present, that is, their vertex is an even numbered one.
Second part: all even-numbered vertices can receive a present.
The construction is the same as the in the previous solution: direct each chord from i to i + n
if 1 ≤ i ≤ k and from i + n to i otherwise; in other words, the sinks are k + 1, k + 2, . . ., k + n.
Then, since the paths do not cross, k will send a present to k + 1, k − 1 will send a present to
k + 2, and so on, until 1 sends a present to (k + 1) + (k − 1) = 2k.

11