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

Solutions and comments.



79.
Let x0 , x1 , x2 be three positive real numbers. A sequence { xn } is defined, for n0 by

xn+3 = xn+2 + xn+1 +1 xn .

Determine all such sequences whose entries consist solely of positive integers.
Solution 1. Let the first three terms of the sequence be x, y, z. Then it can be readily checked that the sequence must have period 8, and that the entries cycle through the following:

x,y,z, y+z+1 x , x+y+z+1+xz xy ,


(x+y+1)(y+z+1) xyz , x+y+z+1+xz yz , x+y+1 z .

For all of these entries to be positive integers, it is necessary that y+z+1 be divisible by x, x+y+1 be divisible by z and (x+1)(z+1) be divisible by y. In particular, xy+z+1 and zx+y+1.
Without loss of generality, we can assume that the smallest entry in the sequence is y. Then,

y+z+1 x y

and

x+y+1 z y

whence

xy2 =y(xy)y(y+z+1) = y2 +yz+y y2 +x+y+1+y =x+(y+1)2 .

Hence

x( y2 -1)(y+1)2

so that either y=1 or

yx y+1 y-1 =1+ 2 y-1 .

The latter yields (y-1)2 2 so that y2.
Suppose that y=1. Then xy+z+1=z+2y+x+3=x+4. Since x divides x and y+z+1, it must divide their difference, which cannot exceed 4. Hence x=y+z+1 or x must be one of 1, 2, 3, 4. Similarly, z=x+y+1 or z must be one of 1, 2, 3, 4.
If x=y+z+1=z+2, then x+y+1=z+4 and so z divides 4. We get the periods

(3,1,1,1,3,5,9,5)


(4,1,2,1,4,3,8,3)


(6,1,4,1,6,2,9,2).

The case z=x+y+1 yields essentially the same periods. Otherwise, 1x,z4 and we find the additional possible period

(2,1,2,2,5,4,5,2)

For each period, x0 can start anywhere.
Suppose that y=2. Then xy+z+1z+3x+6, so that x must divide some number not exceeding 6. Similarly, z cannot exceed 6. If x=2, then x+y+1=5 and so z=5; this yields the period (2,2,5,4,5,2,2,1) already noted. If x=3, then z must be 2, 3 or 6, and we obtain (3,2,3,2,3,2,3,2); the possibilities z=2,6 do not work. If x=4, z=7, which does not work. If x=5, then z=2,4 and we get a period already noted. If x=6, then z=3, which does not work.
Hence there are five possible cycles and the sequence can begin at any term in the cycle:

(1,1,1,3,5,9,5,3)


(1,2,1,4,3,8,3,4)


(1,2,2,5,4,5,2,2)


(1,4,1,6,2,9,2,6)


(2,3,2,3,2,3,2,3)

Solution 2. [O. Ivrii] We show that the sequence contains a term that does not exceed 2. Suppose that none of x0 , x1 and x2 is less than 3. Let k= max ( x1 , x2 ). Then, noting that k is an integer and that k3, we deduce that

x3 = x1 + x2 +1 x0 2k+1 3 <k

so x3 k-1 and

x4 = x2 + x3 +1 x1 2k 3 k-1

so that max ( x3 , x4 )=k-1. If k-13, we repeat the process to get a strictly lower bound on the next two terms. Eventually, we obtain two consecutive terms whose maximum is less than 3. In fact, we can deduce that there is an entry equal to either 1 or 2 arbitrarily far out in the sequence.
Suppose, from some point on in the sequence, there is no term equal to 1. Then there are three consecutive terms a,2,b. The previous term is (a+3)/b and the following term is (b+3)/a, so that a divides b+3 and b divides a+3. Since a-3ba+3, b divides two numbers that differ by at most 6; similarly with a. Hence, neither a nor b exceeds 6. Testing out possibilities leads to (a,b)=(6,3),(5,2),(3,3).
Finally, we suppose that the sequence has three consecutive terms a,1,b and by similar arguments are led to the sequences obtained in the first solution.
Comment. C. Lau established that xn xn+4 = xn+2 xn+6 and thereby obtained the periodicity. R. Barrington Leigh showed that, if all terms of the sequence were at least equal to 2, then the sequence { yn } defined by yn = max ( xn , xn+1 ) satisfies yn+1 yn . Since the same recursion defines the sequence ``going backwards'', we also have yn-1 yn , for all n. Hence { yn } is a constant sequence, and so { xn } is either constant or has period 2. It is straightforward to rule out the constant possibility. If the periodic segment of the sequence is (a,b), then b=(a+b+1)/a or (a-1)(b-1)=2 and we are led to the segment (2,3). Otherwise, there is a 1 in the sequence and we can conclude as before.


80.
Prove that, for each positive integer n, the series

k=1 kn 2k

converges to twice an odd integer not less than (n+1)!.
Solution 1. Since the series consists of nonnegative terms, we can establish its convergence by eventually showing that it is dominated term by term by a geometric series with common ratio less than 1. Noting that nklogk (3/2) for k sufficiently large, we find that for large k, kn <(3/2)k and the kth term of the series is dominated by (3/4)k . Thus the sum of the series is defined for each nonnegative integer n.
For nonnegative integers n, let

Sn = k=1 kn 2k .

Then S0 =1 and

Sn - 1 2 Sn = k=1 kn 2k - k=1 kn 2k+1 = k=1 kn 2k - k=1 (k-1)n 2k = k=1 kn -(k-1)n 2k = k=1 [( n 1 ) kn-1 2k -( n 2 ) kn-2 2k +( n 3 ) kn-3 2k -+(-1)n-1 1 2k ]

whence

Sn =2 [( n 1 ) Sn-1 -( n 2 ) Sn-2 +( n 3 ) Sn-3 -+(-1)n-1 ].

An induction argument establishes that Sn is twice an odd integer.
Observe that S0 =1, S1 =2, S2 =6 and S3 =26. We prove by induction that, for each n0,

Sn+1 (n+2) Sn

from which the desired result will follow. Suppose that we have established this for n=m-1. Now

Sm+1 =2 [( m+1 1 ) Sm -( m+1 2 ) Sm-1 +( m+1 3 ) Sm-2 -( m+1 4 ) Sm-3 + ].

For each positive integer r,

( m+1 2r-1 ) Sm-2r+2 -( m+1 2r ) Sm-2r+1 [( m+1 2r-1 )(m-2r+3)-( m+1 2r ) ] Sm-2r+1 =( m+1 2r-1 )[(m-2r+3)- ( m-2r+2 2r ) ] Sm-2r+1 0.

When r=1, we get inside the square brackets the quantity

(m+1)- m 2 = m+2 2

while when r>1, we get

(m-2r+3)- ( m-2r+2 2r )>(m-2r+3)-(m-2r+2)=1.

Hence

Sm+1 2 [( m+1 1 ) Sm -( m+1 2 ) Sm-1 ] 2 [(m+1) Sm - m(m+1) 2 · 1 m+1 Sm ] =2 [m+1- m 2 ] sm =(m+2) Sm .


Solution 2. Define Sn as in the foregoing solution. Then, for n1,

Sn = 1 2 + k=2 kn 2k = 1 2 + 1 2 k=1 (k+1)n 2k = 1 2 + 1 2 k=1 kn +( n 1 ) kn-1 ++( n n-1 )k+1 2k = 1 2 + 1 2 [ Sn +( n 1 ) Sn-1 ++( n n-1 ) S1 +1 ]

whence

Sn =( n 1 ) Sn-1 +( n 2 ) Sn-2 ++( n n-1 ) S1 +2.

It is easily checked that Sk 2 (mod 4) for k=0,1. As an induction hypothesis, suppose this holds for 1kn-1. Then, modulo 4, the right side is congruent to

2[ k=0 n( n k )-2]+2=2( 2n -2)+2= 2n+1 -2,

and the desired result follows.
For n1,

Sn+1 Sn = ( n+1 1 ) Sn +( n+1 2 ) Sn-1 ++( n+1 n ) S1 +2 Sn =(n+1)+ ( n+1 2 ) Sn-1 +( n+1 3 ) Sn-2 ++(n+1) S1 +2 ( n 1 ) Sn-1 +( n 2 ) Sn-2 ++ nS1 +2 (n+1)+1=n+2,

since each term in the numerator of the latter fraction exceeds each corresponding term in the denominator.

Solution 3. [of the first part using an idea of P. Gyrya] Let f(x) be a differentiable function and let D be the differentiation operator. Define the operator L by

L(f)(x)=x·D(f)(x).

Suppose that f(x)=(1-x)-1 = k=0 xk . Then, it is standard that Ln (f)(x) has a power series expansion obtained by term-by-term differentiation that converges absolutely for x<1. By induction, it can be shown that the series given in the problem is, for each nonnegative integer n, Ln (f)(1/2).
It is straightforward to verify that

L((1-x)-1 )=x(1-x)-2


L2 ((1-x)-1 )=x(1+x)(1-x)-3


L3 ((1-x)-1 )=x(1+4x+ x2 )(1-x)-4


L4 ((1-x)-1 )=x(1+11x+11 x2 + x3 )(1-x)-5 .

In general, a straightforward induction argument yields that for each positive integer n,

Ln (f)(x)=x(1+ an,1 x++ an,n-2 xn-2 + xn-1 )(1-x)-(n+1)

for some integers an,1 ,, an,n-2 . Hence

Ln (f)(1/2)=2( 2n-1 + an,1 2n-2 ++ an,n-2 2+1),

yielding the desired result.


81.
Suppose that x1 and that x=x+{x}, where x is the greatest integer not exceeding x and the fractional part {x} satisfies 0x<1. Define

f(x)= x+{x} x .

(a) Determine the smallest number z such that f(x)z for each x1.
(b) Let x0 1 be given, and for n1, define xn =f( xn-1 ). Prove that limn xn exists.
81. Solution. (a) Let x=y+z, where y=x and z={x}. Then

f(x)2 =1+ 2yz y+z ,

which is less than 2 because yz 1 2 (y+z) by the arithmetic-geometric means inequality. Hence 0f(x)2 for each value of x. Taking y=1, we find that

limx2 f(x)2 = limz1 (1+ 2z 1+z )=2,

whence sup{f(x):x1}=2.
(b) In determining the fate of { xn }, note that after the first entry, the sequence lies in the interval [1,2). So, without loss of generality, we may assume that 1 x0 <2. If xn =1, then each xn =1 and the limit is 1. For the rest, note that f(x) simplifies to (1+x-1)/x on (1,2). The key point now is to observe that there is exactly one value v between 1 and 2 for which f(v)=v, f(x)>x when 1<x<v and f(x)<x when v<x<2. Assume these facts for a moment. A derivative check reveals that f(x) is strictly increasing on (1,2), so that for 1<x<v, x<f(x)<f(v)=v, so that the iterates { xn } constitute a bounded, increasing sequence when 1< x0 <v which must have a limit. (In fact, this limit must be a fixed point of f and so must be v.) A similar argument shows that, if v< x0 <2, then the sequence of iterates constitute a decreasing convergent sequence (with limit v).
It remains to show that a unique fixed point v exists. Let x=1+u with u>0. Then it can be checked that f(x)=x if and only if 1+2u+u=1+3u+3 u2 + u3 or u5 +6 u4 +13 u3 +12 u2 +4u-4=0. Since the left side is strictly increasing in u, takes the value -4 when u=0 and the value 32 when u=1, the equation is satified for exactly one value of u in (0,1); now let v=1+u. The value of V turns out to be about 1.375, (Note that f(x)>x if and only if x<u.)


82.
(a) A regular pentagon has side length a and diagonal length b. Prove that

b2 a2 + a2 b2 =3.

(b) A regular heptagon (polygon with seven equal sides and seven equal angles) has diagonals of two different lengths. Let a be the length of a side, b be the length of a shorter diagonal and c be the length of a longer diagonal of a regular heptagon (so that a<b<c). Prove that:

a2 b2 + b2 c2 + c2 a2 =6

and

b2 a2 + c2 b2 + a2 c2 =5.


82. Solution 1. (a) Let ABCDE be the regular pentagon, and let triangle ABC be rotated about C so that B falls on D and A falls on E. Then ADE is a straight angle and triangle CAE is similar to triangle BAC. Therefore

a+b b = b a b a - a b =1 b2 a2 + a2 b2 -2=1

so that b2 / a2 + a2 / b2 =3, as desired.
(b) Let A,B,C,D,E be consecutive vertices of the regular heptagon. Let AB, AC and AD have respective lengths a, b, c, and let BAC=θ. Then θ=π/7, the length of BC, of CD and of DE is a, the length of AE is c, CAD=DAE=θ, since the angles are subtended by equal chords of the circumcircle of the heptagon, ADC=2θ, ADE=AED=3θ and ACD=4θ. Triangles ABC and ACD can be glued together along BC and DC (with C on C) to form a triangle similar to ΔABC, whence

a+c b = b a .             (1)

Triangles ACD and ADE can be glued together along CD and ED (with D on D) to form a triangle similar to ΔABC, whence

b+c c = b a .             (2)

Equation (2) can be rewritten as 1 b = 1 a - 1 c . whence

b= ac c-a .

Substituting this into (1) yields

(c+a)(c-a) ac = c c-a

which simplifies to

a3 - a2 c-2 ac2 + c3 =0.             (3)

Note also from (1) that b2 = a2 +ac.

a2 b2 + b2 c2 + c2 a2 -6 = a4 c2 + b4 a2 + c4 b2 -6 a2 b2 c2 a2 b2 c2 = a4 c2 +( a4 +2 a3 c+ a2 c2 ) a2 + c4 ( a2 +ac)-6 a2 c2 ( a2 +ac) a2 b2 c2 = a6 +2 a5 c-4 a4 c2 -6 a3 c3 + a2 c4 + ac5 a2 b2 c2 = a( a2 +3ac+ c2 )( a3 - a2 c-2 ac2 + c3 ) a2 b2 c2 =0`.


b2 a2 + c2 b2 + a2 c2 -5 = ( a4 +2 a3 c+ a2 c2 ) c2 + a2 c4 + a4 ( a2 +ac)-5 a2 c2 ( a2 +ac) a2 b2 c2 = a6 + a5 c-4 a4 c2 -3 a3 c3 +2 a2 c4 a2 b2 c2 = a2 (a+2c)( a3 - a2 c-2 ac2 + c3 ) a2 b2 c2 =0.

Solution 2. (b) [R. Barrington Leigh] Let the heptagon be ABCDEFG; let AD and BG intersect at P, and BF and CG intersect at Q. Observe that PD=GE=b, AP=c-b, GP=DE=a, BP=b-a, GQ=AB=a, CQ=c-a. From similarity of triangles, we obtain the following:

a c = c-b a a c - c a + b a =0(ΔAPG~ΔADE)


c-a a = c b c a - c b =1(ΔQBC~ΔCEG)


c-b a = b-a b c a - b a + a b =1(ΔAPG~ΔDPB)


b-a a = b c b a - b c =1(ΔABP~ΔADB).

Adding these equations in pairs yields

b a + a c - c b =1 b2 a2 + a2 c2 + c2 b2 +2 ( b c - c a - a b )=1

and

c a + a b - b c =2 c2 a2 + a2 b2 + b2 c2 +2 ( c b - b a - a c )=4.

The desired result follows from these equations.
Solution 3. (b) [of the second result by J. Chui] Let the heptagon be ABCDEFG and θ=π/7. Using the Law of Cosines in the indicated triangles ACD and ABC, we obtain the following:

cos2θ= a2 + c2 - b2 2ac = 1 2 ( a c + c a - b2 ac )


cos5θ= 2 a2 - b2 2 a2 =1- 1 2 ( b a )2

from which, since cos2θ=-cos5θ,

-1+ 1 2 ( b a )2 = 1 2 ( a c + c a - b2 ac )

or

b2 a2 =2+ a c + c a - b2 ac .             (1)

Examining triangles ABC and ADE, we find that cosθ=b/2a and cosθ=(2 c2 - a2 )/(2 c2 )=1-( a2 /2 c2 ), so that

a2 c2 =2- b a .             (2)

Examining triangles ADE and ACF, we find that cos3θ=a/2c and cos3θ=(2 b2 - c2 )/(2 b2 ), so that

c2 b2 =2- a c .             (3)

Adding equations (1), (2), (3) yields

b2 a2 + c2 b2 + a2 c2 =6+ c2 -bc- b2 ac .

By Ptolemy's Theorem, the sum of the products of pairs of opposite sides of a concylic quadrilaterial is equal to the product of the diagonals. Applying this to the quadrilaterals ABDE and ABCD, respectively, yields c2 = a2 +bc and b2 =ac+ a2 , whence c2 -bc- b2 = a2 +bc-bc-ac- a2 =-ac and we find that

b2 a2 + c2 b2 + a2 c2 =6-1=5.

Solution 4. [of the second result by X. Jin] By considering isosceles triangles with side-base pairs (a,b), (c,a) and (b,c), we find that b2 =2 a2 (1-cos5θ), a2 =2 c2 (1-cosθ), c2 =2 b2 (1-cos3θ), where θ=π/7. Then

b2 a2 + c2 b2 + a2 c2 =2[3-(cosθ+cos3θ+cos5θ)].

Now,

sinθ(costheta+cos3θ+cos5θ) = 1 2 [sin2θ+(sin4θ-sin2θ)+(sin6θ-sin4θ)] = 1 2 sin6θ= 1 2 sinθ,

so that cosθ+cos3θ+cos5θ=1/2. Hence b2 / a2 + c2 / b2 + a2 / c2 =2(5/2)=5.
Solution 5. (b) There is no loss of generality in assuming that the vertices of the heptagon are placed at the seventh roots of unity on the unit circle in the complex plane. Then ζ=cos(2π/7)+isin(2π/7) be the fundamental seventh root of unity. Then ζ7 =1, 1+ζ+ ζ2 ++ ζ6 =0 and (ζ, ζ6 ), ( ζ2 , ζ5 ), ( ζ3 , ζ4 ) are pairs of complex conjugates. We have that

a=ζ-1= ζ6 -1


b= ζ2 -1= ζ9 -1


c= ζ3 -1= ζ4 -1.

It follows from this that

b a =ζ+1 c b = ζ2 +1 a c = ζ3 +1,

whence

b2 a2 + c2 b2 + a2 c2 =(ζ+1)( ζ6 +1)+( ζ2 +1)( ζ5 +1)+( ζ3 +1)( ζ4 +1) =2+ζ+ ζ6 +2+ ζ2 + ζ5 +2+ ζ3 + ζ4 =6+(ζ+ ζ2 + ζ3 + ζ4 + ζ5 + ζ6 )=6-1=5.

Also

a b = ζ4 + ζ2 +1 b c = ζ6 + ζ3 +1 c a = ζ2 +ζ+1,

whence

a2 b2 + b2 c2 + c2 a2 =( ζ4 + ζ2 +1)( ζ3 + ζ5 +1)+( ζ6 + ζ3 +1)(ζ+ ζ4 +1)+( ζ2 +ζ+1)( ζ5 + ζ6 +1) =(3+2 ζ2 + ζ3 + ζ4 +2 ζ5 )+(3+ζ+2 ζ3 +2 ζ4 + ζ6 )+(3+2ζ+ ζ2 + ζ5 +2 ζ6 ) =9+3(ζ+ ζ2 + ζ3 + ζ4 + ζ5 + ζ6 )=9-3=6.

Solution 6. (b) Suppose that the circumradius of the heptagon is 1. By considering isosceles triangles with base equal to the sides or diagonals of the heptagon and apex at the centre of the circumcircle, we see that

a =2sinθ=2sin6θ=-2sin8θ b =2sin2θ=-2sin9θ c =2sin3θ=2sin4θ

where θ=π/7 is half the angle subtended at the circumcentre by each side of the heptagon. Observe that

cos2θ= 1 2 (ζ+ ζ6 )cos4θ= 1 2 ( ζ2 + ζ5 )cos6θ= 1 2 ( ζ3 + ζ4 )

where ζ is the fundamental primitive root of unity. We have that

b a =2cosθ=2cos6θ c b =2cos2θ a c =-2cos4θ

whence

b2 a2 + c2 b2 + a2 c2 =4cos2 6θ+4cos2 2θ+4cos2 4θ =( ζ3 + ζ4 )2 +(ζ+ ζ6 )2 +( ζ2 + ζ5 )2 = ζ6 +2+ζ+ ζ2 +2+ ζ5 + ζ4 +2+ζ=6-1=5.

Also

a b = sin6θ sin2θ =4cos2 2θ-1=(ζ+ ζ6 )2 -1=1+ ζ2 + ζ5 - b c = sin9θ sin3θ =4cos2 3θ-1=4cos2 4θ-1=( ζ2 + ζ5 )2 -1=1+ ζ4 + ζ3 c a = sin3θ sinθ =4cos2 6θ-1=( ζ3 + ζ4 )2 -1=1+ ζ6 +ζ,

whence

a2 b2 + b2 c2 + c2 a2 =(3+2 ζ2 + ζ3 + ζ4 +2 ζ5 )+(3+ζ+2 ζ3 +2 ζ4 + ζ6 )+(3+2ζ+ ζ2 + ζ5 +2 ζ6 ) =9+3(ζ+ ζ2 + ζ3 + ζ4 + ζ5 + ζ6 )=9-3=6.



83.
Let \frakC be a circle with centre O and radius 1, and let \frakF be a closed convex region inside \frakC. Suppose from each point on \frakC, we can draw two rays tangent to \frakF meeting at an angle of 60ˆ . Describe \frakF.
Solution. Let A be an arbitrary point on the circumference of \frakC. Draw rays AC, AB, BD tangent to \frakF; let AC and BD intersect at P. Since CAB=ABD= 60ˆ , APM= 60ˆ and ΔAPB is equilateral and contains \frakF. Suppose, if possible, that P lies strictly inside the circle. Let CE be the second ray from C tangent to \frakF. Then ACE= 60ˆ , so CE is parallel to DB and lies strictly on the opposite side of BD to \frakF; thus, it cannot be tangent to \frakF and we have a contradiction. Similarly, if P lies strictly outside the circle, the second ray from C, CE, tangent to \frakF is parallel to and distinct from BD. We have that \frakF is tangent to AC, BD and CE, an impossibility since DE, within the circle, lies between CE and DB.
Hence C=D=P and ABC is an equilateral triangle containing \frakF with all its sides tangent to \frakF. Since A is arbitrary, \frakF is contained within the intersection of all such triangles, namely the circle \frakD with centre O and radius 1/2, and every chord of the given circle tangent to \frakF has length 3. If \frakF were a proper subset of \frakD, there would be a point Q on the circumference of \frakD outside \frakF. and a tangent of \frakF separating \frakF from Q. This tangent chord would intersect the interior of \frakD and so be longer than 3, yielding a contradiction. Hence \frakF must be the circle \frakD.


84.
Let ABC be an acute-angled triangle, with a point H inside. Let U, V, W be respectively the reflected image of H with respect to axes BC, AC, AB. Prove that H is the orthocentre of ΔABC if and only if U, V, W lie on the circumcircle of ΔABC,
Solution 1. Suppose that H is the orthocentre of ΔABC. Let P, Q, R be the respective feet of the altitudes from A, B, C. Since BC right bisects HU, ΔHBPΔUBP and so HBP=UBP. Thus

ACB =QCB= 90ˆ -QBC= 90ˆ -HBP = 90ˆ -UBP=PUB=AUB,

so that ABUC is concyclic and U lies on the circumcircle of ΔABC. Similarly V and W lie on the circumcircle.
Now suppose that U,V,W lie on the circumcircle. Let \frak C1 , \frak C2 , \frak C3 be the respective reflections of the circumcircle about the axes BC, CA, AB. These three circles intersect in the point H. If H' is the orthocentre of the triangle, then by the first part of the solution, the reflective image of H' about the three axes lies on the circumcircle, so that H' belongs to \frak C1 , \frak C2 , \frak C3 and H=H' or else HH' is a common chord of the three circles. But the latter does not hold, as the common chords AH, BH and CH of pairs of the circles intersect only in H.
Solution 2. Let H be the orthocentre, and P, Q, R the pedal points as defined in the first solution. Since ARHQ is concyclic

BAC+BUC=BAC+BHC=RAQ+RHQ= 180ˆ

and so ABUC is concyclic. A similar argument holds for V and W.
[A. Lin] Suppose that U, V, W are on the circumcircle. >From the reflection about BC, BCU=BCH. >From the reflections about BA and BC, we see that BW=BH=BU, and so, since the equal chords BW and BU subtend equal angles at C, BCW=BCU. Hence BCW=BCH, with the result that C,H,W are collinear and CW is an altitude. Similarly, AU and BV are altitudes that contain H, and so their point H of intersection must be the orthocentre.

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