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

26.
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.
View solution
27.
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  ,

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 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.
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: m2 - 4n = u2, m2 + 4n = v2 for some integers u and v. Suppose m2 can be expressed as the sum of two squares: m2 = p2 + q2. Then 2m2 = (p + q)2 + (p - q)2. Write u = p - q, v = p + q. Then 8n = v2 - u2 = 4pq so that n = 1/2pq.
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)) .

26.
Second solution. With the notation of the first solution, we have that m2 - u2 = v2 - m2, whence v2 - 2m2 = -u2. Let us take u = 1. We show that v2 - 2m2 = -1 has infinitely many solutions with m odd. Let (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 - 2mk2 = -1. Let (m, n) = (mk, 1/4(mk2 - 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).

26.
Third solution. [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 the First Solution.

27.

27.
First solution. When n = 2, we have that
 (1 + x1)(1 + x2) = 1 + x1 + x2 + x1x2 > 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.

27.
Second solution. 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.

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 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 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(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

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.

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.