Problem Set 5
 25.

Let x and y be real numbers. Prove that

max
 (0, x) + 
max
 (1, x, y) = 
max
 (0, x  
max
 (1, y))+ 
max
 (1, y, 1  x, y  x) 

where max(
a,
b) is the larger of the two numbers
a and
b.
View solution
 26.

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

Suppose that n ³ 2 and that, for 1 £ i £ n,
we have that x_{i} ³ 2 and all the x_{i} are nonzero with the
same sign. Prove that
(1 + x_{1})(1 + x_{2}) ¼(1 + x_{n}) > 1 + x_{1} + x_{2} + ¼+x_{n} , 

View solution
 28.

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.
View solution
 29.

Let n^{2} 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.
View solution
 30.

Given a point P, a line L and a circle
C, construct with straightedge and compasses an
equilateral triangle PQR with one vertex at P, another vertex
Q on L and the third vertex R on C.
View solution
Solutions to Problem Set 5
25.
 25.

First solution. If 0 £ x £ 1, then
x £ 0, x  max(1, y) £ x  1 £ 0, 1  x £ 1,
y  x £ y, so that both sides are equal to max(1, y).
If x £ 0, then max(0, x) = x, max(1, x, y) = max(1, y), max(0, x  max(1, y)) = 0 and 1  x ³ 1,
y  x ³ y, so that

max
 (1, y, 1  x, y  x) = 
max
 (1  x, y  x) = 
max
 (1, y)  x 

which is the same as the left side.


Suppose that x ³ 1. Then the left side is equal to
0 + max(x, y) = max(x, y). When y £ 1, the right side
becomes (x  1) + 1 = x = max(x, y). When 1 £ y £ x, the
right side becomes x  y + y = x = max(x, y). When x £ y,
the right side is 0 + y = max(x, y). Thus, the result holds in
all cases.
26.
 26.

First solution. For the factorizations to occur,
both discriminants must be squares: m^{2}  4n = u^{2}, m^{2} + 4n = v^{2} for some integers u and v. Suppose m^{2} can be expressed
as the sum of two squares: m^{2} = p^{2} + q^{2}. Then
2m^{2} = (p + q)^{2} + (p  q)^{2}. Write u = p  q, v = p + q.
Then 8n = v^{2}  u^{2} = 4pq so that n = ^{1}/_{2}pq.


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

and
x^{2} + (r^{2} + s^{2}) x  rs(r^{2}  s^{2}) = (x + r(r + s))(x  s(r  s)) . 

 26.

Second solution.
With the notation of the first solution,
we have that m^{2}  u^{2} = v^{2}  m^{2}, whence
v^{2}  2m^{2} = u^{2}. Let us take u = 1. We show that
v^{2}  2m^{2} = 1 has infinitely many solutions with m odd.
Let (v, m) = (v_{k}, m_{k}) where
(v_{1}, m_{1}) = (1, 1) and v_{k+1} + m_{k+1}Ö2 = (3 + 2Ö2)(v_{k} + m_{k}Ö2) 

so
v_{k+1} = 3v_{k} + 4m_{k} m_{k+1} = 2v_{k} + 3m_{k} 

for
k ³ 1. By induction, it is proved that, for each
k,
v_{k}^{2}  2
m_{k}^{2} = 1. Let (
m,
n) = (
m_{k},
^{1}/
_{4}(
m_{k}^{2}  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,
x^{2} + 29
x + 210 = (
x + 14)(
x + 15)
and
x^{2} + 29
x  210 = (
x + 35)(
x  6).
 26.

Third solution. [M. Boase] Let a be even and let
(m, n) = (a^{2} + 1, a^{3}  a). Then the greatest common divisor
of m and a is 1, as is the greatest common divisor of
m and a^{2}  1. Then
x^{2} + (a^{2} + 1)x + (a^{3}  a) = (x + 
a^{2}  a

)(x + 
a+1

) 

and
x^{2} + (a^{2} + 1)x  (a^{3}  a) = (x + 
a^{2} + a

)(x  
a  1

) . 



Comment. This is a special case of the First Solution.
27.
 27.

First solution. When n = 2, we have that
(1 + x_{1})(1 + x_{2}) = 1 + x_{1} + x_{2} + x_{1}x_{2} > 1 + x_{1} + x_{2} 

since
x_{1} and
x_{2} are nonzero with the same sign. Suppose, as
an induction hypothesis, that the result holds for
n =
k ³ 2.
Then


¼(1 + x_{k})(1 + x_{k+1}) (1 + x_{1} + x_{2} + ¼+ x_{k} + x_{k+1}) 
 
= [(1 + x_{1})(1 + x_{2}) ¼(1 + x_{k})  (1 + x_{1} + x_{2} + ¼+ x_{k})] 
 
+ x_{k+1}[(1+x_{1})(1+x_{2}) ¼(1 + x_{k})  1] 
 
> x_{k+1}[(1+x_{1})(1+x_{2}) ¼(1 + x_{k})  1] º A . 

 

If
x_{i} > 0 (1
£ i £ k+1), then 1 +
x_{i} > 1
(1
£ i £ k) and
A > 0.


Let 2 £ x_{i} < 0. Then, for 1 £ i £ k,
1 £ 1 + x_{i} < 1 Þ 1 £ (1 + x_{1})(1 + x_{2}) ¼(1 + x_{k}) £ 1 

Þ (1 + x_{1})(1 + x_{2}) ¼(1 + x_{k})  1 £ 0 . 

Since also
x_{k+1} < 0,
A ³ 0. Hence
(1 + x_{1})(1 + x_{2}) ¼(1 + x_{k+1}) > 1 + x_{1} + x_{2} + ¼+ x_{k+1} . 

The result follows by induction.
 27.

Second solution. The case n = 2 is proved as
in the first solution. Suppose that all x_{i} are negative and at
least two, say x_{1} and x_{2} lie in [2, 1]. Then
(1 + x_{1})(1 + x_{2}) ¼(1 + x_{n}) ³ 1 ³ 1  1  1 ³ 1 + x_{1} + x_{2} + ¼+ x_{n} 

since 2
£ x_{i} < 0 and
1 +
x_{i}  £ 1 for
1
£ i £ n.


Henceforth assume that either (i) all x_{i} are positive
(1 £ i £ n) or (ii) all x_{i} are negative with
2 £ x_{1} < 0 and 1 < x_{i} < 0 for 2 £ i £ n.
As an induction hypothesis, assume that the result holds for n = k ³ 2. Then 1 + x_{k+1} > 0, so that


(1+x_{2}) ¼(1 + x_{k})(1 + x_{k+1}) 
 
> (1 + x_{1} + x_{2} + ¼+ x_{k})(1 + x_{k+1}) by the induction hypothesis 
 
> 1 + x_{1} + x_{2} + ¼+ x_{k} + x_{k+1} by the n = 2 case. 

 

The result follows by induction.
28.
 28.

First 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
a and b which have respective circumcentres P and
Q. The respective lines m and n to these faces through their
circumcentres are nonparallel lines on the plane rightbisecting
AB and so intersect in a unique point. This point is the centre
of the only sphere that contains all of the vertices of a and
b.


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.
29.
 29.

First 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(n1) + 1 rounds. In the final round, each column must have
exactly one element.


Example:


Suppose, wolog (by shuffling the columns if necessary), that
the entries a_{11}, a_{22}, ¼, a_{nn} are selected from the
array (a_{ij}). If a_{ik} < a_{ii}, then this number must
have been an earlier possible selection and was rejected in favour of
a larger number in its column. Hence a_{ik} < a_{kk}.


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

First solution. Analysis. Suppose that we
have the required triangle PQR with Q Î L and
R Î C. Then a 60^{°} rotation with centre P
takes C to a circle C¢ and R to the point
lying on the intersection of C¢ and L.
Accordingly, we need to construct a rotated image C¢
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 POO¢ and with centre O¢
construct a circle C¢ with radius equal to that of
C. If this circle C¢ 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 C¢ is the image of C
under a 60^{°} rotation with centre P that carries O to
O¢. The point R lies on C¢ so its inverse image Q
under the rotation lies on C. Since PQ = PR and
ÐP = 60^{°}, PQR 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.