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

a_k

where a₁, a₂, ¼, a_n are all positive integers.

Solution 1. The sum cannot exceed å_k=1ⁿ k = ¹/₂n(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 ¹/₂n(n+1) inclusive. Observe that 1 is representable for any n (for example, by making each a_k equal to kn). Also, ¹/₂n(n+1) is representable, by taking a₁ = a₂ = ¼ = a_n. Thus, the result holds for n = 1 and n = 2.

Suppose that it holds for n = m ³ 2. Then, by taking a_m+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 ¹/₂m(m+1) + 1 = (m² + m + 2)/2 inclusive can be represented with a (m+1)- term sum. By taking a_m+1 = 1 and appending m + 1 to each integer representable by an m-term sum, we find that each integer between m+2 and ¹/₂m(m+1) + (m+1) = ¹/₂(m+1)(m+2) can be represented with an (m+1)-term sum. Since [(m² + m + 2)/2] - (m+2) = ¹/₂(m² - m - 2) = ¹/₂(m - 2)(m+1) ³ 0 for m ³ 2, ¹/₂(m² + m + 2) ³ m+2. Thus, we can represent all numbers between 1 and ¹/₂(n+1)(n+2) inclusive. The result follows.

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

Proof. T_k is the entire set when k = ¹/₂n(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 < ¹/₂n(n+1). Then T_m-1 must lack at least one number. If 1 Ï T_m-1, let T_m = T_m-1 È{ 1 }. If 1 Î T_m-1, let i > 1 be the least number not in T_m-1. Then let T_m = T_m-1 È{ i + 1 } \{ i }. ª

Now to the result. Let 2 £ k £ ¹/₂n(n+1) be given and determine T_k-1. Define a_i = 1 when i Î T_k-1 and a_i = ¹/₂n(n+1) - (k-1) when i Ï T_k-1. Then

ì
í
î

a_i

: i Ï T_k-1

ü
ý
þ

é
ë

æ
è

n+1
2

ö
ø

- (k-1)

ù
û

-1

{ i : i Ï T_k-1 }

é
ë

æ
è

n+1
2

ö
ø

- (k-1)

ù
û

-1

é
ë

æ
è

n+1
2

ö
ø

{ i : i Î T_k-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 { a₁, a₂, ¼, a_n } 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

a_k, a_k + a_k+1, a_k + a_k+1 + a_k+2, ¼,a_k + a_k+1 + ¼+ a_n

is positive. Prove that

{ a_k : 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 { a₁, a₂, ¼, a_m } is given. If a₁ Ï S, then å{ a_k : k Î S } > 0, by the induction hypothesis applied to the (m-1)-element set { a₂, ¼, a_m}. Suppose that a₁ Î S and that r is the smallest index for which a₁ + a₂ + ¼+ a_r > 0. Then, for 1 £ i £ r - 1, a₁ + ¼+ a_i £ 0 and so

(a_i+1 + ¼+ a_r) = (a₁ + ¼+ a_r)- (a₁ + ¼+ a_i) > 0 ,

i.e., a₂, a₃, ¼, a_r Î S. Hence å{ a_k : 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 { a_r+1, ¼, a_m }, we have that å{ a_k : 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) - x³ is an increasing function. Must f(x) - x - x² also be increasing?

Solution. The answer is no. Consider f(x) = x³ + x. Then x = f(x) - x³ is increasing, but g(x) = f(x) - x - x² = x³ - x² is not. Indeed, g(0) = 0 while g(¹/₂) = -¹/₈ < 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 |²- |WZ |² = |XY |² - |XZ |².

Proof. Note that

2 (

®
W

®
X

)·(

®
Z

®
Y

) = (

®
Y

®
W

)² - (

®
Z

®
W

)²- (

®
Y

®
X

)²+ (

®
Z

®
X

)² . ª .

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

|KL |² - |KN |²

= (|KA |² + |AL |²) - (|KC |² +|CN |²) = |KA² |- |KC |²

= (|BK |² - |AB |²) - (|BK |²- |BC |²) = |BC |² - |AB |² .

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 |² - |IN |² = (|IU |² + |UL |²) - (|IV |²+ |VN |²) = |UL |² - |VN |² = |BC |² - |AB |² ,

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 A₁, A₅, A₇, A₁₁, A₁₂ 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

sinÐCAO ·sinÐADB ·sinÐDCE

sinÐOAD ·sinÐBDC ·sinÐECA

(

)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 = ¹/₂ÐAEB = 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 { a_n } be a sequence of real numbers for which a₁ = 1/2 and, for n ³ 1,

a_n+1 =

a_n²

a_n² - a_n + 1

Prove that, for all n, a₁ + a₂ + ¼+ a_n < 1.

Solution. Let b_n = 1/a_n for n ³ 1, whence b₁ = 2 and b_n+1 = b_n² - bⁿ + 1 = b_n(b_n - 1) + 1 for n ³ 1. Then { b_n } is an increasing sequence of integers and

b_n

b_n - 1

b_n+1 - 1

for n ³ 1. Hence

a₁ + a₂ + ¼+ a_n

b₁

b₂

+ ¼+

b_n

é
ë

b₁ - 1

b₂ - 1

ù
û

é
ë

b₂ - 1

b₃ - 1

ù
û

+ ¼+

é
ë

b_n - 1

b_n+1 - 1

ù
û

b₁ - 1

b_n+1 - 1

= 1 -

b_n+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] =

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

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

= [BCM] = [DAN]

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

= [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 kÖ2 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 kÖ2 from the diagonal; such a point would lie on a midline of the square. The condition is that 2k + Ö2(kÖ2) < ¹/₂ or k < ¹/₈. On the other hand, we can give a configuration in which each area is at least equal to k and some areas are exactly ¹/₈. This would have M and N on the same midline, each equidistant from an edge and the centre of the square.