CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location: 
       

Solutions


227.
Let n be an integer exceeding 2 and let a0, a1, a2, , an, an+1 be positive real numbers for which a0 = an, a1 = an+1 and
ai-1 + ai+1 = ki ai
for some positive integers ki, where 1 i n.
Prove that
2n k1 + k2 + + kn 3n .
Solution. Since ki = (ai-1/ai) + (ai+1/ai) for each i,
n

i=1 
ki = n

i=1 

 ai+1

ai
+  ai

ai+1

n

i=1 
2 = 2n .

As for the other inequality, since the expression has cyclic symmetry, there is no loss in generality in supposing that an a1 and an an-1 with inequality in at least one case, so that 2an > an-1 + a1. Therefore, kn = 1 and an = an-1 + a1.

We establish the right inequality by induction. For the case n = 3, we may suppose that

a2 + a3 = k1 a1 ;    a1 + a3 = k2 a2 ;    a1 + a2 = a3
Substituting for a3 and rearranging the terms yields the brace of equations
2a2 = (k1 - 1)a1         2a1 = (k2 - 1)a2
whence 4 = (k1 - 1)(k2 - 1). It follows that k1 + k2 + k3 is either 5 + 2 + 1 = 8 or 3 + 3 + 1 = 7.

Now suppose the result holds when the index is n - 1 3. Then, supposing that kn = 1 and substituting for an, we obtain the n-1 equations

an-1 + a2 = (k1 - 1)a1

a1 + a3 = k2 a2


an-3 + an-1 = kn-2an-2

an-2 + a1 = (kn-1 - 1)an-1 .
By the induction hypothesis
(k1 - 1) + k2 + + (kn-1 - 1) 3(n - 1) = 3n - 3
whence
k1 + k2 + + kn (3n - 3) + 2 + 1 = 3n .


241.
Determine sec40 + sec80+ sec160.
Solution 1. The values 40, 80 and 160 all satisfy cos3q = 3D -1/2, or 8 cos3 q- 6cosq+ 1 = 3D 0. Thus, cos40. cos80 and cos160 are the roots of the cubic equation 8x3 - 6x + 1 = 3D 0, so that their reciprocals sec40, sec80 and sec160 are the roots of the cubic equation x3 - 6x2 + 8 = 3D 0. The sum of the roots of this cubic is
sec40 + sec80 + sec160 = 3D 6 .

Solution 2. Let z = 3D cos40 + i sin 40. Then z9 = 3D 1. In fact, since z9 - 1 = 3D (z - 1)(z2 + z + 1) (z6 + z3 + 1) and the first two factors fail to vanish, z6 + z3 + 1 = 3D 0. Also 1 + z + z2 + + z8 = 3D (1 + z + z2)(1 + z3 + z6) = 3D 0. Observe that cos40 = 3D 1/2(z + 1/z), cos80 = 3D 1/2(z2 + [ 1/(z2)]) and cos160 = 3D 1/2(z4 + [ 1/(z4)]), so that the given sum is equal to

2
 z

1 + z2
+  z2

1 + z4
+  z4

1 + z8

=3D 2
 z

1 + z2
+  z2

1 + z4
+  z5

1 + z

=3D 2
 z(1 + z + z4 + z5) + z2(1 + z + z2 + z3) + z5(1 + z2 + z4 + z6)

(1 + z)(1 + z2)(1 + z4)

=3D 2
 z7 + z6 + 3z5 + z4 + z3 + 3z2 + z + 1

(1 + z)(1 + z2)(1 + z4)

=3D 2
 (z+1)(z6 + z3 + 1) + 3z2 (z3 + 1)

(1 + z)(1 + z2)(1 + z4)

=3D 2
  0 - 3z8

1 + z + z2 + z3 + z4 + z5 + z6 + z7

=3D 2
 -3z8

-z8

=3D 6 .

Solution 3. [T. Liu]

sec40 + sec80 + sec 160
=3D  cos40 + cos80

cos40 cos80
+  1

cos 160
=3D  2cos60 cos20

cos40cos80
+  1

cos160
=3D  cos20 cos160 + cos40 cos80

cos40 cos80 cos 160
=3D  cos180 + cos140 + cos120 + cos40

cos40(cos240 + cos80)
=3D  -1 - 1/2

(1/2)(-cos40 + cos120+ cos40)
=3D  -3/2

-1/4
=3D 6 .

Solution 4. Let x = 3D cos40, y = 3D cos 80 and z = 3D cos160. Then

x + y + z = 3D 2cos60cos20 - cos20 = 3D 0
and
xy + yz + zx
=3D  1

2
[cos120 + cos140 + cos240 + cos 80 + cos200 + cos120]
=3D  1

2

-  3

2
+ x + y + z
=3D -  3

4
 .
Now
8 sin40 cos40 cos80 cos160
=3D 4 sin80 cos80 cos 160
=3D 2 sin160 cos160 = 3D sin 320 = 3D -sin40
so that xyz = 3D -1/8. Then the sum of the problem is equal to (xy + yz + zx)/(xyz) = 3D 6.



248.
Find all real solutions to the equation
  


x + 3 - 4


x - 1
 
+   


x + 8 - 6


x - 1
 
= 1 .
Solution 1. For the equation to be valid over the reals, we require that x 1. Suppose that y2 = x - 1 and y 0. Then the equation becomes
|y - 2 |+ |y - 3 | = 1 .
When 1 x 5, we have that 0 y 2 and the equation becomes (2 - y) + (3 - y) = 1 or y = 2, x = 5. When 5 x 10, we have that 2 y 3 and the equation becomes an identity (y - 2) + (3 - y) = 1. Thus, it holds for all x on the closed interval [5, 10]. Finally, when 10 x, we have that 3 y and the equation becomes (y - 2) + (y - 3) = 1 or y = 3, x = 10. Thus, the complete set of solutions of the equation is given by 5 x 10. All these solutions check out.

Solution 2. [Z. Wu] For a solution to exist, we require that x 1 and that both 0 x + 3 - 4{x - 1} 1 and 0 x + 8 - 6{x - 1} 1. These two conditions lead to (x + 2)2 16(x - 1) and (x + 7)2 36(x - 1), which in turn leads to

(x - 2)(x - 10) = (x2 + 4x + 4) - (16x - 16) 0
and
(x - 5)(x - 17) = (x2 + 14x + 49) - (36x - 36) 0 .
These conditions are both satisfied only if 5 x 10. (Thus, 5 x 10 is a necessary condition for a solution.)

On the other hand, 5 x 10 implies that 2 {x-1} 3, so that (as in Solution 1) we find that the equation is equivalent to ({x - 1} - 2) + (3 - {x-1}) = 1, which is an identity. Thus, the equation holds exactly when 5 x 10.

Comment. Your first observation should be that, in order for the equation to make sense, we require that x 1. It is important not just to write down a lot of algebraic equations, but to indicate the logical relationships between them; which equations imply which other equations? which pairs of equations are equivalent? This is especially desirable when surd equations are involved, where the operations that lead from one equation to another are not logically reversible and extraneous solutions might be introduced.



249.
The non-isosceles right triangle ABC has CAB = 90. Its inscribed circle with centre T touches the sides AB and AC at U and V respectively. The tangent through A of the circumscribed circle of triangle ABC meets UV in S. Prove that:
(a) ST || BC;

(b) |d1 - d2 | = r , where r is the radius of the inscribed circle, and d1 and d2 are the respective distances from S to AC and AB.
Solution. Wolog, we may assume that AB < AC so that S and C are on opposite sides of AB. Ad (a), SVT = SVA = 45, AV = VT and SV is common, so that triangles AVS and TVS are congruent. Hence SAV = STV STU = SAU = ACB (by the tangent-chord property). Since TU || AC, it follows that CB || ST.

Ad (b), let P and Q be the respective feet of the perpendiculars from S to AB and AC. Note that SQAP is a rectangle so that PUS = PSU = 45 and so PU = PS. Then |QS |- |PS | = |AP |- |PU | = r.



250.
In a convex polygon P, some diagonals have been drawn so that no two have an intersection in the interior of P. Show that there exists at least two vertices of P, neither of which is an enpoint of any of these diagonals.
Solution 1. If no diagonal has been drawn, the result is clear. Suppose that at least one diagonal has been drawn. Let d be a diagonal that has, on one of its sides, the fewest vertices of the polygon. There is at least one such vertex. Then on that side, no further diagonal is drawn, since it cannot cross d and cannot have fewer vertices between its endpoints than d. Hence there is at least one vertex on that side from which no diagonal is drawn.

On the other side of d, select a diagonal g which has the smallest number of vertices between its endpoints on the side opposite to the side of d. By an argument similar to the above, there is at least one vertex on the side of g opposite to d from which no diagonal has been drawn.

Solution 2. [S. King] The result is vacuously true for triangles. Suppose that the polygon has at least four sides. Suppose that a (possibly void) collection of diagonals as specified in the problem is given. We continue adding diagonals one at a time such that each new diagonal does not cross any previous one in the interior of the polygon. At each stage, the polygon P is partitioned into polygons with fewer sides all of whose vertices are vertices of the polygon P. As long as any of the subpolygons has more than three sides, we can add a new diagonal. However, the process will eventually terminate with a triangulation of P, i.e., a partitioning of P into n - 2 triangles all of whose vertices are vertices of P. (Exercise. Explain why the number of triangles is n - 2. One way to do this is to note that the sum of all the angles of the triangles is equal to the sum of the angles in the polygon.)

Each triangle must have at most two sides in common with the given polygon. Since there are n sides and n - 2 triangles, at least two triangles have two sides in common with P. In each case, the vertex common to the two sides has no diagonal emanating from it (neither an original diagonal nor an added diagonal), and the result follows.

Comment. Many solvers failed to appreciate that the collection of diagonals is given, and that the problem is to establish the desired property no matter what the collection is. A lot of arguments had the students constructing diagonals without indicating how the ones constructed might have anything to do with a given set; in effect, they were giving a particular situation in which the result obtained. Several solvers tried induction, using one diagonal to split P into two, but did not handle well the possibility that the loose vertices in the subpolygons might be at the ends of the subdividing diagonal. One way around this is to make the result stronger, and show that one can find two non-adjacent vertices that are not the endpoints of diagonals. This is certainly true for quadrilaterals, and using this an induction hupothesis yielded a straightforward argument for polygons of higher order.



251.
Prove that there are infinitely many positive integers n for which the numbers { 1, 2, 3, , 3n } can be arranged in a rectangular array with three rows and n columns for which (a) each row has the same sum, a multiple of 6, and (b) each column has the same sum, a multiple of 6.
Solution 1. The sum of all the numbers in the array is 3n(3n+1)/2, so that each column sum must be 3(3n + 1)/2. Since this is divisible by 6, 3(3n+1) must be a multiple of 12, and so 3n + 1 is divisible by 4 and n 1 (mod 4). Since each row sum, n(3n+1)/2 is divisible by 6, n must be divisible by 3. Putting this together, we conclude that n = 12k + 9 for some value of k.

We now show that, for each n of this form, we can actually construct an array with the desired property. Starting with the magic square, we derive the following array for n = 9:

8 1 6 17 10 15 26 19 24
21 23 25 3 5 7 12 14 16
13 18 11 22 27 20 4 9 2

We generalize this for n = 12k + 9, for k a nonnegative integer. Suppose that an array is possible. Then the sum of all the elements in the array is (36k + 27)(18k + 14) = 18(4k + 3)(9k + 7). The sum of the elements in each column is 6(9k + 7) = 54k + 42 and the sum in each row is 6(4k + 3)(9k + 7) = (4k + 3)(54k + 42). If we can achieve this with distinct entries, then we have constructed the array.

We build the array by juxtaposing horizontally 4k + 3 square 3 ×3 blocks of the form:

8 + 9a 1 + 9a 6 + 9a
3 + 9b 5 + 9b 7 + 9b
4 + 9c 9 + 9c 2 + 9c
where we make 4k + 3 distinct choices of each of a, b, c to ensure that no number is repeated in any row (it is not possible for any repetition to occur down a column). To achieve the column sum, we require that 15 + 9(a + b + c) = 54k + 42, or a + b + c = 6k + 3 = 3(2k + 1). To achieve the row sum, we require that
15(4k + 3) + 27
a
= 15(4k + 3) + 27
b = 15(4k + 3) + 27
c
= (4k + 3)(54k + 42)
so that

a =
b =
c = (4k + 3)(2k + 1) = 0 + 1 + + (4k + 2) ,
where each sum is over 4k + 3 distinct elements. It is convenient to let the sets of a's, b's, and c's each consist of the numbers 0, 1, 2, , 4k + 2 in some order. In the ith 3 ×3 block, let 0 a, b, c, 4k + 2 and
a = i - 1

b (i - 1) + 2(k + 1) = 2k + i + 1 (mod 4k + 2)

c = (6k + 3) - (a + b) 4k + 3 - 2i  (mod 4k + 3) .
for 1 i 4k+3. It is straightforward to verify that the a's, the b's and the c's each run through a complete set of residues (mod 4k + 3), and we have arranged that a + b + c = 6k + 3. If 1 i 2k + 1, then 2k + 2 b = 2k + i + 1 4k + 2 and 2k + 2 a + b = 2(k + i) 6k + 2, so that 1 c 4k + 1. If 2k + 2 i 4k + 3, then 0 b = (2k + i + 1) - (4k + 3) = i - 2k - 2 2k + 1 and 2k + 1 a + b = 2i - 2k - 3 6k + 3, so that 0 c 4k + 2. With this choice of the variables a, b, c we can construct the array as desired.

For example, when n = 45, k = 3, there are 15 blocks and the choice of a, b, c for these blocks can be read along the rows of

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
8 9 10 11 12 13 14 0 1 2 3 4 5 6 7
13 11 9 7 5 3 1 14 12 10 8 6 4 2 0
It is left as an exercise for the reader to construct the 3 ×45 array.

Solution 2. [Y. Zhao] We can form the 3 ×9 array:

4 9 2 13 18 11 22 27 20
12 14 16 21 23 25 3 5 7
26 19 24 8 1 6 17 10 15
Suppose, as an induction hypothesis, we can build a 3 ×n array for some positive integer n. Duplicate this array five times and put them side by side in a row. Partition the 3 ×5n array into fifteen 1 ×n subarrays, and to the elements of each of the fifteen subarrays add a constant number as indicated by the positions in the following 3 ×5 table:
+0 +3b +6n +9n +12n
+6n +9n +12n +0 +3
+12n +6n +0 +9n +3n
The row sum of the numbers added is 30n and the column sum is 18n, so the 3 ×5n array preserves the divisibility by 6 properties of the 3 ×n array. Therefore, we can see by induction that an array is constructibel whenever n = 9 ×5k for 0 k.

Solution 3. [J. Zhao] For the time being, neglect the conditions involving divisibility by 6, and focus only on the condition that the numbers 1, 2, , 3n be used and that the row sums and the column sums be each the same. Then, when n = 3, a magic square will serve.

Suppose that, for some k 1, we have found a suitable 3 ×3k matrix M. Let A be the 3 ×3k+1 matrix obtained by placing three copies of M side by side and B the 3 ×3k+1 matrix determined by placing side by side the 3 ×3k matrices B1, B2, B3 where each column of B1 is (the transpose of) (0, 1, 2), of B2 is (1, 2, 0), and of B3 is (2, 0, 1). Each of A and B has constant row sums and constant column sums.

Let N = A + 3k+1B. Then N not only has constant row and column sums, but consists of the numbers 1, 2, , 3k+2 (why?). The row sums of M are each (1/6)(3k+1)(3k+1 + 1), so that the row sums of N are each

3 ×(1/6)(3k+1)(3k+1 + 1)
+ 3k+1(3k) + 3k+1(2 ×3k) = (1/6)[3k+2(3k+1 + 1)] + (32k+1 ×3)
= (1/6)(3k+2)(3k+1 + 1 + 6 ×3k) = (1/6)(3k+2)(3k+2 + 1) .
The column sums of M are each (3/2)(3k+1 + 1) and so the column sums of N are each
(3/2)(3k+1 + 1) + 3k+1 + 2 ×3k+1 = (1/2)(3k+2 + 3 + 2 ×3k+2) = (3/2)(3k+2 + 1) .

We now require that each of (1/6)(3k+1)(3k+1 + 1) and (3/2)(3k+1 + 1) be divisible by 6. This will occur exactly when 3k+1 + 1 0 (mod 4), so that k must be even. Thus, we can obtain an array as desired when n = 9m for some positive integer m. (Note that 9m 9 (mod 12).)



252.
Suppose that a and b are the roots of the quadratic x2 + px + 1 and that c and d are the roots of the quadratic x2 + qx + 1. Determine (a - c)(b - c)(a + d)(b + d) as a function of p and q.
Solution 1. From the theory of the quadratic, we have that a + b = -p, c + d = -q and ab = cd = 1. Then
(a - c)(b - c)
(a + d)(b + d) = (a - c)(b + d)(b - c)(a + d)
= (ab - cd + ad - bc)(ba - cd + bd - ca)
= (ad - bc)(bd - ca) = abd2 - a2cd - b2cd + abc2
= d2 - a2 - b2 + c2 = [(c + d)2 - 2cd] - [(a + b)2 - 2ab]
= (q2 - 2) - (p2 - 2) = q2 - p2 .

Solution 2. Using a + b = -p, c + d = -q and ab = cd = 1, we obtain that

(a-c)(b-c)(a+d)(b+d)
= [ab - (a + b)c + c2][ab + (a + b)d + d2]
= (1 + pc + c2)(1 - pd + d2) = (2 + c2 + d2) - p2
= (c + d)2 - p2 = q2 - p2 .



253.
Let n be a positive integer and let q = p/(2n+1). Prove that cot2 q, cot2 2q, , cot2 nq are the solutions of the equation

2n + 1
1

xn -
2n + 1
3

xn-1 +
2n+1
5

xn-2 - = 0 .
Solution 1. From de Moivre's Theorem that
cosmq+ i sinmq = (cosq+ i sinq)m ,
we obtain from a comparison of imaginary parts that
sinmq =
m
1

cosm-1qsinq-
m
3

cosm-3 sin3 q+  ,
for each positive integer m. Hence
sin(2n + 1)q = sin2n+1q

2n + 1
1

cot2n q-
2n + 1
3

cot2n-2 q+
 .
When q = (kp)/(2n + 1) for 1 k n, sin(2n + 1)q = 0 while sinq 0. The desired result follows.

Solution 2. [Y. Zhao] Observe that, for each complex a,

 1

2
[(a + 1)2n+1 - (a - 1)2n+1] =
2n + 1
1

a2n +
2n + 1
3

a2n - 2 +
2n + 1
5

a2n - 4 +   .
Suppose that a = i cotkq with q = p/(2n+1) and 1 k n. Note that sinkq 0. Then

2n + 1
1
(-cot2 kq)n
+
2n + 1
3
(-cot2 kq)n-1 + =
 1

2
[ (i cotk q+ 1)2n + 1 -(i cotq- 1)2n + 1]
=  1

2

 i

sinkq

2n + 1

 
[ (coskq- i sinkq)2n + 1- (coskq+ i sinkq)2n + 1 ]
=
 i

sinkq

2n + 1

 
[ - sin(2n + 1)k q] =
 i

sinkq

2n + 1

 
[ - sinkp] = 0 ,
and the result follows.



254.
Determine the set of all triples (x, y, z) of integers with 1 x, y, z 1000 for which x2 + y2 + z2 is a multiple of xyz.
Solution. Suppose that x2 + y2 + z2 = kxyz, for a positive integer k. It can be checked that if the equation is satisfied by (x, y, z) then it is also satisfied by (x, y, kxy - z). Since z2 < x2 + y2 + z2 = kxyz, it follows that z < kxy, If z > 1/2kxy, then kxy - z < 1/2kxy. Suppose that we start with a solution. If we have, say z exceeding 1/2xy, then we can replace z by a new value less than 1/2xy. We can do the analogous thing with x and y. Every such operation reduces the sum x + y + z, so it can be performed at most finitely often, and we reach a situation where it cannot be done any more. Thus, we arrive at a solution where, say, 1 x y z kxy/2, so that, in particular kx 2. We can also start with such a solution and go backwards to achieve any given solution.

Since

x2 + y2 +
 kxy

2
- z
2

 
=
 kxy

2

2

 
 ,
it follows that
x2 + y2 +
 kxy

2
- y
2

 

 kxy

2

2

 
 ,
so that
3y2 x2 + 2y2 kxy2
and kx 3. Thus kx = 2 or kx = 3.

The case kx = 2 leads to x2 + (y - z)2 = 0 which has no solutions as specified. Hence kx = 3 and k = 1 or k = 3. For these two cases, we find that the base solutions are respectively (x, y, z) = (3, 3, 3) and (x, y, z) = (1, 1, 1).

Suppose that k = 1. Modulo 3, any square is congruent to 0 or 1. If, say, x 0 (mod 3), then y2 + z2 0 (mod 3); this can occur only if y and z are multiples of 3. Hence (x, y, z) = (3u, 3v, 3v) for some integers u, v, w. But then 9u2 + 9v2 + 9w2 = 27uvw, or u2 + v2 + w2 = 3uvw. Contrarily, any solution (u, v, w) of this equation gives rise to a solution (x, y, z) of x2 + y2 + z2 = xyz. Therefore there is a one-one correspondence between solutions of x2 + y2 + z2 = xyz where all numbers are multiples of 3 and solutions of x2 + y2 + z2 = 3xyz. We will obtain these solutions below.

The only other possibility is that none of x, y, z is divisible by 3. But then, x2 + y2 + z2 would be a multiple of 3 and xyz not a multiple of 3; thus there are no solutions of this type.

Suppose that k = 3. From the above, we know that every solution arises from a solution for which 1 x y z 3xy/2 and for such a solution x = 1. Let (x, y, z) = (1, y, ty) where 1 y 3/2. Then 1 + (1 + t2)y2 = 3ty2, so that

y2 =  1

3t - 1 - t2
=  1

 5

4
-(t -  3

2
)2
 .
The denominator is not less than 1, so that y2 1. Hence the only solution that can generate the rest is (x, y, z) = (1, 1, 1).

To get a handle on the situation, fix x = u and consider a sequence of solutions (x, y, z) = (u, vn-1, vn). The solution w = vn-1 satisfies the quadratic equation

u2 + w2 + vn2 = 3uwvn
and so also does a second value w = vn+1. By the theory of the quadratic, we have that
vn+1 + vn-1 = 3uvn
(1)
and
vn+1 vn-1 = u2 + vn2 .
(2)
If we start off with a solution (x, y, z) = (u, v0, v1), we can use either (1) or (2) to determine the sequence { vn }. Note that, since
vn+1 - vn = vn - vn-1 + (3u - 2)vn > vn - vn-1 ,
if v1 v0, then the sequence { vn } is increasing. Note also, that the equations (1) and (2) are symmetric in vn-1 and vn+1, so we can extend the sequence backwards as well as forwards.

Using the recursion vn+1 = 3uvn - vn-1, we get the following sequences for various values of u:

u = 1 :   { vn } = { 1, 1, 2, 5, 13, 34, 89, 233, 610 }

u = 2 ;   { vn } = { 1, 1, 5, 29, 169, 985 }

u = 5 ;   { vn } = { 194, 13, 1, 2, 29, 433 }

u = 13 ;    { vn } = { 34, 1, 5, 194 }

u = 29 ;    { vn } = { 433, 5, 2, 169 }

u = 34 ;    { vn } = { 13, 1 89 }
and so on. This yields the following solutions with 1 x y z 1000: (x, y, z) = (1, 1, 1), (1, 1, 2), (1, 5, 13), (1, 13, 34), (1, 34, 89), (1, 89, 233), (1, 233, 610), (2, 5, 29), (2, 29, 169), (2, 169, 985), (5, 13, 194), (5, 29, 433).


© Canadian Mathematical Society, 2014 : https://cms.math.ca/