EGMO 2016, Day 1 – Solutions

Problem 1. Let n be an odd positive integer, and let x1 , x2 , . . ., xn be

non-negative real numbers. Show that

min (x2i + x2i+1 ) ≤ max (2xj xj+1 ),

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

where xn+1 = x1 .

Solution. In what follows, indices are reduced modulo n. Consider the n

differences xk+1 −xk , k = 1, . . . , n. Since n is odd, there exists an index j such
that (xj+1 − xj )(xj+2 − xj+1 ) ≥ 0. Without loss of generality, we may and
will assume both factors non-negative, so xj ≤ xj+1 ≤ xj+2 . Consequently,

min (x2k + x2k+1 ) ≤ x2j + x2j+1 ≤ 2x2j+1 ≤ 2xj+1 xj+2 ≤ max (2xk xk+1 ).
k=1,...,n k=1,...,n

Remark. If n ≥ 3 is odd, and one of the xk is negative, then the conclusion

may no longer hold. This is the case if, for instance, x1 = −b, and x2k = a,
x2k+1 = b, k = 1, . . . , (n − 1)/2, where 0 ≤ a < b, so the string of numbers is

−b, b, a, b, a, . . . , b, a.

If n is even, the conclusion may again no longer hold, as shown by any

string of alternate real numbers: a, b, a, b, . . . , a, b, where a 6= b.

Problem 2. Let ABCD be a cyclic quadrilateral, and let diagonals AC and

BD intersect at X. Let C1 , D1 and M be the midpoints of segments CX,
DX and CD, respectively. Lines AD1 and BC1 intersect at Y , and line M Y
intersects diagonals AC and BD at different points E and F , respectively.
Prove that line XY is tangent to the circle through E, F and X.
Y C

M
C1
D
E
D1
X
F

A B
Solution. We are to prove that ∠EXY = ∠EF X; alternatively, but equi-
valently, ∠AY X + ∠XAY = ∠BY F + ∠XBY .
Since the quadrangle ABCD is cyclic, the triangles XAD and XBC are
similar, and since AD1 and BC1 are corresponding medians in these triangles,
it follows that ∠XAY = ∠XAD1 = ∠XBC1 = ∠XBY .
Finally, ∠AY X = ∠BY F , since X and M are corresponding points in the
similar triangles ABY and C1 D1 Y : indeed, ∠XAB = ∠XDC = ∠M C1 D1 ,
and ∠XBA = ∠XCD = ∠M D1 C1 .

Problem 3. Let m be a positive integer. Consider a 4m × 4m array of

square unit cells. Two different cells are related to each other if they are in
either the same row or in the same column. No cell is related to itself. Some
cells are coloured blue, such that every cell is related to at least two blue
cells. Determine the minimum number of blue cells.

Solution 1 (Israel). The required minimum is 6m and is achieved by a

diagonal string of m 4 × 4 blocks of the form below (bullets mark centres of
blue cells):
•
•
•
• • •
In particular, this configuration shows that the required minimum does not
exceed 6m.
We now show that any configuration of blue cells satisfying the condition
in the statement has cardinality at least 6m.
Fix such a configuration and let mr1 be the number of blue cells in rows
containing exactly one such, let mr2 be the number of blue cells in rows
containing exactly two such, and let mr3 be the number of blue cells in rows
containing at least three such; the numbers mc1 , mc2 and mc3 are defined
similarly.
Begin by noticing that mc3 ≥ mr1 and, similarly, mr3 ≥ mc1 . Indeed, if a
blue cell is alone in its row, respectively column, then there are at least two
other blue cells in its column, respectively row, and the claim follows.
Suppose now, if possible, the total number of blue cells is less than 6m.
We will show that mr1 > mr3 and mc1 > mc3 , and reach a contradiction by the
preceding: mr1 > mr3 ≥ mc1 > mc3 ≥ mr1 .
We prove the first inequality; the other one is dealt with similarly. To this
end, notice that there are no empty rows — otherwise, each column would
contain at least two blue cells, whence a total of at least 8m > 6m blue cells,
which is a contradiction. Next, count rows to get mr1 + mr2 /2 + mr3 /3 ≥ 4m,

2
and count blue cells to get mr1 + mr2 + mr3 < 6m. Subtraction of the latter
from the former multiplied by 3/2 yields mr1 − mr3 > mr2 /2 ≥ 0, and the
conclusion follows.

Solution 2. To prove that a minimal configuration of blue cells satisfying

the condition in the statement has cardinality at least 6m, consider a bipar-
tite graph whose vertex parts are the rows and the columns of the array,
respectively, a row and a column being joined by an edge if and only if the
two cross at a blue cell. Clearly, the number of blue cells is equal to the num-
ber of edges of this graph, and the relationship condition in the statement
reads: for every row r and every column c, deg r + deg c − (r, c) ≥ 2, where
(r, c) = 2 if r and c are joined by an edge, and (r, c) = 0 otherwise.
Notice that there are no empty rows/columns, so the graph has no isolated
vertices. By the preceding, the cardinality of every connected component
of the graph is at least 4, so there are at most 2 · 4m/4 = 2m such and,
consequently, the graph has at least 8m − 2m = 6m edges. This completes
the proof.

Remarks. The argument in the first solution shows that equality to 6m is

possible only if mr1 = mr3 = mc1 = mc3 = 3m, mr2 = mc2 = 0, and there are no
rows, respectively columns, containing four blue cells or more.
Consider the same problem for an n×n array. The argument in the second
solution shows that the corresponding minimum is 3n/2 if n is divisible by
4, and 3n/2 + 1/2 if n is odd; if n ≡ 2 (mod 4), the minimum in question is
3n/2 + 1. To describe corresponding minimal configurations Cn , refer to the
minimal configurations C2 , C3 , C4 , C5 below:

•
• •
• • •
• • • • •
• • • • • • • • • • • •

The case n ≡ 0 (mod 4) was dealt with above: a Cn consists of a diagonal

string of n/4 blocks C4 . If n ≡ r (mod 4), r = 2, 3, a Cn consists of a diagonal
string of bn/4c blocks C4 followed by a Cr , and if n ≡ 1 (mod 4), a Cn consists
of a diagonal string of bn/4c − 1 blocks C4 followed by a C5 .
Minimal configurations are not necessarily unique (two configurations be-
ing equivalent if one is obtained from the other by permuting the rows and/or
the columns). For instance, if n = 6, the configurations below are both min-
imal:

3
 • • •
• • •
• • • •
• •
• •
• • • • • •

4
 EGMO 2016, Day 2 – Solutions

Problem 4. Two circles, ω1 and ω2 , of equal radius intersect at different

points X1 and X2 . Consider a circle ω externally tangent to ω1 at a point T1 ,
and internally tangent to ω2 at a point T2 . Prove that lines X1 T1 and X2 T2
intersect at a point lying on ω.

Solution 1. Let the line Xk Tk and ω meet again at Xk0 , k = 1, 2, and notice
that the tangent tk to ωk at Xk and the tangent t0k to ω at Xk0 are parallel.
Since the ωk have equal radii, the tk are parallel, so the t0k are parallel, and
consequently the points X10 and X20 coincide (they are not antipodal, since
they both lie on the same side of the line T1 T2 ). The conclusion follows.

Solution 2. The circle ω is the image of ωk under a homothety hk centred

at Tk , k = 1, 2. The tangent to ω at Xk0 = hk (Xk ) is therefore parallel to the
tangent tk to ωk at Xk . Since the ωk have equal radii, the tk are parallel, so
X10 = X20 ; and since the points Xk , Tk and Xk0 are collinear, the conclusion
follows.

1 t1 2 X1
X1
T2
2
T1 T2
t2
 X2 Y 
X2 T1 1

Solution 3. Invert from X1 and use an asterisk to denote images under this
inversion. Notice that ωk∗ is the tangent from X2∗ to ω ∗ at Tk∗ , and the pole
X1 lies on the bisectrix of the angle formed by the ωk∗ , not containing ω ∗ .
Letting X1 T1∗ and ω ∗ meet again at Y , standard angle chase shows that Y
lies on the circle X1 X2∗ T2∗ , and the conclusion follows.

Remarks. The product h1 h2 of the two homotheties in the first solution

is reflexion across the midpoint of the segment X1 X2 , which lies on the line
T1 T2 .
Various arguments, involving similarities, radical axes, and the like, work
equally well to prove the required result.

Problem 5. Let k and n be integers such that k ≥ 2 and k ≤ n ≤ 2k − 1.

Place rectangular tiles, each of size 1 × k or k × 1, on an n × n chessboard so
that each tile covers exactly k cells, and no two tiles overlap. Do this until
no further tile can be placed in this way. For each such k and n, determine
the minimum number of tiles that such an arrangement may contain.

Solution. The required minimum is n if n = k, and it is min(n, 2n − 2k + 2)

if k < n < 2k.
The case n = k being clear, assume henceforth k < n < 2k. Begin
by describing maximal arrangements on the board [0, n] × [0, n], having the
above mentioned cardinalities.
If k < n < 2k − 1, then min(n, 2n − 2k + 2) = 2n − 2k + 2. To obtain
a maximal arrangement of this cardinality, place four tiles, [0, k] × [0, 1],
[0, 1] × [1, k + 1], [1, k + 1] × [k, k + 1] and [k, k + 1] × [0, k] in the square
[0, k]×[0, k], stack n−k−1 horizontal tiles in the rectangle [1, k+1]×[k+1, n],
and erect n − k − 1 vertical tiles in the rectangle [k + 1, n] × [1, k + 1].
If n = 2k − 1, then min(n, 2n − 2k + 2) = n = 2k − 1. A maximal
arrangement of 2k − 1 tiles is obtained by stacking k − 1 horizontal tiles in
the rectangle [0, k] × [0, k − 1], another k − 1 horizontal tiles in the rectangle
[0, k] × [k, 2k − 1], and adding the horizontal tile [k − 1, 2k − 1] × [k − 1, k].
The above examples show that the required minimum does not exceed
the mentioned values.
To prove the reverse inequality, consider a maximal arrangement and let
r, respectively c, be the number of rows, respectively columns, not containing
a tile.
If r = 0 or c = 0, the arrangement clearly contains at least n tiles.
If r and c are both positive, we show that the arrangement contains at
least 2n − 2k + 2 tiles. To this end, we will prove that the rows, respectively
columns, not containing a tile are consecutive. Assume this for the moment,
to notice that these r rows and c columns cross to form an r × c rectangular
array containing no tile at all, so r < k and c < k by maximality. Conse-
quently, there are n − r ≥ n − k + 1 rows containing at least one horizontal
tile each, and n − c ≥ n − k + 1 columns containing at least one vertical tile
each, whence a total of at least 2n − 2k + 2 tiles.
We now show that the rows not containing a tile are consecutive; columns
are dealt with similarly. Consider a horizontal tile T . Since n < 2k, the
nearest horizontal side of the board is at most k − 1 rows away from the row
containing T . These rows, if any, cross the k columns T crosses to form a
rectangular array no vertical tile fits in. Maximality forces each of these rows
to contain a horizontal tile and the claim follows.
Consequently, the cardinality of every maximal arrangement is at least
min(n, 2n − 2k + 2), and the conclusion follows.

Remarks. (1) If k ≥ 3 and n = 2k, the minimum is n + 1 = 2k + 1

2
and is achieved, for instance, by the maximal arrangement consisting of the
vertical tile [0, 1] × [1, k + 1] along with k − 1 horizontal tiles stacked in
[1, k+1]×[0, k−1], another k−1 horizontal tiles stacked in [1, k+1]×[k+1, 2k],
and two horizontal tiles stacked in [k, 2k] × [k − 1, k + 1]. This example shows
that the corresponding minimum does not exceed n + 1 < 2n − 2k + 2. The
argument in the solution also applies to the case n = 2k to infer that for a
maximal arrangement of minimal cardinality either r = 0 or c = 0, and the
cardinality is at least n. Clearly, we may and will assume r = 0. Suppose,
if possible, such an arrangement contains exactly n tiles. Then each row
contains exactly one tile, and there are no vertical tiles. Since there is no
room left for an additional tile, some tile T must cover a cell of the leftmost
column, so it covers the k leftmost cells along its row, and there is then room
for another tile along that row — a contradiction.
(2) For every pair (r, c) of integers in the range 2k − n, . . ., k − 1, at least
one of which is positive, say c > 0, there exists a maximal arrangement of
cardinality 2n − r − c.
Use again the board [0, n] × [0, n] to stack k − r horizontal tiles in each of
the rectangles [0, k]×[0, k−r] and [k−c, 2k−c]×[k, 2k−r], erect k−c vertical
tiles in each of the rectangles [0, k − c] × [k − r, 2k − r] and [k, 2k − c] × [0, k],
then stack n−2k +r horizontal tiles in the rectangle [k −c, 2k −c]×[2k −r, n],
and erect n − 2k + c vertical tiles in the rectangle [2k − c, n] × [1, k + 1].

Problem 6. Let S be the set of all positive integers n such that n4 has a
divisor in the range n2 + 1, n2 + 2, . . ., n2 + 2n. Prove that there are infinitely
many elements of S of each of the forms 7m, 7m + 1, 7m + 2, 7m + 5, 7m + 6
and no elements of S of the form 7m + 3 or 7m + 4, where m is an integer.

Solution. The conclusion is a consequence of the lemma below which actu-

ally provides a recursive description of S. The proof of the lemma is at the
end of the solution.
Lemma. The fourth power of a positive integer n has a divisor in the range
n2 + 1, n2 + 2, . . ., n2 + 2n if and only if at least one of the numbers 2n2 + 1
and 12n2 + 9 is a perfect square.
Consequently, a positive integer n is a member of S if and only if m2 −
2n = 1 or m2 − 12n2 = 9 for some positive integer m.
2

The former is a Pell equation whose solutions are (m1 , n1 ) = (3, 2) and

(mk+1 , nk+1 ) = (3mk + 4nk , 2mk + 3nk ), k = 1, 2, 3, . . . .

In what follows, all congruences are modulo 7. Iteration shows that

(mk+3 , nk+3 ) ≡ (mk , nk ). Since (m1 , n1 ) ≡ (3, 2), (m2 , n2 ) ≡ (3, −2), and

3
(m3 , n3 ) ≡ (1, 0), it follows that S contains infinitely many integers from
each of the residue classes 0 and ±2 modulo 7.
The other equation is easily transformed into a Pell equation, m02 −
12n02 = 1, by noticing that m and n are both divisible by 3, say m = 3m0
and n = 3n0 . In this case, the solutions are (m1 , n1 ) = (21, 6) and

(mk+1 , nk+1 ) = (7mk + 24nk , 2mk + 7nk ), k = 1, 2, 3, . . . .

This time iteration shows that (mk+4 , nk+4 ) ≡ (mk , nk ). Since (m1 , n1 ) ≡
(0, −1), (m2 , n2 ) ≡ (−3, 0), (m3 , n3 ) ≡ (0, 1), and (m4 , n4 ) ≡ (3, 0), it follows
that S contains infinitely many integers from each of the residue classes 0
and ±1 modulo 7.
Finally, since the nk from the two sets of formulae exhaust S, by the
preceding no integer in the residue classes ±3 modulo 7 is a member of S.
We now turn to the proof of the lemma. Let n be a member of S, and
let d = n2 + m be a divisor of n4 in the range n2 + 1, n2 + 2, . . . , n2 + 2n, so
1 ≤ m ≤ 2n. Consideration of the square of n2 = d − m shows m2 divisible
by d, so m2 /d is a positive integer. Since n2 < d < (n + 1)2 , it follows that
d is not a square; in particular, m2 /d 6= 1, so m2 /d ≥ 2. On the other hand,
1 ≤ m ≤ 2n, so m2 /d = m2 /(n2 + m) ≤ 4n2 /(n2 + 1) < 4. Consequently,
m2 /d = 2 or m2 /d = 3; that is, m2 /(n2 + m) = 2 or m2 /(n2 + m) = 3. In
the former case, 2n2 + 1 = (m − 1)2 , and in the latter, 12n2 + 9 = (2m − 3)2 .
Conversely, if 2n2 + 1 = m2 for some positive integer m, then 1 < m2 <
4n , so 1 < m < 2n, and n4 = (n2 + m + 1)(n2 − m + 1), so the first factor
2

is the desired divisor.

Similarly, if 12n2 + 9 = m2 for some positive integer m, then m is odd,
n ≥ 6, and n4 = (n2 + m/2 + 3/2)(n2 − m/2 + 3/2), and again the first factor
is the desired divisor.