 Canadian Mathematical Society www.cms.math.ca
 location:
Problems - Mathematical Olympiads' Correspondence Program - 1997-1998

Problem Set 1

1.
(a) Let m be any positive integer greater than 2, such that x2 º 1 (mod m) whenever the greatest common divisor of x and m is equal to 1. An example is m = 12. Suppose that n is a positive integer for which n + 1 is a multiple of m. Prove that the sum of all of the divisors of n is divisible by m.
(b) Does the result in (a) hold when m = 2?
(c) Find all possible values of m that satisfy the condition in (a).
(Note: (a) and (c) are posed as Problem 2229 in CM+MM, April, 1997. Part (c) was submitted by the proposer without a solution.
View solution
2.
(a) Prove that, for each pair (m, n) of integers with 1 £ m £ n,
 n å i = 1 i(i-1)(i-2)¼(i-m+1) = (n+1)n(n-1)¼(n-m+1)m+1 .

(b) Suppose that 1 £ r £ n and consider all subsets of r elements of the set { 1, 2, 3, ¼, n }. The elements of this subset are arranged in ascending order of magnitude. For 1 £ i £ r, let ti denote the ith smallest element in the subset, and let T(n, r, i) denote the arithmetic mean of the elements ti. Prove that
 T(n, r, i) = i æç è n+1r+1 ö÷ ø .

(Note: Part (b) is Problem 2239 in CM+MM, May, 1997.)
View solution

3.
Let 0 < a < b. Prove that, for any positive integer n,
b+a
2
£ n æ
ú
Ö

 bn+1 - an+1(b-a)(n+1)

£ n æ
ú
Ö

 an + bn2

.
View solution

4.
How many distinct acute angles a are there for which cosacos2acos4a = 1/8?
(Note: This is Problem 2249 in CM+MM, May, 1997.)
View solution

5.
A convex closed figure lies inside a given circle. The figure is seen from every point of the circumference of the circle at right angles (that is, the two rays drawn from the point and supporting the convex figure are perpendicular). Prove that the centre of the circle is a centre of symmetry of the figure.
View solution
6.
The nonisosceles right triangle ABC has ÐCAB = 90°. The inscribed circle with centre T touches the sides AB and AC at U and V respectively. The tangent through A of the circumscribed circle meets UV produced 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.
(Note: This is Problem 2235 in CM+MM.)
View solution

Solutions to Problem Set 1

1.

1.
(a) First solution. Let n + 1 be a multiple of m. Then gcd(m, n) = 1. We observe that n cannot be a square. Suppose, if possible, that n = r2. Then gcd(r, m) = 1. Hence r2 º 1 (mod m). But r2 + 1 º 0 (mod m) by hypothesis, so that 2 is a multiple of m, a contradiction.
As a result, if d is a divisor of n, then n/d is a distinct divisor of n. Suppose d |n (read ``d divides n''). Since m divides n + 1, therefore gcd(m, n) = gcd(d, m) = 1, so that d2 = 1 + bm for some integer b. Also n + 1 = cm for some integer c. Hence
 d + nd = d2 + nd = 1 + bm + cm - 1d = (b + c)md .
Since gcd(d, m) = 1 and d + n/d is an integer, d divides b + c and so d + n/d º 0 (mod m).

Hence
 å d |n d = å { (d + n/d) : d |n, d < Ön } º 0     (mod   m)
as desired.

(a) Second solution. Suppose that n + 1 º 0 (mod m). As in the first solution, it can be established that n is not a perfect square. Let x be any positive divisor of n and suppose that xy = n; x and y are distinct. Since gcd (x, m) = 1, x2 º 1 (mod m), so that
 y = x2 y º xn º -x    (mod  m)
whence x + y is a multiple of m. Thus, the divisors of n comes in pairs, each of which has sum divisible by m, and the result follows.

(a) Third solution. [M. Boase] As in the second solution, if xy = n, then x2 º y2 º 1 (mod m) so that
 0 º x2 - y2 º (x - y)(x + y)      (mod  m).
For any divisor r of m, we have that
 x(x - y) º x2 - xy º 1     (mod  r)
from which it follows that the greatest common divisor of m and x - y is 1. Therefore, m must divide x + y and the solution can be completed as before.

1.
(b) When m = 2, the result does not hold. The hypothesis is true. However, the conclusion fails when n = 9 since 9 + 1 is a multiple of 2, but 1 + 3 + 9 = 13 is odd.
1.
(c) First solution. By inspection, we find that m = 1, 2, 3, 4, 6, 8, 12, 24 all satisfy the condition in (a).
Suppose that m is odd. Then gcd(2, m) = 1 Þ22 = 4 º 1 (mod m) Þ m = 1, 3.
Suppose that m is not divisible by 3. Then gcd(3, m) = 1Þ 9 = 32 º 1 (mod m) Þm = 1, 2, 4, 8. Hence any further values of m not listed in the above must be even multiples of 3, that is, multiples of 6.
Suppose that m ³ 30. Then, since 25 = 52 ¹ 1 (mod m), m must be a multiple of 5.
It remains to show that in fact m cannot be a multiple of 5. We observe that there are infinitely many primes congruent to 2 or 3 modulo 5. [To see this, let q1, ¼, qs be the s smallest odd primes of this form and let Q = 5q1 ¼qs + 2. Then Q is odd. Also, Q cannot be a product only of primes congruent to ±1 modulo 5, for then Q itself would be congruent to ±1. Hence Q has an odd prime factor congruent to ±2 modulo 5, which must be distinct from q1, ¼, qs. Hence, no matter how many primes we have of the desired form, we can always find one more.] If possible, let m be a multiple of 5 with the stated property and let q be a prime exceeding m congruent to ±2 modulo 5. Then gcd(q, m) = 1 Þ q2 º 1 (mod m) Þ q2 º 1 (mod 5) Þ q \not º ±2 (mod 5), yielding a contradiction. Thus, we have given a complete collection of suitable numbers m.
(c) Second solution. [D. Arthur] Suppose that m = ab satisfies the condition of part (a), where the greatest common divisor of a and b is 1. Let gcd (x, a) = 1. Since a and b are coprime, there exists a number t such that at º 1 - x (mod b), so that z = x + at and b are coprime. Hence, the greatest common divisor of z and ab equals 1, so that z2 º 1 (mod ab), whence x2 º z2 º 1 (mod a). Thus a (and also b) satisfies the condition of part (a).
When m is odd and exceeds 3, then gcd (2, m) = 1, but 22 = 4 \not º 1 (mod m), so m does not satisfy the condition. When m = 2k for k ³ 4, then gcd (3, m) = 1, but 32 = 9 \not º 1 (mod m). It follows from the first paragraph that if m satisfies the condition, it cannot be divisible by a power of 2 exceeding 8 nor by an odd number exceeding 3. This leaves the possibilities 1, 2, 3, 4, 6, 8, 12, 24, all of which satisfy the condition.

2.

2.
(a) First solution. i(i-1)(i-2) ¼(i-m+1) = [([(i+1)-(i-m)])/(m+1)]i(i-1)(i-2) ¼(i-m+1)
 = (i+1)i(i-1) ¼(i-m+1) - i(i-1)(i-2)¼(i-m+1)(i-m)m+1
so that
 n å i = 0 i(i-1)(i-2)¼(i-m+1)
 = n+1 å i = 2 i(i-1)¼(i-m)m+1 - n å i = 1 i(i-1)¼(i-m)m+1
 = (n+1)n(n-1)¼(n-m+1)m+1 - 0
 = (n+1)n(n-1)¼(n-m+1)m+1 .

(a) Second solution. [K. Yeats] Let n = m + k. Then
 n å i = 1 i(i-1)(i-2)¼(i-m+1) = m! + (m+1)!1! + ¼+ n!(n-m)!
 = 1(m+1)k! éê ë (m+1)!k! + (m+1)!k!(m+1)1! + (m+2)!k!(m+1)2! + ¼+ n!(m+1) ùú û
 = (m+1)!(m+1)k! éê ë k! + k!1! (m+1) + k!2! (m+2)(m+1) + ¼+ n(n-1)¼(m+2)(m+1) ùú û .
The quantity in square brackets has the form (with q = 0)
 k!q! + k!(q+1)! (m+1) + k!(q+2)! (m+q+2)(m+1) + k!(q+3)! (m+q+3)(m+q+2)(m+1) + ¼
 + k!k! n(n-1)¼(m+q+2)(m+1)
 = (m+q+2) éê ë k!(q+1)! + k!(q+2)! (m+1) + k!(q+3)! (m+q+3)(m+1)+ ¼+ k!k! n ¼(m+q+3)(m+1) ùú û .
Applying this repeatedly with q = 0, 1, 2, ¼, k-1 leads to the expression for the left sum in the problem of
 (m+k+1)!(m+1)k! éê ë k!k! ùú û = (n+1)!(m+1)(n-m)! = (n+1)n(n-1) ¼(n-m+1)m+1 .
[A variant, due to D. Nicholson, uses an induction on r to prove that, for m £ r £ n,
 r å i = m i(i-1)¼(i-m+1) = (r+1)!(r-m)!(m+1) .]

(a) Third solution. For 1 £ i £ m-1, i(i-1)¼(i-m+1) = 0. For m £ i £ n, i(i-1)¼(i-m+1) = m!(i || m). Also,
 (n+1)n ¼(n-m+1)m+1 = m! æç è n+1 m+1 ö÷ ø
so the statement is equivalent to
 n å m æç è i m ö÷ ø = æç è n+1 m+1 ö÷ ø .
This is clear for n = m. Suppose it holds for n = k ³ m. Then
 k+1 å i = m æç è i m ö÷ ø = æç è k+1 m+1 ö÷ ø + æç è k+1 m ö÷ ø = æç è k+2 m+1 ö÷ ø
and the result follows by induction.

(a) Fourth solution. Use induction on n. If n = 1, then m = 1 and both sides of the equation are equal to 1. Suppose that the result holds for n = k and 1 £ m £ k. Then, for 1 £ m £ k,
 k+1 å i = 1 i(i-1)¼(i-m+1)
 = (k+1)k(k-1)¼(k-m+1)m+1 + (k+1)k(k-1) ¼(k-m+2)
 = (k+1)k(k-1)¼(k-m+2)m+1 [(k-m+1)+ (m+1)]
 = (k+2)(k+1)k(k-1)¼(k-m+2)m+1
as desired. When m = n = k+1, all terms on the left have k+1 terms and so they vanish except for the one corresponding to i = k+1. This one is equal to (k+1)! and so to the right side.

2.
(b) First solution. For 1 £ i £ r £ n, let S(n, r, i) be the sum of the elements ti where (t1, t2, ¼, tr) runs over r-tples with 1 £ t1 < t2 < ¼ < tr £ n. Then S(n, r, i) = (n || r)T(n, r, i). For 1 £ k £ n, 1 £ i £ r, the number of ordered r-tples (t1, t2, ¼, tr) with ti = k is ((k-1) || (i-1))((n-k) || (r-i)) where (0 || 0) = 1 and (a || b) = 0 when b > a. Hence
 æç è n r ö÷ ø = n å k = 1 æç è k-1 i-1 ö÷ ø æç è n-k r-i ö÷ ø .
Replacing n by n+1 and r by r+1 yields a reading
 æç è n+1 r+1 ö÷ ø = n+1 å k = 1 æç è k-1 i-1 ö÷ ø æç è n+1-k r-(i-1) ö÷ ø for  1 £ i £ r+1 .
Replacing i-1 by i yields
 æç è n+1 r+1 ö÷ ø = n+1 å k = 1 æç è k-1 i ö÷ ø æç è n+1-k r-i ö÷ ø for  0 £ i £ r .
When 1 £ i £ r, the first term of the sum is 0, so that
 æç è n+1 r+1 ö÷ ø = n+1 å k = 2 æç è k-1 i ö÷ ø æç è n-(k-1) r-i ö÷ ø = n å k = 1 æç è k i ö÷ ø æç è n-k r-i ö÷ ø .
Thus
 S(n,r,i) = n å k = 1 k æç è k-1 i-1 ö÷ ø æç è n-k r-i ö÷ ø = i n å k = 1 æç è k i ö÷ ø æç è n-k r-i ö÷ ø = i æç è n+1 r+1 ö÷ ø
so
 T(n, r, i) = i n+1r+1 .

2.
(b) Second solution. When r = 1, we have that
 T(n, 1, 1) = 1 + 2 + ¼+ nn = n+12 .
When r = 2, the subsets are {1, 2 }, { 1, 3 }, ¼,{ 1, n} , { 2, 3 }, { 2, 4 }, ¼{ 2, n },¼, { n-1 , n }, so that
 T(n, 2, 1)
= 1 ×(n-1) + 2 ×(n-2) + ¼+ (n-1) ×1
 æç è n 2 ö÷ ø
= [(n-1) + (n-2) + ¼+ 1] + [(n-2) + (n-3) + ¼+ 1]+ ¼+ 1
 æç è n 2 ö÷ ø
=
 n-1 å j = 1 [1 + 2 + ¼+ (n-j)]

n(n-1)/2
=
 n-1 å j = 1 (n-j+1)(n-j)/2

n(n-1)/2
 = (1/6)(n+1)n(n-1)(1/2)n(n-1) = n+13 ,
and
 T(n, 2, 2)
= (n-1)×n + (n-2)×(n-1) + ¼+ 1 ×2
 æç è n 2 ö÷ ø
 = (n+1)n(n-1)/3n(n-1)/2 = 2 æç è n+13 ö÷ ø .
Thus, the result holds for n = 1, 2 and all i, r with 1 £ i £ r £ n, and for all n and 1 £ i £ r £ 2. Suppose as an induction hypothesis, we have established the result up to n-1 and all appropriate r and i, and for n and 1 £ i £ r-1. The r-element subsets of { 1, 2, ¼, n } have ((n-1) || r) instances without n and ((n-1) || (r-1)) instances with n.

Let 1 £ i £ r-1. Then
 T(n, r, i)
=
 æç è n-1 r ö÷ ø T(n-1, r, i) + æç è n-1 r-1 ö÷ ø T(n-1, r-1, i)

 æç è n r ö÷ ø
=
 i[ æç è n-1 r ö÷ ø nr+1 + æç è n-1 r-1 ö÷ ø nr ]

 æç è n r ö÷ ø
=
 i[ æç è n r+1 ö÷ ø + æç è n r ö÷ ø ]

 æç è n r ö÷ ø
= i
 æç è n+1 r+1 ö÷ ø

 æç è n r ö÷ ø
= i n+1
r+1
Also
 T(n, r, r)
=
 æç è n-1 r ö÷ ø T(n-1, r, r) + æç è n-1 r-1 ö÷ ø n

 æç è n r ö÷ ø
=
 æç è n-1 r ö÷ ø rnr+1 + æç è n-1 r-1 ö÷ ø rnr

 æç è n r ö÷ ø
=
 r[ æç è n r+1 ö÷ ø + æç è n r ö÷ ø ]

 æç è n r ö÷ ø
= r æ
ç
è
n+1
r+1
ö
÷
ø
.

(b) Third solution. For 1 £ i £ r £ n, let S(n, r, i) be the sum of the elements ti where (t1, t2, ¼, tr) runs over r-tples with 1 £ t1 < t2 < ¼ < tr £ n. Then S(n, r, i) = (n || r)T(n, r, i). We observe first that
 S(n, r, i) = S(n-1, r-1, i) + S(n-2, r-1, i) + ¼+ S(r-1, r-1, i)
for 1 £ i £ r-1. This is true, since, for each j with 1 £ j £ n-r+1, S(n-j, r-1, i) adds the ti over all r-tples for which tr = n - j + 1.

Now S(n, 1, 1) = 1 + 2 + ¼+ n = 1/2(n+1)n and S(n, 2, 1) = 1/2n(n-1) + ¼+ 1 = [1/3!](n+1)n(n-1). As an induction hypothesis, suppose that S(n, r-1, 1) = [1/r!](n+1)n(n-1)¼(n-r+2). Then
 S(n, r, 1)
 = n-1 å k = r-1 S(k, r-1, 1)
 = 1r! n-1 å k = r-1 (k+1)k(k-1) ¼(k-r+2) = 1r! n å k = 1 k(k-1) ¼(k-r+1)
 = 1(r+1)! (n+1)n(n-1) ¼(n-r+1) = æç è n+1r+1 ö÷ ø n!r!(n-r)! = æç è n+1r+1 ö÷ ø æç è n r ö÷ ø .
Thus, for each r with 1 £ r £ n, S(n, r, 1) = (n || r)(n+1)/(r+1) so that T(n, r, 1) = (n+1)/(r+1).

Let n ³ 2. Suppose that for 1 £ k £ n-1 and 1 £ i £ r £ k, it has been established that S(k, r, i) = iS(k, r, 1). Then for 1 £ i £ r £ n,
 S(n, r, i)
 = S(n-1, r-1, i) + S(n - 2, r-1, i) +¼+ S(r - 1, r- 1, i)
 = i[S(n-1, r-1, 1) + S(n-2, r-1, 1) + ¼+ S(r-1, r-1, 1) = iS(n, r, 1)  .
Dividing by (n || r) yields
 T(n, r, i) = iT(n, r, 1) = i æç è n+1r+1 ö÷ ø .

Comments. (1) There is a one-one correspondence
 (t1, t2, ¼, tr) « (n+1 - tr, n + 1 - tr-1 , ¼, n + 1 - tr)
of the set of suitable r-tples to itself, it follows that
 S(n, r, r)
 = æç è n r ö÷ ø (n+1) -S(n, r, 1) = æç è n r ö÷ ø (n+1) éê ë 1 - 1r+1 ùú û
 = r(n+1)r+1 æç è n r ö÷ ø = rS(n, r, 1)
from which T(n, r, r) = r(n+1)/(r+1) = rT(n, r, 1).

(2) To illustrate another method for getting and using the recursion, we prove first that T(n, r, 2) = 2T(n, r, 1) for 2 £ r £ n. Consider the case r = 2. For 1 £ t1 < t2 £ n, (t1, t2) « (t2 - t1, t2) defines a one-one correspondence between suitable pairs. Since t2 = t1 + (t2 -t1), it follows from this correspondence that S(n, 2, 2) = 2S(n, 2, 1). Dividing by (n || 2) yields T(n, 2, 2) = 2T(n, 2, 1).
Suppose that r ³ 2. For each positive integer j with 1 £ j £ n - r + 1, we define a one-one correspondence between r-tples (t1, t2, ¼, tr) with 1 £ t1 < t2 < ¼ < tr £ n and t3 - t2 = j and (r-1)-tples (s1, s2, s3, ¼, sr) = (t1, t2, t4 - j, ¼, tr - j) with 1 £ s1 = t1 < s2 = t2 < s3 = t4 - j < ¼ < sr = tr - j £ n - j. The sum of the elements t2 over all r-tples with t3 - t2 = j is equal to the sum of t2 over all the (r - 1)-tples. Hence
 S(n, r, 2) = S(n - 1, r - 1, 2) + S(n - 2, r - 1, 2) + ¼+ S(r - 1, r - 1, 2)  .

More generally, for 1 £ j £ n - r - 1, there is a one-one correspondence between r-tples (t1, t2, ¼, tr) with ti+1 - ti = j and (r - 1)-tples (s1, s2, ¼, sr-1) = (t1, ¼, ti, ti+2 - j, ¼, tr - j) with 1 £ s1 = t1 < ¼ < si = ti < si+1 = ti+2 - j < ¼ < sr-1 = tr - j £ n - j. We now use induction on r. We have that
 S(n, r, i)
 = S(n-1, r-1, i) + S(n - 2, r-1, i) +¼+ S(r - 1, r- 1, i)   .

(b) Fourth solution. [Y. Shen] We establish that
 i+(n-r) å k = i æç è k i ö÷ ø æç è n-k r-i ö÷ ø = æç è n+1 r+1 ö÷ ø .
Consider the (r+1)-element sets where ti+1 = k+1 and tr+1 £ n + 1. We must have i £ k £ n - (r-i) and there are (k || i)((n-k) || (r-i)) ways of selecting t1, ¼, ti and ti+2, ¼, tr+1. The desired equation follows from a counting argument over all possibilities for ti+1.

In a similar way, we note that ti = k for ((k-1) || (i-1))((n-k) || (r-i)) sets { t1, ¼, tr } chosen from {1, ¼, n }, where 1 £ k £ n-r+1. Observe that
 æç è k-1 i-1 ö÷ ø æç è n-k r-i ö÷ ø = ik æç è k i ö÷ ø æç è n-k r-i ö÷ ø .
Then
 T(n, r, i)
=
 n-r+1 å k = i k æç è k-1 i-1 ö÷ ø æç è n-k r-i ö÷ ø

 æç è n r ö÷ ø
=
 i n-r+i å k = i æç è k i ö÷ ø æç è n-k r-i ö÷ ø

 æç è n r ö÷ ø
=
 æç è n+1 r+1 ö÷ ø

 æç è n r ö÷ ø
= i æ
ç
è
n+1
r+1
ö
÷
ø
.

(b) Fifth solution. [Christopher So] Note that
 n-r+i å k = i æç è k i ö÷ ø æç è n-k r-i ö÷ ø
is the coefficient of xi yr-i in the polynomial
 n-r+i å k = i (1 + x)k (1 + y)n-k
or in
 n+1 å k = 0 (1 + x)k (1 + y)n-k
 = (1 + y)n+1 - (1 + x)n+1y - x
=
 n+1 å j = 0 æç è n+1 j ö÷ ø (yj - xj)

y-x
.
Now the only summand which involves terms of degree r corresponds to j = r+1, so that the coefficient of xi yr-1 in the sum is the coefficient in the single term
 æç è n+1 r+1 ö÷ ø yr+1 - xr+1y-x
namely, ((n+1) || (r+1)). We can now complete the argument as in the fourth solution.

(b) Comment. Let r and n be fixed values and consider i to be variable. The (n || r) r-term sets contain altogether r (n || r) numbers, each number occurring equally often: r/n(n || r) times. The sum of all the elements in the set is
 S(n, r, 1) + S(n, r, 2) + ¼+ S(n, r, r) = rn æç è n r ö÷ ø (1 + 2 + ¼+ n) = r(n+1)2 æç è n r ö÷ ø
where S(n, r, i) is the sum of the elements ti over the (n || r) subsets. The ordered r-element subsets (t1, t2, ¼, tr) can be mapped one-one to themselves by
 (t1, t2, ¼, tr) « (n+1 - tr, n+1 - tr-1, ¼, n + 1 - t1) .
From this, we see that, for 1 £ r,
 S(n, r, r+1-i) = æç è n r ö÷ ø (n+1) - S(n, r, i)
so that
 S(n, r, 1) + S(n, r, r) = S(n, r, 2) + S(n, r, r-1) = ¼ = S(n, r, i) + S(n, r, r + 1 - i) = ¼ = æç è n r ö÷ ø (n+1) .
This is not enough to imply that S(n, r, i) is an arithmetic progression in i, but along with this fact would give a quick solution to the problem.

3.

3.
First solution. Dividing the inequality through by (b+a)/2 yields the equivalent inequality
1 £ n æ
ú
Ö

 b¢n+1 - a¢n+1(b¢- a¢)(n+1)

£ n æ
ú
Ö

 a¢n + b¢n2

with a¢ = (2a)/(b+a) and b¢ = (2b)/(b+a). Note that (a¢+ b¢)/2 = 1, and we can write b¢ = 1 + u and a¢ = 1 - u with 0 < u < 1. The central term becomes the nth root of
 (1+u)n+1 - (1 - u)n+12(n+1)u
=
 2[(n+1)u + æç è n+1 3 ö÷ ø u3 + æç è n+1 5 ö÷ ø u5 + ¼]

2(n+1)u
 = 1 + 13 æç è n 2 ö÷ ø u2 + 15 æç è n 4 ö÷ ø u4 +¼
which clearly exceeds 1 and gives the left inequality. The right term becomes the nth root of
 12 [(1 + u)n + (1 - u)n ] = 1 + æç è n 2 ö÷ ø u2+ æç è n 4 ö÷ ø u4 + ¼
and the right inequality is clearly true.

3.
Second solution. The inequality
n æ
ú
Ö

 bn+1 - an+1(b-a)(n+1)

£ n æ
ú
Ö

 an + bn2

is equivalent to
 0 £ (n+1)(an + bn) - 2(bn+1 - an+1)b-a .
The right side is equal to
 (n+1)(an + bn)
 - 2(bn + bn-1a + bn-2a2 ¼+ b2 an-2 + ban-1 + an)
 = (an - bn) + (an - bn-1a) + (an - bn-2a) + ¼+ (an - b an-1) + (an - an)
 + (bn - bn) +(bn - bn-1a) + ¼+ (bn - ban-1) + (bn - an)
 = (an - bn) + a(an-1 - bn-1) + a2(an-2 - bn-2) +¼+ an-1(a - b) + 0
 + 0 + bn-1(b - a) + ¼+ b(an-1 - an-1) + (bn - an)
 = 0 + (b-a)(bn-1 - an-1) + (b2 - a2)(bn-2 - an-2)+ ¼+ (bn-1 - an-1)(b - a)
 > 0 .

The left inequality
b+a
2
£ n æ
ú
Ö

 bn+1 - an+1(b-a)(n+1)

is equivalent to
 æç è b+a2 ö÷ ø n £ bn+1 - an+1(b-a)(n+1) .
Let v = 1/2(b-a) so that b + a = 2(a + v). Then
 bn+1 - an+1(b-a)(n+1) - æç è b+a2 ö÷ ø n
 = (a+2v)n+1 - an+1(b-a)(n+1) - (a + v)n
 = 12v(n+1) æç è n+1 å k = 1 æç è n+1 k ö÷ ø an+1-k (2v)k ö÷ ø - (a + v)n
 = 1n+1 æç è n+1 å k = 1 æç è n+1 k ö÷ ø an-(k-1) (2v)k-1 ö÷ ø - (a + v)n
 = 1n+1 æç è n å k = 0 æç è n+1 k+1 ö÷ ø an-k (2v)k ö÷ ø - n å k = 0 æç è n k ö÷ ø an-k vk
 = æç è n å k = 0 1k+1 æç è n k ö÷ ø an-k (2v)k - n å k = 0 æç è n k ö÷ ø an-k vk ö÷ ø
 = n å k = 0 æç è 2kk+1 - 1 ö÷ ø æç è n k ö÷ ø an-k vk ³ 0  ,
since 2k = (1 + 1)k = 1 + k + (k || 2) + ¼ ³ 1 + k with equality if and only if k = 0 or 1. The result follows.

3.
Third solution. [D. Nicholson] (partial) Let n ³ 2i + 1. Then
 (bn-iai + bi an-i) - (bn-i-1ai+1 + bi+1an-i-1) = (b - a)ai bi (bn-2i-1 - an-2i-1) ³ 0 .
Hence, for 0 £ j £ 1/2(n+1),
 bn + an ³ bn-1a + abn-1 ³ ¼ ³ bn-jaj +bj an-j  .
When n = 2k+1,
 bn + bn-1a + ¼+ ban-1 + an = k å i = 0 (bn-iai + bi an-i) £ (k+1)(bn + an) = n+12 (bn + an)
and when n = 2k, we use the Arithmetic-Geometric Means Inequality to obtain bk ak £ 1/2(a2k + b2k), so that
 bn + bn-1a + ¼+ ban-1 + an = k-1 å i = 0 (bn-i ai + bi an-i) + bk ak £ k(bn + an) + bn + an2 = n+12 (bn + an) .
Hence
 bn+1 - an+1(b-a)(n+1) £ bn + an2 .

3.
Fourth solution. [Y. Shen] Let 1 £ k £ n and 1 £ i £ k. Then
 (bk+1 + ak+1) - (bi ak+1-i + ai bk+1-i) = (bi - ai)(bk+1-i - ak+1-i) ³ 0 .
Hence
 k(bk+1 + ak+1) ³ k å i = 1 (bi ak+1-i + ai bk+1-i) = 2 k å i = 1 bi ak+1-i  .
This is equivalent to
 (2k+2) k+1 å i = 0 bi ak+1-i
 = (2k + 2)(bk+1 + ak+1) + (2k + 2) k å i = 1 bi ak+1-i
 ³ (k+2) (bk+1 + ak+1) + (2k + 4) k å i = 1 bi ak+1-i
 = (k + 2) (bk+1 + 2 k å i = 1 bi ak+1-i + ak+1)
 = (k + 2) (b + a) k å i = 0 bi ak-i
which in turn is equivalent to
 k+1 å i = 0 bi ak+1-i

k+2
³
 (b+a)( k å i = 0 bi ak-i)

2(k+1)
.
We establish by induction that
 æç è b+a2 ö÷ ø n £ 1n+1 n å i = 0 bi an-i
which will yield the left inequality. This holds for n = 1. Suppose that it holds for n = k. Then
 æç è b+a2 ö÷ ø
 = æç è b+a2 ö÷ ø · æç è b+a2 ö÷ ø k
 £ æç è b+a2 ö÷ ø · æç è 1k+1 ö÷ ø k å i = 0 bi ak-i £ 1k+2 k+1 å i = 0 bi ak-i   .

As above, we have, for k = n-1,
 (n-1)(bn + an) ³ 2 n-1 å i = 1 bi an-i
so that
 (n+1)(bn + an) ³ 2 n å i = 0 bi an-i = 2 æç è bn+1 - an+1b-a ö÷ ø
from which the right inequality follows.

3.
Comment. The inequality
b+a
2
£ n æ
ú
Ö

 bn+1 - an+1(b-a)(n+1)

is equivalent to
 0 £ 2n(bn+1 - an+1)b - a - (n+1)(b+a)n .
When n = 1, the right side is equal to 0. When n = 2, it is equal to
 4(b2 + ba + a2) - 3(b + a)2 = (b - a)2 > 0 .
When n = 3, we have
 8(b3 + b2a + ba2 + a3) - 4(b + a)3 = 4b3 - 4b2a - 4ba2 + 4a3 = 4(b2 - a2)(b - a) = 4(b + a)(b - a)2 > 0 .
When n = 4, 5 and 6, the right side is, respectively,
 (11b2 + 18ab + 11a2)(b - a)2
 (26b3 + 54b2a + 54ba2 + 26a3)(b - a)2
 (57b4 + 136b3a + 174b2a2 + 136ba3 + 57a4)(b - a)2 .
There is a pattern here; can anyone express it in a general way that will yield the result, or at least show that the right side is the product of (b - a)2 and a polynomial with positive coefficients?

4.

4.
First solution.
 8 sinacosacos2acos4a = 4 sin2 acos2acos4a = 2 sin4acos4a = sin8a  .
Hence the given equation is equivalent to sin8a = sina with sina ¹ 0. Hence, we must have a+ 8a = p, 8a = 2p+ a or 8a = 3p- a, since a lies strictly between 0 and p/2. These lead respectively to a = p/9 (20°), a = 2p/ 7 and a = p/3 (60°). Thus, there are three acute angles a for which the equation is satisfied.

Comment. Alternatively, note that
 0 = sin8a- sina = 2sin 7a2 cos 9a2
whence 7a = 2p or 9a = p or 3p.

Second solution. Let x = cosa. Then cos2a = 2x2 - 1 and cos4a = 2(2x2 - 1)2 - 1 = 8x4 - 8x2 + 1, so that
 cosacos2acos4a = x(2x2 - 1)(8x4 - 8x2 + 1)  .
Let f(x) = x(2x2 - 1)(8x4 - 8x2 + 1) - 1/8. Using the fact that a = p/3 corresponding to x = 1/2 is an obvious solution of the equation f(x) = 0, we find that
 8f(x)
 = 128x7 - 192x5 + 80x3 - 8x - 1
 = (2x - 1)(64x6 + 32x5 - 80x4 - 40x3 + 20x2 + 10x + 1)  .
Consider the factor
 g(x)
 = 64x6 + 32x5 - 80x4 - 40x3 + 20x2 + 10x + 1
 = (2x + 1)(32x5 - 40x3 + 10x) + 1  .
By Descartes' Rule of Signs, g(x) = 0 has at most two positive roots (there are two changes of signs as one reads along the coefficients from left to right). Now g(1) = 7, g(1/2) = 3 and g(3/4) = (5/2)([(-177)/32]) + 1 < 0. Hence g(x) = 0 has precisely two roots, one in each of the intervals (1/2, 3/4) and (3/4, 1). These along with x = 1/2, constitute the three roots of f(x) = 0. Since all roots lie in (0, 1), they are cosines of acute angles a for which cosacos2acos4a = 1/8.

Comment. g(x) = (8x3 + 4x2 - 4x - 1)(8x3 - 6x - 1). By Descartes' Rule of Signs, each factor has one positive root, and since each is negative for x = 0 and positive for x = 1, that root must lie between 0 and 1. We need to dispose of the possibility that both factors have the same root. If c is such a common root, then 8c3 + 8c2 - 4c - 1 = 8c3 - 6c - 1 = 0 Þ8c2 + 2c = 0 which yields a contradiction.
Third solution. [A. Birka] An obvious solution is a = p/3. Observe that the product cosacos2acos4a vanishes exactly when a = p/8 and a = p/4. On the interval [0, p/8], cosa, cos2a, cos4a are all nonnegative and decreasing, so the product decreases from 1 to 0. Hence, by the Intermediate Value Theorem and the continuity of the functions, cosacos2acos4a = 1/8 has precisely one solution in this interval. On the interval (p/8, p/4), cosa and cos2a are positive and cos4a is negative, so there are no solutions. Similarly, on the interval (3p/8, p/2), cosa and cos4a are positive and cos2a is negative, so there are no solutions. Hence any remaining solutions must lie in (p/4, 3p/8), where cosa > 0, cos2a < 0 and cos4a < 0.
We need a preliminary result. Suppose that u(a) and v(a) are nonnegative twice differentiable functions on an open interval (a, b) such that u(a) is increasing, v(a) is decreasing and both functions are concave (i.e., have negative second derivative). Then u(a) v(a) is also concave. This follows immediately from (uv)¢¢ = u¢¢v + 2u¢v¢+ uv¢¢.
Apply this to the interval ([( p)/4], [(p)/3]) and u(a) = -cos2a, v(a) = cosa to obtain that u(a) v(a) is concave. Observe that u(a)v(a) is nonnegative and
 (uv)¢(a)
 = [cosa(-cos2a)]¢ = (cosa- 2cos3 a)¢
 = sina(6cos2 a- 1) ³ 12 sina(6 cos2 p3 - 1) = 14 sina > 0
so u(a) v(a) is increasing.

On the interval ([(p)/4], [(p)/3]), -cos4a is nonnegative, decreasing and concave, so we can apply the result again with u(a) = -cosacos2a and v(a) = -cos4a to obtain that f(a) º cosacos2acos4a is nonnegative and concave on ([(p)/4], [(p)/3]). It can be checked that f([(p)/4]) = 0, f([(p)/3]) = 1/8 and f¢([(p)/3]) = -3 Ö3/8 < 0, so an analysis of the graph reveals exactly one solution of f(a) = 1/8 for p/4 < a < p/3.
Finally, we consider p/ 3 < a < 3p/ 8. If g(a) º cos2acos4a = 2 cos3 2a- cos2a, then g¢(a) = 2sin2a[1 - 6cos2 2 a] < 0, so g(a) is positive and decreasing on ([(p)/3],[(3p)/8]). Since g(p/ 3) = 1/4, it follows that f(a) < (cosa) /4 < 1/8 for p/3 < a < 3p/8. The result follows.
Comment: It is interesting that the three solutions, given in increasing order of complexity, with the second requiring some sophisticated algebraic machinery and the last a reasonably sophisticated analysis, are also increasingly loath to provide information. The first solution is not only the easiest, but in fact allows us to explicitly state the values of a. In the second solution, we at least have the tools to make some kind of approximation to the solutions, although the one corresponding to the factor (2x - 1) can be given exactly. The analytic theory (intermediate value theorem) in the third solution just tells us that some interval has a solution without specifying very exactly where.

5.

5.
First solution. Let the figure be denoted by F and the circle by C, and let r be the central reflection through the centre of the circle. Suppose that m is any line of support for F and that it intersects the circle in P and Q. Then there are lines p and q through P and Q respectively, perpendicular to m, which support F. Let p meet the circle in P and R, and q meet it in Q and S; let t be the line RS. Since PQRS is concyclic with adjacent right angles, it is a rectangle, and t is a line of support of F. Since PS and RQ are both diameters of C, it follows that S = r(P), R = r(Q) and t = r(m).
Hence, every line of support of F is carried by r into a line of support of F. We note that F must be on the same side of its line of support as the centre of the circle.
Suppose that X Î F. Let Y = r(X). Suppose, if possible that Y \not Î F. Then there must be a disc containing Y that does not intersect F, so we can find a line m of support for F such that F is on one side and Y is strictly on the other side of m. Let n = r(m). Then n is a line of support for F which has X = r(Y) on one side and O = r(O) on the other. But this is not possible. Hence Y Î F and so r(F) Í F. Now r°r is the identity mapping, so F = r(r(F)) Í r(F). It follows that F = r(F) and the result follows.
Second solution. Let P be any point on the circle C. There are two perpendicular lines of support from P meeting the circle in Q and S. As in the first solution, we see that P is one vertex of a rectangle PQRS each of whose sides supports F. Let G be the intersection of all the rectangles as P ranges over the circumference of the circle C. Since each rectangle has central symmetry about the centre of C, the same is true of G. It is clear that F Í G. It remains to show that G Í F. Suppose a point X in G does not belong to F. Then there is a line r of support to F for which X and F are on opposite sides. This line of support intersects C at the endpoints of a chord which must be a side of a supporting rectangle for F. The point X lies outside this rectangle, and so must lie outside of G. The result follows.
Third solution. [D. Arthur] If the result is false, then there is a line through the centre of the circle such that OP > OQ, where P is where the line meets the boundary of the figure on one side and Q is where it meets the boundary on the other. Let m be the line of support of the figure through Q. Then, as shown in Solution 1, its reflection t in the centre of the circle is also a line of support. But then P and O lie on opposite sides of t and we obtain a contradiction. 6.

6.
(a) First solution. Wolog, suppose that the situation is as diagrammed. ÐBAC = ÐAUT = ÐAVT = 90°, so that AUVT is a rectangle with AU = AV and UT = VT. Hence AUTV is a square with diagonals AT and UV which right-bisect each other at W. Since SW right-bisects AT, by reflection in the line SW, we see that DASU º DUST, and so ÐUTS = ÐUAS.
Let M be the midpoint of BC. Then M is the circumcentre of DABC, so that MA = MC and ÐMCA = ÐMAC. Since AS is tangent to the circumcircle of DABC, AS ^AM. Hence
 ÐUTS = ÐUAS = ÐSAM - ÐBAM = 90°- ÐBAM = ÐMAC = ÐMCA .
Now UT ^AB implies that UT || AC. Since ÐUTS = ÐACB, it follows that ST || BC.

(a) Second solution. Wolog, suppose that S is on the opposite side of AB to C.
BT, being a part of the diameter produced of the inscribed circle, is a line of reflection that takes the circle to itself and takes the tangent BA to BC. Hence ÐUBT = 1/2ÐABC. Let a = ÐABT. By the tangent-chord theorem applied to the circumscribed circle, ÐXAC = ÐABC = 2a, so that ÐSAU = 90° - 2a.
Consider triangles SAU and STU. Since AUTV is a square (see the first solution), AU = UT and ÐAUV = ÐTUV = 45° so ÐSUA = ÐSUT = 135°. Also SU is common. Hence DSAU º DSTU, so ÐSTU = ÐSAU = 90° - 2a. Therefore,
 ÐSTB = ÐUTB - ÐSTU = (90° - a)- (90° - 2a) = a = ÐTBC
from which it results that ST || BC.

(a) Third solution. As before DAUS º DTUS, so ÐSAU = ÐSTU. Since UT || AC, ÐSTU = ÐSYA. Also, by the tangent-chord theorem, ÐSAB = ÐACB. Hence ÐSYA = ÐSTU = ÐSAB = ÐACB, so ST || BC.
(a) ³Fourth solution. In the Cartesian plane, let A ~ (0, 0), B ~ (0, -b), C ~ (c, 0). The centre of the circumscribed circle is at M ~ (c/2, -b/2). Since the slope of AM is -b/c, the equation of the tangent to the circumscribed circle through A is y = (c/b)x. Let r be the radius of the inscribed circle. Since AU = AV, the equation of the line UV is y = x - r. The abscissa of S is the solution of x - r = (cx)/b, so S ~ ([br/(b-c)], [cr/(b-c)]). Since T ~ (r, -r), the slope of ST is b/c and the result follows. 6.
(b) First solution. [¼] denotes area. Wolog, suppose that d1 > d2, as diagrammed.
Let r be the inradius of DABC. Then [AVU] = 1/2r2, [AVS] = 1/2rd1 and [AUS] = 1/2rd2. From [AVU] = [AVS] - [AUS], it follows that r2 = rd1 - rd2, whence r = d1 - d2.
(b) Second solution. [F. Crnogorac] Suppose that the situation is as diagrammed. Let P and Q be the respective feet of the perpendiculars from S to AC and AB. Since ÐPVS = 45° and ÐSPV = 90°, DPSV is isosceles and so PS = PV = PA + AV = SQ + AV, i.e., d1 = d2 + r.
(b) Third solution. Using the coordinates of the fourth solution of (a), we find that
 d1 = êê ê crb-c êê ê and          d2 = êê ê brb-c êê ê
whence |d2 - d1 | = r as desired.

(b) Fourth solution. [M. Boase] Wolog, assume that the configuration is as diagrammed.
Since ÐSUB = ÐAUV = 45°, SU is parallel to the external bisector of ÐA. This bisector is the locus of points equidistant from AB and CA produced. Wolog, let PS meet this bisector in W, as in the diagram. Then PW = PA so that PS - PA = PS - PW = SW = AU and thus d1 - d2 = r. top of page | contact us | privacy | site map |     © Canadian Mathematical Society, 2019 : https://cms.math.ca/