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² + 5x + 6 = (x + 2)(x + 3) while x² + 5x - 6 = (x + 6)(x - 1). Determine infinitely many coprime pairs (m, n) of positive integers for which both x² + mx + n and x² + 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 + x1)(1 + x2) ¼(1 + xn) > 1 + x1 + x2 + ¼+xn  ,

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

Now we construct our examples. Let r and s be a coprime pair of integers with opposite parity. Define p = r² - s², q = 2rs, m = r² + s² and n = rs (r² - s²). Then any prime power divisor of m and n must divide both r² + s² and one of r, s and r² - s², and hence both 2r² and 2s². 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 m² - u² = v² - m², whence v² - 2m² = -u². Let us take u = 1. We show that v² - 2m² = -1 has infinitely many solutions with m odd. Let (v, m) = (v_k, m_k) 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, v_k² - 2m_k² = -1. Let (m, n) = (m_k, ¹/₄(m_k² - 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² + 29x + 210 = (x + 14)(x + 15) and x² + 29x - 210 = (x + 35)(x - 6).

26.

Third solution. [M. Boase] Let a be even and let (m, n) = (a² + 1, a³ - a). Then the greatest common divisor of m and a is 1, as is the greatest common divisor of m and a² - 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 x₁ and x₂ 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 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 + xi < 1 Þ -1 £ (1 + x1)(1 + x2) ¼(1 + xk) £ 1

Þ (1 + x1)(1 + x2) ¼(1 + xk) - 1 £ 0 .

Since also x_k+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 x_i are negative and at least two, say x₁ and x₂ lie in [-2, -1]. Then

(1 + x1)(1 + x2) ¼(1 + xn) ³ -1 ³ 1 - 1 - 1 ³ 1 + x1 + x2 + ¼+ xn

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₁ < 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 + 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 a₁₁, a₂₂, ¼, 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.