Solutions to the November problems

185.

Find all triples of natural numbers a, b, c, such that all of the following conditions hold: (1) a < 1974; (2) b is less than c by 1575; (3) a² + b² = c².

Solution. Conditions (2) and (3) can be written as c - b = 1575 and a² = c² - b². Hence a² = 1575(c+b) = 3² ·5² ·7 ·(b + c), so that a = 3 ·5 ·7 ·k = 105k. By (1), k £ 18.

>From 105² k² = 1575(c + b), it follows that 7k² = c + b. Putting this with 1575 = c - b yields that 2c = 7k² + 1575 and 2b = 7k² - 1575. Since b is a natural number, 7k² > 1575, whence k > 15. Since k is also odd (why?), the only possibility is for k to be equal to 17. This works and we obtain the triple (a, b, c) = (1785, 224, 1799).

Comment. This was solved by most participants. Some solutions used the fact that all primitive pythagorean triples can be parametrized by (a, b, c) = (m² - n², 2mn, m² + n²), where m and n are natural numbers, m > n and the greatest common divisor of m and n is 1. Note that this representation is not adequate to get all non-primitive triples, such as (15, 36, 39) and the triple of this problem. The general form is given by (a, b, c) = (k(m² - n²), 2kmn, k(m² + n²)), where k is a positive constant. When you build your solution on such a ``well-known'' fact, make sure that you recall it correctly and respect all restrictions and specifics. Otherwise, you risk applying it in a situation that does not satisfy all the requirements or you find only a subset of the possible solutions.

---

186.

Find all natural numbers n such that there exists a convex n-sided polygon whose diagonals are all of the same length.

Solution 1. [T. Yue] First, we prove that n < 6. Suppose that n ³ 6 and that there exists a convex n-sided polygon with vertices A₁, A₂, ¼, A_n whose diagonals are all of the same length. Since the diagonals are all of the same length, we have that A₁A₅ = A₂A₅ = A₁A₄ = A₂A₄, so that A₁A₂A₅ and A₁A₂A₄ are isosceles triangles and A₄ and A₅ both lie on the right bisector of A₁A₂. Since the polynomial is convex, both A₄ and A₅ must lie on the same side of A₁A₂. But then they could not be distinct, yielding a contradiction.

In the case n = 3, there are no diagonals, so the result is vacuously true. For n = 4, all squares, rectangles and isosceles trapezoids satisfy the condition. When n = 5, the regular pentagon is an example. (Is it the only example?)

Solution 2. Suppose that n ³ 6, and the vertices of the polygon be A₁, A₂, ¼, A_n. Suppose that A₁A_n-2 and A₂A_n-1 intersect at O. Then, by the triangle inequality, A₁O + OA_n-1 > A₁A_n-1 and A₂O + OA_n-2 > A₂A_n-2, so that

A1An-2 + A2An-1 = A1O + OAn-2 + A2O + OAn-1 > A1An-1 + A2An-2

and so the diagonals A_iA_j are not all of the same length. Hence, n £ 5 and we can conclude as before.

---

187.

Suppose that p is a real parameter and that

f(x) = x3 - (p + 5)x2 - 2(p - 3)(p - 1)x + 4p2 - 24p + 36 .

(a) Check that f(3 - p) = 0.

(b) Find all values of p for which two of the roots of the equation f(x) = 0 (expressed in terms of p) can be the lengths of the two legs in a right-angled triangle with a hypotenuse of 4Ö2.

Solution. (a) Observe that

f(x) = [(x - (3 - p)][x2 - 2(p+1)x + 4(p-3)] .

(b) [Y. Sun] From the factorization in (a), we can identify the three roots: x₁ = 3 - p,

x2 = (p+1) +   _________ Ö(p-1)2 + 12    ,

x3 = (p+1) -   _________ Ö(p-1)2 + 12    .

Note that x₂ - x₃ = 2Ö[((p-1)² + 12)] ³ 2Ö[12] = 4Ö3 > 4Ö2, so that, by the triangle inequality, x₂ and x₃ cannot be the legs of a right triangle with hypotenuse 4Ö2. On the other hand,

x1 + x3 = 4 -   _________ Ö(p-1)2 + 12   £ 4 -   __ Ö12   = 2(2 - Ö3) < 4Ö2 ,

so that, by the triangle inequality, x₁, x₃ and 4 Ö2 cannot be the sides of a triangle. Thus, the only possibility is that x₁² + x₂² = 32.

Thus, we must have

(3 - p)2 + [(p+1) +   __________ Öp2 - 2p + 13   ]2 = 32

Þ 2(p+1)   __________ Öp2 - 2p + 13   = -3p2+ 6p + 9 = 3(p+1)(3 - p) .

Therefore, either p = -1 or 2Ö[(p² - 2p + 13)] = 3(3 - p). The latter possibility leads to

4(p2 - 2p + 13) = 9(p - 3)2 Þ 5p2 - 46p + 29 = 0 .

Since 3(3-p) must be positive, we reject one root of this quadratic for p, and so have only the additional possibility (23 - 8Ö6)/5.

---

188.

(a) The measure of the angles of an acute triangle are a, b and g degrees. Determine (as an expression of a, b, g) what masses must be placed at each of the triangle's vertices for the centroid (centre of gravity) to coincide with (i) the orthocentre of the triangle; (ii) the circumcentre of the triangle.

(b) The sides of an arbitrary triangle are a, b, c units in length. Determine (as an expression of a, b, c) what masses must be placed at each of the triangle's vertices for the centroid (centre of gravity) to coincide with (i) the centre of the inscribed circle of the triangle; (ii) the intersection point of the three segments joining the vertices of the triangle to the points on the opposite sides where the inscribed circle is tangent (be sure to prove that, indeed, the three segments intersect in a common point).

Solution. [R. Barrington Leigh] Suppose that a, b, c are the respective lengths of BC, CA and AB of triangle ABC and that a = ÐCAB, b = ÐABC and g = ÐBCA. Let masses m_a, m_b, m_c be masses placed at the respective vertices A, B, C. We use the following lemma, which will be established in the Comments:

Lemma 1. The centroid G of two combined collections of mass particles is on the line joining the centroids P and Q of the two collections, and the following ratio holds: PG:GQ = m_Q:m_P, where m_Q and m_P are the totals of the masses in the two mass collections at Q and P respectively.

It follows that, if X is the centroid of the masses at the vertices of DABC and Y is the intersection point of AX and BC, then Y is the centroid of the masses at the vertices B and C. Furthermore, let h_b and h_c be the perpendicular distances from B and C respectively to the line AY. By the lemma and the similar right triangles formed by the drawn perpendiculars,

mb mc = YC YB = hc hb

(*)

(a) (i) Let Y be the foot of the altitude from A to BC, so that the orthocentre of the triangle is on AY. By (*),

mb mc = AY/tang AY/tanb = tanb tang  .

By symmetry, we see that

ma : mb : mc = tana: tanb: tang .

Since the triangle is acute, the elements of the ratio are positive and it is well-defined.

(a) (ii) Let X = O be the circumcentre of DABC. From (*),

mb mc = hc hb = OC ·sinÐCOA OB ·sinÐBOA = sin2b sin2g  .

By symmetry, we have that

ma : mb : mc = sin2a: sin2b: sin2g .

(b) (i) Let X = I, the incentre of the triangle ABC; this is the intersection of the angle bisectors. Then ÐBAI = ÐCAI, and, by (*),

mb mc = hc hb = b ·sinÐCAI c ·sinÐBAI = b c  .

By symmetry, we find that m_a : m_b : m_c = a : b : c.

(b) (ii) Let the incircle of ABC meet BC at D, CA at E and AB at F. Let x, y, z be the respective lengths of AE = AF, BD = BF, CD = CE, so that y + z = a, z + x = b, x + y = c. Then 2x = b + c - a, 2y = c + a - b and 2z = a + b - c. The semi-perimeter s of the triangle is equal to (a + b + c)/2, so that x = s - a, y = s - b and z = s - c. Using Ceva's Theorem, we see from

AF FB · BD DC · CE EA = x y · y z · z x = 1

that AD, BE and CF concur at a point X. From (*), we have that

mb mc = CD BD = z y = 1/(s-b) 1/(s-c)

so that, from symmetry,

ma : mb : mc = 1 s - a : 1 s - b : 1 s - c  .

Comment. A couple of correct solutions were received, most based on the lemma and the derived statement (*). This solution was chosen because of its excellently organized and clear presentation. Some students came up with other expressions in the ratios, equivalent after some simple trigonometric transformations to the expressions here. Two of the students, A. Feiz Mohammadi and J.Y. Zhoa used an interesting an helpful fact:

Lemma 2. Let X be the centroid of triangle ABC and denote by S_a, S_b and S_c the respective areas of the triangles XBC, XCA and XAB. Then m_a : m_b : m_c = S_a : S_b : S_c.

Lemma 2 can be used to obtain a beautiful and elegant solution to each of the four parts of the problem. Let us turn to the proofs of these lemmata.

Proof of Lemma 1. We statement can be replaced by the equivalent form: given two point masses m_P and m_Q at the respective points P and Q, their centroid is on the line segment PQ at the point G for which PG:GQ = m_Q:m_P. From the definition of a centroid, if O is any point selected as the origin of vectors,

® OG   = mP ® OP   + mQ ® OQ   mP + mQ = mP mP + mQ ® OP   + mQ mP + mQ ® OQ    .

(1)

In general, consider a point K on the segment PQ for which PK : KQ = k : (1 - k), for 0 < k < 1. Then

® OK   = ® OP   + ® PK   = ® OP   + k ® PQ   = ® OP   + k( ® OQ   - ® OP   ) = (1 - k) ® OP   + k ® OQ    .

(2)

Now choose k = m_Q/(m_P + m_Q), so that 1 - k = m_P/(m_P + m_Q). From (1) and (2), we have that G = K and we can complete the proof of the lemma.

Proof of Lemma 2. We prove that m_a : m_b = S_a : S_b, whence the rest follows from symmetry. Let K be the intersection of CX and AB. Then m_a : m_b = BK : AK. Since triangles AKC and BKC have the same altitudes from C, [AKC]:[BKC] = AK : BK. Similarly, [AXK]:[BXK] = AK:BK. Now S_a = [BKC] - [BXK] and S_b = [AKC] - [AXK], so that S_a : S_b = BK : AK and the result is proven.

---

189.

There are n lines in the plane, where n is an integer exceeding 2. No three of them are concurrent and no two of them are parallel. The lines divide the plane into regions; some of them are closed (they have the form of a convex polygon); others are unbounded (their borders are broken lines consisting of segments and rays).

(a) Determine as a function of n the number of unbounded regions.

(b) Suppose that some of the regions are coloured, so that no two coloured regions have a common side (a segment or ray). Prove that the number of regions coloured in this way does not exceed ¹/₃(n² + n).

Solution 1. (a) Draw a circle big enough to contain in its interior all the intersection points of the n lines. Since there are n lines and each of them intersects the circle in two points, they divide the circle into 2n arcs. Each of the arcs corresponds to one unbounded region, so that there are 2n unbounded regions.

(b) [M. Butler] Let k regions be coloured. Construct a circle around all the bounded regions, big enough to contain part of each of the unbounded regions as well as the intersection points of the lines. Regions that were unbounded before are now bounded (in part by an arc of the circle). Denote the k coloured regions by R₁, R₂, ¼, R_k, and let R_i have v_i vertices (including the intersections of the lines and the circles). Every region has at least three vertices, so that v_i ³ 3, and v₁ + v₂ + ¼+ v_k ³ 3k (1).

On the other hand, we can tabulate v₁ + v₂ + ¼+ v_k by adding up the numer of coloured regions meeting at an intersection, for all intersection points. Since no three lines have a common point, there are (n || 2) intersection points among the lines and each of them is a vertex of at most two coloured regions. So there are at most 2 (n || 2) coloured regions counted so far. In addition, there are 2n intersections between the circles and the lines with at most one coloured region at each of them. Taking (1) into consideration, we deduce that

2 æ ç è n 2 ö ÷ ø + 2n ³ v1 + v2 + ¼+ vk ³ 3k

so that n² + n ³ 3k and the result follows.

Solution 2. (b) Let m₂, m₃, ¼ m_k denote the number of coloured regions with respectively 2, 3, ¼, k sides (rays or segments). Regions with two sides are angles, and hence unbounded. Since no two adjecent regions are coloured, m₂ £ (1/2)2n = n. On the other hand, each line is divided by the other n-1 lines into n parts, so that the number of parts of all the lines is n². Therefore

2m2 + 3m3 + 4m4 + ¼+ kmk £ n2 .

The total number k of all the coloured regions satisfies

k = m1 + m2 + ¼+ mk = (1/3)m2 + (2/3)m2 + m3 + ¼+ mk £ (1/3)m2 + (1/3)(2m2 + 3m3 + 4m4 + ¼+ kmk £ (1/3)(n + n2) ,

as desired.

---

190.

Find all integer values of the parameter a for which the equation

|2x + 1 |+ |x - 2 | = a

has exactly one integer among its solutions.

Solution 1. [H. Li] To deal with the absolute values, we consider the equation for different ranges of x. If x < -1/2, the equation becomes -3x + 1 = a (E₁). If -1/2 £ x < 2, the equation is x + 3 = a (E₂). If x ³ 2, the equation is 3x - 1 = a (E₃). Thus, the given equation is the union of three linear equations. The graph of a as a function of x is a broken line consisting of two rays u₁ and u₃ (corresponding to E₁ and E₃) and a segment u₂ (corresponding to E₂); please graph it before continuing to read. The minimum possible value of a is 2.5. For an integer a to admit more than one integer solution to the equation, the horizontal line y = a must intersect the graph in at least two lattice points.

When x < -1/2, a > 2.5 and when -1/2 £ x < 2, then 2.5 £ a < 5. The only lattice points on segment u₂ are (0, 3) and (1, 4) and the second one has a corresponding lattice point on u₁. So, for a = 4, there are two integer solutions, -1 and 1, to the equation. Let x be an integer. When x ³ 2, a ³ 5 and we want to consider lines y = a intersecting rays u₁ and u₃. When x < -1/2, then -3x + 1 º 1 (mod 3), while if x ³ 2, 3x - 1 º 2 (mod 3), so that none of the horizontal lines can intersect both of them at a lattice point.

Hence, in conclusion, the given equation has exactly one integer solution x for the following values of a: a = 3, a ³ 5 and a º 1 (mod 3) and a ³ 5 and a º 2 (mod 3).

Solution 2. First, solve the equation by considering the three cases:

· x ³ 2: Then x = [(a+1)/3] and the equation is solvable in this range Û a ³ 5;

· -1/2 < x < 2: Then x = a - 3 and the equation is solvable in this range Û 5/2 < a < 5;

· x £ 1/2: Then x = (1 - a)/3 and the equation is solvable in this range Û a ³ 5/2.

Thus, summing up, we see that the equation has

· no solution when a < 5/2,

· the unique solution x = -1/2 when a = 5/2,

· two solutions x = a - 3 and x = (1-a)/3 when 5/2 < a < 5, of which both are integers when a = 4 and one is an integer when a = 3,

· two solutions x = 2 and x = -4/3 when a = 5, and

· two solutions x = (1 ±a)/3 when a > 5.

When a > 5 we can check that there is no solution when a º 0, and exactly one solution when a \not º 0 (mod 3), and we obtain the set in the first solution.

---

191.

In Olymonland the distances between every two cities is different. When the transportation program of the country was being developed, for each city, the closest of the other cities was chosen and a highway was built to connect them. All highways are line segments. Prove that

(a) no two highways intersect;

(b) every city is connected by a highway to no more than 5 other cities;

(c) there is no closed broken line composed of highways only.

Solution. (a) Assume that the highways AC and BD intersect at a point O. From the existence of AC, either C is the closest city to A or A is the closest city to C. A similar statement holds for BD. Wolog, suppose that C is the closest city to A and D the closest city to B. Hence, AD > AC, BC > BD so that AD + BC > AC + BD. On the other hand, from the triangle inequality,

AO + OD > AD  &   BO + OC > BC   ÞAC + BD = (AO + OC) + (BO + OD) > AD + BC ,

which contradicts the earlier inequality. Thus, no two highways intersect.

(b) Consider any three cities A, B, X. If X is connected by a highway to both A and B, then AB must be the longest side in triangle ABX. To prove it, let us suppose, if possible, that one of the other sides, say AX, is longest. Then AX > AB and AX > XB, so that AX would not exist as B is closer to A than X is, and B is closer to X than A is.

So AB is the longest side, which implies that ÐAXB is the greatest angle in the triangle. Thus, ÐAXB > 60^°. Assume that a city X is connect to six other cities A, B,C, D, E, F by highways. Then each of the angles with vertices at X with these cities must exceed 60^°, so the sum of the angles going round X from one highway back to it must exceed 360^°, which yields a contradiction. Therefore, every city is connected by a highway to no more than five other cities.

(c) Suppose that there are n cities A₁, A₂, ¼, A_n that are connected in this order by a closed broken line of highways. Since all distances between pairs of cities are distinct, there must be a longest distance between a pair of adjacent cities, say A₁ and A_n. Then A₁A_n > A₁A₂, so A_n is not the closest city to A₁. Also A₁A_n > A_n-1A_n, so A₁ is not the closest city to A_n. Therefore, the highway A₁A_n must not exist and we get a contradiction. So there is no broken line composed only of highways.