1.

(a) Let m be any positive integer greater than 2, such that x² º 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.

2.

(a) Prove that, for each pair (m, n) of integers with 1 £ m £ n,

(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 t_i denote the ith smallest element in the subset, and let T(n, r, i) denote the arithmetic mean of the elements t_i. Prove that

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

4.

How many distinct acute angles a are there for which cosacos2acos4a = 1/8?

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.

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) |d₁ - d₂ | = r, where r is the radius of the inscribed circle and d₁ and d₂ are the respective distances from S to AC and AB.

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 = r². Then gcd(r, m) = 1. Hence r² º 1 (mod m). But r² + 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 d² = 1 + bm for some integer b. Also n + 1 = cm for some integer c. Hence

Hence

(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, x² º 1 (mod m), so that

(a) Third solution. [M. Boase] As in the second solution, if xy = n, then x² º y² º 1 (mod m) so that

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 Þ2² = 4 º 1 (mod m) Þ m = 1, 3.

Suppose that m is not divisible by 3. Then gcd(3, m) = 1Þ 9 = 3² º 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 = 5² ¹ 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 q₁, ¼, q_s be the s smallest odd primes of this form and let Q = 5q₁ ¼q_s + 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 q₁, ¼, q_s. 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 Þ q² º 1 (mod m) Þ q² º 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 z² º 1 (mod ab), whence x² º z² º 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 2² = 4 \not º 1 (mod m), so m does not satisfy the condition. When m = 2^k for k ³ 4, then gcd (3, m) = 1, but 3² = 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.

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

(a) Second solution. [K. Yeats] Let n = m + k. Then

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

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

2.

(b) First solution. For 1 £ i £ r £ n, let S(n, r, i) be the sum of the elements t_i where (t₁, t₂, ¼, t_r) runs over r-tples with 1 £ t₁ < t₂ < ¼ < t_r £ 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 (t₁, t₂, ¼, t_r) with t_i = k is ((k-1) || (i-1))((n-k) || (r-i)) where (0 || 0) = 1 and (a || b) = 0 when b > a. Hence

2.

(b) Second solution. When r = 1, we have that

Let 1 £ i £ r-1. Then

(b) Third solution. For 1 £ i £ r £ n, let S(n, r, i) be the sum of the elements t_i where (t₁, t₂, ¼, t_r) runs over r-tples with 1 £ t₁ < t₂ < ¼ < t_r £ n. Then S(n, r, i) = (n || r)T(n, r, i). We observe first that

Now S(n, 1, 1) = 1 + 2 + ¼+ n = ¹/₂(n+1)n and S(n, 2, 1) = ¹/₂n(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

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,

Comments. (1) There is a one-one correspondence

(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 £ t₁ < t₂ £ n, (t₁, t₂) « (t₂ - t₁, t₂) defines a one-one correspondence between suitable pairs. Since t₂ = t₁ + (t₂ -t₁), 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 (t₁, t₂, ¼, t_r) with 1 £ t₁ < t₂ < ¼ < t_r £ n and t₃ - t₂ = j and (r-1)-tples (s₁, s₂, s₃, ¼, s_r) = (t₁, t₂, t₄ - j, ¼, t_r - j) with 1 £ s₁ = t₁ < s₂ = t₂ < s₃ = t₄ - j < ¼ < s_r = t_r - j £ n - j. The sum of the elements t₂ over all r-tples with t₃ - t₂ = j is equal to the sum of t₂ over all the (r - 1)-tples. Hence

More generally, for 1 £ j £ n - r - 1, there is a one-one correspondence between r-tples (t₁, t₂, ¼, t_r) with t_i+1 - t_i = j and (r - 1)-tples (s₁, s₂, ¼, s_r-1) = (t₁, ¼, t_i, t_i+2 - j, ¼, t_r - j) with 1 £ s₁ = t₁ < ¼ < s_i = t_i < s_i+1 = t_i+2 - j < ¼ < s_r-1 = t_r - j £ n - j. We now use induction on r. We have that

(b) Fourth solution. [Y. Shen] We establish that

In a similar way, we note that t_i = k for ((k-1) || (i-1))((n-k) || (r-i)) sets { t₁, ¼, t_r } chosen from {1, ¼, n }, where 1 £ k £ n-r+1. Observe that

(b) Fifth solution. [Christopher So] Note that

(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

3.

First solution. Dividing the inequality through by (b+a)/2 yields the equivalent inequality

3.

Second solution. The inequality

The left inequality

3.

Third solution. [D. Nicholson] (partial) Let n ³ 2i + 1. Then

3.

Fourth solution. [Y. Shen] Let 1 £ k £ n and 1 £ i £ k. Then

As above, we have, for k = n-1,

3.

Comment. The inequality

4.

First solution.

Comment. Alternatively, note that

Second solution. Let x = cosa. Then cos2a = 2x² - 1 and cos4a = 2(2x² - 1)² - 1 = 8x⁴ - 8x² + 1, so that

Comment. g(x) = (8x³ + 4x² - 4x - 1)(8x³ - 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 8c³ + 8c² - 4c - 1 = 8c³ - 6c - 1 = 0 Þ8c² + 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

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]) = ¹/₈ 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 cos³ 2a- cos2a, then g¢(a) = 2sin2a[1 - 6cos² 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.

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.

(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

(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 = ¹/₂Ð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,

(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 d₁ > d₂, as diagrammed.

Let r be the inradius of DABC. Then [AVU] = ¹/₂r², [AVS] = ¹/₂rd₁ and [AUS] = ¹/₂rd₂. From [AVU] = [AVS] - [AUS], it follows that r² = rd₁ - rd₂, whence r = d₁ - d₂.

(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., d₁ = d₂ + r.

(b) Third solution. Using the coordinates of the fourth solution of (a), we find that

(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 d₁ - d₂ = r.