Solutions for October

640. Suppose that n ≥ 2 and that, for 1 ≤ i ≤ n, we have that xi ≥ −2 and all the xi are nonzero with the
same sign. Prove that

(1 + x1 )(1 + x2 ) · · · (1 + xn ) > 1 + x1 + x2 + · · · + xn ,

Solution 1. When n = 2, we have that

(1 + x1 )(1 + x2 ) = 1 + x1 + x2 + x1 x2 > 1 + x1 + x2

since x1 and x2 are nonzero with the same sign. Suppose, as an induction hypothesis, that the result holds
for n = k ≥ 2. Then

(1 + x1 )(x + x2 ) · · · (1 + xk )(1 + xk+1 ) − (1 + x1 + x2 + · · · + xk + xk+1 )

= [(1 + x1 )(1 + x2 ) · · · (1 + xk ) − (1 + x1 + x2 + · · · + xk )]
+ xk+1 [(1 + x1 )(1 + x2 ) · · · (1 + xk ) − 1]
> xk+1 [(1 + x1 )(1 + x2 ) · · · (1 + xk ) − 1] ≡ A .

If xi > 0 (1 ≤ i ≤ k + 1), then 1 + xi > 1 (1 ≤ i ≤ k) and A > 0.

Let −2 ≤ xi < 0. Then, for 1 ≤ i ≤ k,

−1 ≤ 1 + xi < 1 =⇒ −1 ≤ (1 + x1 )(1 + x2 ) · · · (1 + xk ) ≤ 1

=⇒ (1 + x1 )(1 + x2 ) · · · (1 + xk ) − 1 ≤ 0 .
Since also xk+1 < 0, A ≥ 0. Hence

(1 + x1 )(1 + x2 ) · · · (1 + xk+1 ) > 1 + x1 + x2 + · · · + xk+1 .

The result follows by induction.

Solution 2. The case n = 2 is proved as in the first solution. Suppose that all xi are negative and at
least two, say x1 and x2 lie in [−2, −1]. Then

(1 + x1 )(1 + x2 ) · · · (1 + xn ) ≥ −1 ≥ 1 − 1 − 1 ≥ 1 + x1 + x2 + · · · + xn

since −2 ≤ xi < 0 and |1 + xi | ≤ 1 for 1 ≤ i ≤ n.

Henceforth assume that either (i) all xi are positive (1 ≤ i ≤ n) or (ii) all xi are negative with
−2 ≤ x1 < 0 and −1 < xi < 0 for 2 ≤ i ≤ n. As an induction hypothesis, assume that the result holds for
n = k ≥ 2. Then 1 + xk+1 > 0, so that

(1 + x1 )(1 + x2 ) · · · (1 + xk )(1 + xk+1 )

> (1 + x1 + x2 + · · · + xk )(1 + xk+1 ) by the induction hypothesis
> 1 + x1 + x2 + · · · + xk + xk+1 by the n = 2 case.

The result follows by induction.

641. Observe that x2 + 5x + 6 = (x + 2)(x + 3) while x2 + 5x − 6 = (x + 6)(x − 1). Determine infinitely many
coprime pairs (m, n) of positive integers for which both x2 + mx + n and x2 + mx − n can be factored
as a product of linear polynomials with integer coefficients.

1
 Solution 1. For the factorizations to occur, both discriminants must be squares: m2 − 4n = u2 ,
m +4n = v 2 for some integers u and v. Suppose m2 can be expressed as the sum of two squares: m2 = p2 +q 2 .
2

Then 2m2 = (p + q)2 + (p − q)2 . Write u = p − q, v = p + q. Then 8n = v 2 − u2 = 4pq so that n = 21 pq.

Now we construct our examples. Let r and s be a coprime pair of integers with opposite parity. Define
p = r2 − s2 , q = 2rs, m = r2 + s2 and n = rs(r2 − s2 ). Then any prime power divisor of m and n must
divide both r2 + s2 and one of r, s and r2 − s2 , and hence both 2r2 and 2s2 . Hence it must divide 2. But
we have arranged for m to be odd. Hence m and n are coprime. Observe that

x2 + (r2 + s2 )x + rs(r2 − s2 ) = (x + s(r + s))(x + r(r − s))

and
x2 + (r2 + s2 )x − rs(r2 − s2 ) = (x + r(r + s))(x − s(r − s)) .

Solution 2. With the notation of the first solution, we have that m2 − u2 = v 2 − m2 , whence v 2 − 2m2 =
−u . Let us take u = 1. We show that v 2 − 2m2 = −1 has infinitely many solutions with m odd. Let
2

(v, m) = (vk , mk ) where

√ √ √
(v1 , m1 ) = (1, 1) and vk+1 + mk+1 2 = (3 + 2 2)(vk + mk 2)

so
vk+1 = 3vk + 4mk mk+1 = 2vk + 3mk
for k ≥ 1. By induction, it is proved that, for each k, vk2 − 2m2k = −1. Let (m, n) = (mk , 14 (m2k − 1)). Then
it is readily shown that (m, n) are both integers and satisfy the condition of the problem. For example, we
have
(u, v; m, n) = (1, 1; 1, 0), (1, 7; 5, 6), (1, 41; 29, 210), · · ·
so that, for example, x2 + 29x + 210 = (x + 14)(x + 15) and x2 + 29x − 210 = (x + 35)(x − 6).

Solution 3. [J. Rickards, M. Boase] Let a be even and let (m, n) = (a2 + 1, a3 − a). Then the greatest
common divisor of m and a is 1, as is the greatest common divisor of m and a2 − 1. Then

x2 + (a2 + 1)x + (a3 − a) = (x + a2 − a)(x + a + 1)

and
x2 + (a2 + 1)x − (a3 − a) = (x + a2 + a)(x − a − 1) .

Comment. This is a special case of Solution 1.

Solution 4. [S. Hemmati] Let k be an integer and let

m = 4k 2 + 1 = (2k + 1)2 − 4k = (2k − 1)2 + 4k

and n = 2k(2k + 1)(2k − 1). The three factors of n are pairwise coprime, and it follows that the greatest
common divisor of m and n is 1. We have that

x2 + mx − n = [x + 2k(2k + 1)][x − (2k − 1)]

and
x2 + mx + n = [x + 2k(2k − 1)][x + (2k + 1)] .

Solution 5. [C. Deng] Suppose that x2 + mx − n has roots a and −b and that x2 + mx + n has roots r
and s. Then n = ab = rs and m = b − a = −r − s. In terms of a and b, the values of r and s are given by
√
a − b ± a2 − 6ab + b2
.
2

2
Since a − b and a2 − 6ab + b2 have the same parity, these are integers if and only if a2 − 6ab + b2 is a square.
Any values of a and b which make this quantity square will yield acceptable values of m and n.
Let (a1 , b1 ) = (1, 6), and for k ≥ 1,

ak+1 = 6ak − bk , bk+1 = ak .

Then
a2k+1 − 6ak+1 bk+1 + b2k+1 = (6ak − bk )2 − 6(6ak − bk )ak + a2k = a2k − 6ak bk + b2k ,
so that, by induction, we see that this quantity is equal to 1 for all k ≥ 1. Thus
 
ak − bk − 1) ak − bk + 1
(rk , sk ) = , .
2 2

Observe that the greatest common divisor of ak+1 and bk+1 is equal to that of ak and bk , and so, by
induction, equal to 1, the greatest common divisor of 1 and 6. It follows, for all k, that ak bk and ak − bk are
relativeoly prime. Thus, the pair

(x2 + (bk − ak )x − ak bk , x2 + (bk − ak )x + ak bk )

satisfy the desired conditions for k ≥ 1.

In particular, we find that

x2 + 5x − 6 = (x + 6)(x − 1) , x2 + 5x + 6 = (x + 2)(x + 3) ;

x2 + 29x − 210 = (x + 35)(x − 6) , x2 + 29x + 210 = (x + 14)(x + 15) ;

x2 + 169x − 7140 = (x + 204)(x − 35) , x2 + 169x + 7140 = (x + 84)(x + 85) .

Solution 5. [K. Zhou] Suppose that x2 + mx − n has integer roots −a and −b and that x2 + mx + n has
an integer root c. Then
x2 + mx − n = (x + a)(x + b)
so that m = a + b and n = −ab¿ The two roots of the polynomial x2 + mx + n are −c and c − m, where
−ab = n = c(a + b − c). Therefore a(b + c0 = c2 − bc so that

2b2
a = c − 2b + .
b+c

Thus, b + c must divide 2b2 as all the other terms in the equation are integers.
To construct our examples, let a, b, c be chosen so that a and b are integers, b+c = 1 and a = c−2b+2b2 .
Then c is an integer and

c=1−b , a = 1 − 3b + 2b2 = (1 − b)(1 − 2b) .

Therefore, let
m = a + b = 1 − 2b + 2b2 = (1 − b)2 + b2
= (1 − b) + b(2b − 1)
and
n = −ab = −b(1 − b)(1 − 2b) .
Suppose, if possible, that some prime p divides both m and n. From the factorization of n, it follows that
p divides one of b, 1 − b and 1 − 2b, and from the expressions for m, we see that it must divide all three of

3
 these numbers. But this is impossible, as b and 1 − b are coprime. Therefore, for all integers b, m and n are
coprime.
We verify that these values of m and

x2 + (1 − 2b + b2 )x + b(b − 1)(2b − 1) = (x + b)(x + (b − 1)(2b − 1)) ;

x2 + (1 − 2b + b2 )x − b(b − 1)(2b − 1) = (x − b + 1)(x + b(2b − 1) .

642. In a convex polyhedron, each vertex is the endpoint of exactly three edges and each face is a concyclic
polygon. Prove that the polyhedron can be inscribed in a sphere.

Solution. Let us begin with a couple of preliminary observations. Since three edges are incident with
each vertex, exactly three faces of the polyhedron meet at each vertex. The centre of the circumscribing
circle of any face is the point common to the right bisectors of the edges. The planes that right bisect the
edges of a face intersect in a line perpendicular to the face, and this line is the locus of the centres of spheres
which contain all the vertices of the face. Finally, any two vertices of the polyhedron can be joined by a path
of edges of the polyhedron.
Any two adjacent faces of the polyhedron are inscribed in a unique sphere. Let the edge AB be common
to two faces α and β which have respective circumcentres P and Q. The respective lines m and n to these
faces through their circumcentres are non-parallel lines on the plane right-bisecting AB and so intersect in
a unique point. This point is the centre of the only sphere that contains all of the vertices of α and β.
The three faces meeting at any vertex are contained in the same sphere. Suppose that vertex A belongs
to the edges AB, AC and AD. The right bisecting planes of the edges AB and AC meet in a line through
the centre of and perpendicular to the circumcircle of ABC. The right bisecting plane of AD is not parallel
to this line and does not contain it, and so meets it in a single point. This point, lying on the perpendicular
to each of the three faces adjacent to A and passing through their circumcentres is equidistance from all the
vertices of these faces and so is the centre of a sphere containing these faces.

There is a circumscribing sphere for the polyhedron. Suppose this is false. Then there must be two
vertices for which the spheres circumscribing the faces about the vertices differ. Join the two vertices by
a path of edges. For one of the edges, say RS, the sphere circumscribing the faces meeting at R must be
different from the sphere circumscribing the faces meeting at S. But then this means that the two faces
adjacent to RS must be circumscribed by two separate spheres, contrary to what was shown above. Hence
the desired result follows.

643. Let n2 distinct integers be arranged in an n × n square array (n ≥ 2). Show that it is possible to select n
numbers, one from each row and column, such that if the number selected from any row is greater than
another number in this row, then this latter number is less than the number selected from its column.

Solution. We proceed in a number of rounds. In Round 1, select the least element in each row. If each
column has one such number, we stop; otherwise, deselect in any column all but the largest of the selected
numbers. Any row that does not contain a selected number, we call free. In each subsequent round, pick the
least element not yet tried from each free row, and then deselect all but the biggest number in each column.
Since any row can be freed at most n − 1 times, there are at most n(n − 1) + 1 rounds. In the final round,
each column must have exactly one element.

Example:

6 5 11 6 5 11 6 5 11
4 2 3 → 4 2 3 → 4 2 3
7 10 1 7 10 1 7 10 1

4
 Suppose, wolog (by shuffling the columns if necessary), that the entries a11 , a22 , · · · , ann are selected
from the array (aij ). If aik < aii , then this number must have been an earlier possible selection and was
rejected in favour of a larger number in its column. Hence aik < akk .

Comment: There is a dual procedure taking the largest element of each column and rejecting all but
the smallest selected number in each row.

644. Given a point P , a line L and a circle C, construct with straightedge and compasses an equilateral
triangle P QR with one vertex at P , another vertex Q on L and the third vertex R on C.

Solution 1. Analysis. Suppose that we have the required triangle P QR with Q ∈ L and R ∈ C. Then
a 60◦ rotation with centre P takes C to a circle C0 and R to the point lying on the intersection of C0 and L.
Accordingly, we need to construct a rotated image C0 of C and, if this intersects L, then we can construct
the triangle.
Construction. Let O be the centre of C. Construct an equilateral triangle P OO0 and with centre O0
construct a circle C0 with radius equal to that of C. If this circle C0 intersects L at R, then there are two
constructible points which with P and R are the vertices of an equilateral triangle; one of them Q will lie
on C.
Proof. The circle C0 is the image of C under a 60◦ rotation with centre P that carries O to O0 . The
point R lies on C0 so its inverse image Q under the rotation lies on C. Since P Q = P R and 6 P = 60◦ , P QR
is an equilateral triangle.
Comment. There are two possible images of C yielding up to four possibilities for R. However, it is also
possible that neither images intersects L and the construction is not possible.

645. Let n ≥ 3 be a positive integer. Are there n positive integers a1 , a2 , · · · , an not all the same such that
for each i with 3 ≤ i ≤ n we have

ai + Si = (ai , Si ) + [ai , Si ] .

where Si = a1 + a2 + · · · + ai , and where (·, ·) and [·, ·] represent the greatest common divisor and least
common multiple respectively?

Solution 1. Letting bi = (ai , Si ), we find that

ai Si ai Si
[ai , Si ] = = .
(ai , Si ) bi
The given condition is equivalent to ai + Si = bi + (ai Si /bi ), which is equivalent to

0 = b2i − (ai + Si )bi + ai Si = (bi − ai )(bi − Si ) .

We can achieve the condition by making ai = (ai , Si ) and Si = [ai , Si ]. Let a1 = a2 = 1, ai = 2i−2 for i ≥ 3.
Then
Xi
Si = 1 + 2j−2 = 1 + (2i−1 − 1) = 2i−1
j=2

=⇒ (ai , Si ) = 2i−2 , [ai , Si ] = 2i−1

for i ≥ 3.

Solution 2. Let ai = 1, a2 = 2 and ai = 3 · 2i−3 for i ≥ 3. Then

i−3
X
Si = 1 + 2 + 3 2j = 1 + 2 + 3(2i−2 − 1) = 3 · 2i−2
j=0

5
 =⇒ (ai , Si ) = 3 · 2i−3 , [ai , Si ] = 3 · 2i−2
for i ≥ 3.

Solution 3. [K. Purbhoo] Choose a1 at will, and let ai = Si−1 for i ≥ 2. Then Si = Si−1 + ai = 2ai ,
ai + Si = 3ai , (ai , Si ) = ai and [ai , Si ] = 2ai for i ≥ 2.

Solution 4. [K. Yeats] Let a1 = 1, a2 = 3 and an = 2n−1 for n ≥ 3. Then Sn = 2n for n ≥ 2 and, for
each i with 3 ≤ i ≤ n, (ai , Si ) = 2i−1 and [ai , Si ] = 2i .

646. Let ABC be a triangle with incentre I. Let AI meet BC at L, and let X be the contact point of the
incircle with the line BC. If D is the reflection of L on X, we construct B 0 and C 0 as the reflections of
D with respect to the lines BI and CI, respectively. Show that the quadrailateral BCC 0 B 0 is cyclic.

Solution 1. Without loss of generality, we may assume that AC ≥ AB. Observe that B 0 lies on the side
AB and C 0 lies on the side AC. We use the conventional notation for the sides a, b, c of the triangle and
2s = a + b + c for the permimeter. Let Z and Y be the tangent points of the incircle with sides AB and AC
respectively. Observe that IX ⊥ BC, IY ⊥ AC and IZ ⊥ AB.
We have that XL = XD = ZB 0 = Y C 0 ,

|XC| = s − c , |AY | = |AZ| = s − a ;

ab
|LC| = .
b+c
Therefore
ab
|XL| = s − c − ,
b+c
|AB 0 | = |AZ| + |ZB|
ab ab
=s−a+s−c− =b−
b+c b+c
 
a
=b 1− ;
b+c
and
|AC 0 | = |AY | − |Y C 0 |
ab
=s−a−s+c+
b+c
−ab + bc − ac + c2 + ab
=
b+c
   
b+c−a a
=c =c 1− .
b+c b+c

Therefore
AC 0 : AB 0 = c : b = AB : AC
so that triangles ABC and AC 0 B 0 are similar and 6 ABC = 6 AC 0 B 0 , 6 ACB = 6 AB 0 C 0 . Therefore the
quadrilateral BCC 0 B 0 is concyclic.

Solution 2. [S. Sun] Suppose that AC ≥ AB. Use the same notation as in Solution 1, and let t = |BL|.
Then |ZB 0 | = |Y C 0 | = |DX| = |XL| = t − (s − b). We have that

|AB 0 | = (s − a) + t − (s − b) = t + (b − a)

and
|AC 0 | = (s − a) − t + (s − b) = c − t ,

6
whereupon
AB 0 : AC 0 = [t + (b − a)] : [c − t] = [b − (a − t)] : [c − t] .
However, as AL is an angle bisector, we have that (a − t) : t = b : c, so that

[b − (a − t) : [c − t] = b : c = AC : AB .

Therefore, triangles AC 0 B 0 and ABC are similar, and we can conclude, as in Solution 1, that BCC 0 B 0 is
concyclic.
Comment. Notice that Solutions 1 and 2 follow the same strategy, but the second solution is cleaner as
it avoid the actual computation of t and merely exploited a relationship involving this variable.

Solution 3. [A. Murali] We again assume that AC ≥ AB and use the notation of Solution 1. We first
show that AB 0 IC 0 is concyclic. Observe that 6 ZB 0 I = 6 LD0 I = 6 Y C 0 I, so that triangles IB 0 Z and IC 0 Y
are similar and 6 ZIB 0 = 6 Y IC 0 . Thus 6 B 0 AC 0 = 180◦ − 6 ZIY = 180◦ − 6 B 0 IC 0 and AB 0 IC 0 is concyclc.
It follows that 6 B 0 C 0 I = 6 BAI = 12 6 BAC = 6 LAC.
We have that
6 CC 0 I = 6 IDC = 6 ILB = 6 LAC + 6 ACL ,
whence

6 CC 0 B 0 = 6 CC 0 I + 6 B 0 C 0 I = (6 LAC + 6 ACL) + 6 LAC = 6 ACB + 6 BAC = 180◦ − 6 ABC .

Therefore, BCC 0 B 0 is concyclic.