CMS/SMC
Société mathématique du Canada
www.smc.math.ca
Société mathématique du Canada
  location: 
       

Solutions for November Problems


Notes. A real-valued function f(x) of a real variable is increasing if and only if u < v implies that f(u) f(v). The circumcircle of a triangle is that circle that passes through its three vertices; its centre is the circumcentre of the triangle. The incircle of a triangle is that circle that is tangent internally to its three sides; its centre is the incentre of the triangle.
346.
Let n be a positive integer. Determine the set of all integers that can be written in the form
n

k=1 
 k

ak
where a1, a2, , an are all positive integers.
Solution 1. The sum cannot exceed k=1n k = 1/2n(n+1). We prove by induction that the set of integers that can be written in the required form consists of the integers from 1 to 1/2n(n+1) inclusive. Observe that 1 is representable for any n (for example, by making each ak equal to kn). Also, 1/2n(n+1) is representable, by taking a1 = a2 = = an. Thus, the result holds for n = 1 and n = 2.

Suppose that it holds for n = m 2. Then, by taking am+1 = m + 1 and appending (m+1)/(m+1) to each integer representable by an m-term sum, we find that each integer between 2 and 1/2m(m+1) + 1 = (m2 + m + 2)/2 inclusive can be represented with a (m+1)- term sum. By taking am+1 = 1 and appending m + 1 to each integer representable by an m-term sum, we find that each integer between m+2 and 1/2m(m+1) + (m+1) = 1/2(m+1)(m+2) can be represented with an (m+1)-term sum. Since [(m2 + m + 2)/2] - (m+2) = 1/2(m2 - m - 2) = 1/2(m - 2)(m+1) 0 for m 2, 1/2(m2 + m + 2) m+2. Thus, we can represent all numbers between 1 and 1/2(n+1)(n+2) inclusive. The result follows.

Solution 2. [Y. Zhao] Lemma. For any integer k with 1 k 1/2n(n+1), there is a subset Tk of { 1, 2, , n } for which the sum of the numbers in Tk is k.

Proof. Tk is the entire set when k = 1/2n(n+1). For the other values of k, we give a proof by induction on k. A singleton suffices for 1 k n. Suppose that the result holds for k = m - 1 < 1/2n(n+1). Then Tm-1 must lack at least one number. If 1 Tm-1, let Tm = Tm-1 { 1 }. If 1 Tm-1, let i > 1 be the least number not in Tm-1. Then let Tm = Tm-1 { i + 1 } \{ i }.

Now to the result. Let 2 k 1/2n(n+1) be given and determine Tk-1. Define ai = 1 when i Tk-1 and ai = 1/2n(n+1) - (k-1) when i Tk-1. Then




 i

ai
: i Tk-1

=

n+1
2

- (k-1)
-1

 

{ i : i Tk-1 }
=

n+1
2

- (k-1)
-1

 


n+1
2

-
{ i : i Tk-1
= 1 .
Since one can give a representation for 1 and since no number exceeding ((n+1) || 2) can be represented, it follows that the set of representable integers consists of those between 1 and ((n+1) || 2) inclusive.
347.
Let n be a positive integer and { a1, a2, , an } a finite sequence of real numbers which contains at least one positive term. Let S be the set of indices k for which at least one of the numbers
ak, ak + ak+1, ak + ak+1 + ak+2, ,ak + ak+1 + + an
is positive. Prove that

{ ak : k S } > 0 .
Solution. We prove the result by induction on n. When n = 1, the result is obvious. Let m 2 and suppose that the result holds for all n m-1. Suppose a suitable sequence { a1, a2, , am } is given. If a1 S, then { ak : k S } > 0, by the induction hypothesis applied to the (m-1)-element set { a2, , am}. Suppose that a1 S and that r is the smallest index for which a1 + a2 + + ar > 0. Then, for 1 i r - 1, a1 + + ai 0 and so
(ai+1 + + ar) = (a1 + + ar)- (a1 + + ai) > 0 ,
i.e., a2, a3, , ar S. Hence { ak : 2 k r } > 0. If there are no elements of S that exceed r. then the desired conclusion follows. Otherwise, by the induction hypothesis applied to the (m-r)- element set { ar+1, , am }, we have that { ak : k S, r+1 k m } > 0. The desired conclusion follows.

Comment. Most solvers had much more elaborate solutions which essentially used this idea. No one recognized that the proliferation of cases could be sidestepped by the technical use of an induction argument.


348.
Suppose that f(x) is a real-valued function defined for real values of x. Suppose that f(x) - x3 is an increasing function. Must f(x) - x - x2 also be increasing?
Solution. The answer is no. Consider f(x) = x3 + x. Then x = f(x) - x3 is increasing, but g(x) = f(x) - x - x2 = x3 - x2 is not. Indeed, g(0) = 0 while g(1/2) = -1/8 < 0.

Comment. See Problem 348.(b) included with the February set.


349.
Let s be the semiperimeter of triangle ABC. Suppose that L and N are points on AB and CB produced (i.e., B lies on segments AL and CN) with |AL | = |CN | = s. Let K be the point symmetric to B with respect to the centre of the circumcircle of triangle ABC. Prove that the perpendicular from K to the line NL passes through the incentre of triangle ABC.
Let the incentre of the triangle be I.

Solution 1. Let P be the foot of the perpendicular from I to AK, and Q the foot of the perpendicular from I to CK. Since BK is a diameter of the circumcircle of triangle ABC, BAK = BCK = 90 and IP || BA, IQ || BC. Now |IP | = s - a = |BN |, |IQ | = s - c = |BL | and PIQ = ABC = NBL, so that DIPQ DBNL (SAS). Select R on IP and S on IQ (possibly produced) so that IR = IQ, IS = IP. Thus, DISR DBNL and RS || NL (why?). Since IPKQ is concyclic, KIP + IRS = KIP+ IQP = KIP + IKP = 90. Therefore IK is perpendicular to RS, and so to NL.

Solution 2. Lemma. Let W, X, Y, Z be four points in the plane. Then WX ^YZ if and only ig |WY |2- |WZ |2 = |XY |2 - |XZ |2.

Proof. Note that

2 (
W
 
-
X
 
)·(
Z
 
-
Y
 
) = (
Y
 
-
W
 
)2 - (
Z
 
-
W
 
)2- (
Y
 
-
X
 
)2+ (
Z
 
-
X
 
)2 .  .

Since BK is a diameter of the circumcircle, LAK = NCK = 90. We have that

|KL |2 - |KN |2
= (|KA |2 + |AL |2) - (|KC |2 +|CN |2) = |KA2 |- |KC |2
= (|BK |2 - |AB |2) - (|BK |2- |BC |2) = |BC |2 - |AB |2 .
Let U and V be the respective feet of the perpendiculars from I to BA and BC. Observe that |AU | = |BN | = s - a, |CV | = |BL | = s - c and |BU | = |BV | = s - b, so that |UL | = |BC | = a, |VN | = |AB | = c. Then
|IL |2 - |IN |2 = (|IU |2 + |UL |2) - (|IV |2+ |VN |2) = |UL |2 - |VN |2 = |BC |2 - |AB |2 ,
which, along with the lemma, implies the result.
350.
Let ABCDE be a pentagon inscribed in a circle with centre O. Suppose that its angles are given by B = C = 120, D = 130, E = 100. Prove that BD, CE and AO are concurrent.
Solution 1. [P. Shi; Y. Zhao] The vertices ABCDE are the vertices A1, A5, A7, A11, A12 of a regular 18-gon. (Since A,B,C,D,E lie on a circle, the position of the remaining vertices are determined by that of A are the angle sizes. Alternatively, look at the angles subtended at the centre by the sides of the pentagon.) Since the sum of the angles of a pentagon is 540, A = 70. Since AED > 90, D and E lie on the same side of the diameter through A, and B and C lie on the other side. Thus, the line AO produced intersects the segment CD. Consider the triangle ACD for which AO produced, BD and CE are cevians. We apply the trigonometric version of Ceva's theorem.

We have that CAO = 30, ADB = 40, DCE = 10, OAD = 10, BDC = 20 and ECA = 70. Hence

 sinCAO ·sinADB ·sinDCE

sinOAD ·sinBDC ·sinECA
=
(  1

2
)sin40 sin10

sin10 sin20 sin70
=  cos20

sin70
= 1 .
Hence the three lines AO, BD and CE are concurrent as desired.

Solution 2. [C. Sun] Let BD and CE intersect at P. We can compute the following angles: EAB = EBA = 70, AEB = 40, BEP = PDC = 20, EBP = PCD = 10, PBC = PED = 40, BCP = EDP = 110 and BPC = EPD = 30. Since triangle ABE is acute, the circumcentre O of it (and the pentagon) lie in its interior, and AOB = 1/2AEB = 80. Since triangle ABE is isosceles, BAO = ABO = 50.

Let Q be the foot of the perpendicular from E to AB and R the foot of the perpendicular from B to EP produced. Since DEQB DERB (ASA), QB = RB. Since BPR = 30, PBR = 60 and PB = 2RB = 2QB = AB. Hence ABP is isosceles with apex ABP = 80. Thus, BAP = BPA = 50. Hence BAO = BAP = 50, so that AO must pass through P and the result follows.


351.
Let { an } be a sequence of real numbers for which a1 = 1/2 and, for n 1,
an+1 =  an2

an2 - an + 1
 .
Prove that, for all n, a1 + a2 + + an < 1.
Solution. Let bn = 1/an for n 1, whence b1 = 2 and bn+1 = bn2 - bn + 1 = bn(bn - 1) + 1 for n 1. Then { bn } is an increasing sequence of integers and
 1

bn
=  1

bn - 1
-  1

bn+1 - 1
for n 1. Hence
a1 + a2 + + an
=  1

b1
+  1

b2
+ +  1

bn
=
 1

b1 - 1
-  1

b2 - 1

+
 1

b2 - 1
-  1

b3 - 1

+ +
 1

bn - 1
-  1

bn+1 - 1

=  1

b1 - 1
-  1

bn+1 - 1
= 1 -  1

bn+1 - 1
< 1 .

352.
Let ABCD be a unit square with points M and N in its interior. Suppose, further, that MN produced does not pass through any vertex of the square. Find the smallest value of k for which, given any position of M and N, at least one of the twenty triangles with vertices chosen from the set { A, B, C, D, M, N } has area not exceeding k.
Solution 1. Wolog, suppose that M lies in the interior of triangle ABN. Then
[ABM] + [AMN] + [BMN] + [CND] = [ABN] + [CND] =  1

2
 ,
so that at least one of the four triangles on the left has area not exceeding 1/8. Hence k 1/8. We give a configuration for which each of the twenty triangles has area not less than 1/8, so that k = 1/8.

Suppose that M and N are both located on the line joining the midpoints of AD and BC with M distant 1/4 from the side AD and N distant 1/4 from the side BC. Then

 1

4
= [ABM] = [CDM] = [ABN] = [CDN]

 3

8
= [BCM] = [DAN]

 1

2
= [ABC] = [BCD] = [CDA] = [DAB]

 1

8
= [DAM] = [BCN] = [AMN] = [BMN] = [CMN] = [DMN] = [AMC] = [ANC] = [BMD] = [BND] .

Solution 2. [L. Fei] Suppose that all triangle have area exceed k. Then M and N must be in the interior of the square distant more than 2k from each edge to ensure that areas of triangles like ABM exceed k. Similarly, M and N must be distant more than k2 from the diagonals of the square. For points M and N to be available that satisfy both conditions, we need to find a point that is distant at least 2k from the edges and k2 from the diagonal; such a point would lie on a midline of the square. The condition is that 2k + 2(k2) < 1/2 or k < 1/8. On the other hand, we can give a configuration in which each area is at least equal to k and some areas are exactly 1/8. This would have M and N on the same midline, each equidistant from an edge and the centre of the square.


© Société mathématique du Canada, 2014 : http://smc.math.ca/