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

Solutions and Comments


Write your solutions to be read. You may have to rework and re-edit your solution to make the argument clear, close gaps in the reasoning, define symbols used and present ideas in logical order. Always check your work. It is too easy to miscopy or misrepresent a symbol and to make a computational mistake. In a competition, your goal is to maximize the number of points you receive. In the following solutions, [AZ] represents the area of the figure AZ, dist (A,BC) is the perpendicular distance from point A to line BC, and dist (a,b) is the perpendicular distance between parallel lines a and b.


13.
Suppose that x1 , x2 ,, xn are nonnegative real numbers for which x1 + x2 ++ xn < 1 2 . Prove that

(1- x1 )(1- x2 )(1- xn )> 1 2 ,

Comments. Some of you tried a ``moving variables'' argument, or an ``extreme case'' argument, i.e., if we make xi as large as possible, we reduce the product, so that if it works for ( x1 , x2 ,, xn )=( 1 2 ,0,0,,0), then we are in business. Some felt that if it works for the extreme case with each xi =1/2n, then we are ok. Unless you back this up with solid argument and detailed analysis that relates the general case to the extreme case, then it is worthless. ``Moving variable'' arguments are always risky and best avoided. Both approaches often muddy the situation rather than clarify it.
Solution 1. If 0<u,v<1, then

(1-u)(1-v)=1-(u+v)+uv>1-(u+v).

It can be shown by induction that

(1- x1 )(1- x2 )(1- xk )>1-( x1 + x2 ++ xk )

for 2kn, whence

(1- x1 )(1- xn )>1-( x1 ++ xn )> 1 2 .

Comments. You should carry out the necessary induction argument. Note that the problem asks for > rather than .
Solution 2. [R. Barrington Leigh] Let

tk ={ x i1 x 12 x ik :1 i1 < i2 << ik n}

for 1kn. Then

(1- x1 )(1- x2 )(1- xn )=1- t1 + t2 - t3 + t4 -+(-1)n tn .

For 1kn-1, we have that

tk ={ x i1 x i2 x ik :1 i1 < i2 << ik n} >{ x i1 x i2 x ik ( x ik +1 + x ik +2 ++ xn ):1 i1 < i2 << ik n}= tk+1

so that

(1- x1 )(1- x2 )(1- xn )=(1- t1 )+( t2 - t3 )+>(1- t1 )=1-( x1 ++ xn )> 1 2 .



14.
Given a convex quadrilateral, is it always possible to determine a point in its interior such that the four line segments joining the point to the midpoints of the sides divide the quadrilateral into four regions of equal area? If such a point exists, is it unique?
Note. Let ABCD be the quadrilateral and let P,Q,R,S be the respective midpoints of AB, BC, CD, DA. Recall that PSQR and PQSR (prove it!).
Solution 1. Observe that [APS]= 1 4 [ABD] and [CRQ]= 1 4 [CDB], so that [APS]+[CRQ]= 1 4 [ABCD] (why?). Since

[ABCD]= 1 2 BD·(dist(A,BD)+dist(C,BD))


[APS]= 1 4 BD·dist(A,PS)


[CRQ]= 1 4 BD·dist(C,QR)

we have that

dist(A,PS) +dist(C,QR)= 1 2 [dist(A,BD)+dist(C,BD) =dist(PS,QR).

Hence it is possible to draw a line m parallel to and between PS and QR for which dist (m,QR) = dist (A,PS) and dist (m,PS) = dist (C,QR). For any point M on m, we have that [MQR]=[APS] and [MSP]=[CRQ], so that [MQCR]=[APMS]= 1 4 [ABCD].
In a similar way, we can draw a line n parallel to and between PQ and SR for which dist (n,PQ) = dist (D,SR) and dist (n,SR) = dist (B,PQ), so that, for any point N on n, [NPQ]=[DSR], [NRS]=[BRP] and [NPBQ]=[DSNR]= 1 4 [ABCD].
The lines m and n are not parallel, and, so, intersect in a unique point O for which

[OQCR]=[APOS]=[OPBQ]=[DSOR]= 1 4 [ABCD].

Note that m and n intersect inside PQRS and so inside ABCD.
We show that O is the only point with this property. Let L be another point inside ABCD. Then L lies in one of the four partitioning quadrilaterals, say [OQCR], so that [LQCR]<[OQCR]= 1 4 [ABCD]. Hence, L will satisfy the conditions of the problem.
Comments. A careful solution will contain the observation that m and n are not parallel, and will intersect within the quadrilateral. The fact that m and n have a unique point of intersection does not, in and of itself, establish that the requisite point cannot be found in some other way. Therefore, uniqueness needs to be explicitly handled, either by showing that the required point must lie on m and n or by some other argument.
Solution 2. Analysis. Suppose such a point O exists. Then [OPBQ]=[OCQR]= 1 4 [ABCD], so that

[AOB]=2[POB]=2([OPBQ]-[OBQ])=2([OQCR]-[OQC])=2[ROC]=[DOC].

Since [AOB]= 1 2 AB·dist(O,AB) and [DOC]= 1 2 CD·dist(O,CD), we must have that

dist(O,AB) dist(O,CD) = CD AB .

The locus of points O with this property is a line h through the intersection of AB and CD (or parallel to them if they do not intersect) which lies between them (prove this!). Similarly, O must lie on a line k defined by

dist(O,BC) dist(O,AD) = AD BC

through the intersection of BC and AD (if they intersect) that lies between them. These lines are not parallel and intersect within ABCD (why?). If O exists, it must lie on the intersection of h and k.
Synthesis. Construct lines h and k to satisfy the foregoing conditions. They must intersect in a unique point O within ABCD. Now

[AOB]= 1 2 AB·dist(O,AB)= 1 2 CD·dist(O,CD)=[DOC].

Hence [AOP]=[POB]=[COR]=[DOR]. Let α be the common value. Similarly, [BOQ]=[COQ]=[AOS]=[DOS]=β, say. Then each of [APOS], [BQOP], [CROQ] and [DSOR] has the value α+β and O is the desired point.


15.
Determine all triples (x,y,z) of real numbers for which

x(y+1)=y(z+1)=z(x+1).

Comments. In solving a system of equations, one begins by assuming a solution and determining what properties it must have. Since this may involve one-way reasoning, such properties may not necessarily yield a solution and extraneous solutions may arise. Thus, when you have solved the equations, for a complete solution, you should check that the solution is valid.
If, in your manipulations, you divide by a certain quantity or find a quantity in the denominator of a fraction, you should explore the possibility that the quantity could vanish, Remember that you cannot divide by zero. When you write up your final solution, it is often a good idea to deal with this possibility ahead of time and get it out of the way.
Solution 1. Suppose one of the variable, say x, is 0. Then z(x+1)=0, so z=0, and y(z+1)=0 so y=0. Suppose one of the variables, say x is -1. The x(y+1)=0, so y=-1 and y(z+1)=0, so z=-1. Hence, if any variable assumes either of the values -1 and 0, then all are equal. Henceforth, we assume that none of them have either value.
>From the equations, we find that

y(z+1) y+1 =x= yz+y-z z

whence

yz(z+1)=(y+1)yz+(y+1)(y-z)

or

yz(z-y)=(y+1)(y-z).

Hence, either y=z or yz+y+1=0.
If y=z, then z+1=x+1. so that z=x and x=y=z. Conversely, the system is satisfied when x=y=z.
Suppose that yz+y+1=0. Then x(y+1)=z(x+1)=y(z+1)=-1, and so xy+x+1=xz+z+1=0. Suppose z=t, Then x=-(t+1)/t and y=-1/(t+1). Conversely, it is straightforward to check that the system is satisfied by

(x,y,z)= (- t+1 t ,- 1 1+t ,t )

where t0,-1. Thus, we have obtained exactly the complete set of solutions.
Comment. The solution with x,y,z unequal may look non-symmetrical. Verify that, if x=s=-(t+1)/t, then y=-1/(1+t)=-(s+1)/s and z=t=-1/(1+s). Check that x and z can similarly be expressed in terms of y=r.
Solution 2. From the equations, we find that

x(y-z)=z-x,y(z-x)=x-y,andz(x-y)=y-z.

Multiplying these equations yields

xyz(y-z)(z-x)(x-y)=(z-x)(x-y)(y-z).

Hence, either two variables (and so all) are equal or xyz=1. The system is satisfied when all variables are equal.
Suppose that xyz=1. Then

xy+x+1=xy+x+xyz=x(yz+y+1)

and

yz+y+1=yz+y+xyz=y(zx+z+1).

Since xy+x=yz+y=zx+z, either x=y=z=1 or xy+x+1=yz+y+1=zx+z+1=0. We need to check that there are solutions of this type. Select arbitrary x0,-1, then y to satisfy xy+x+1=0 and z to satisfy xyz=1. Then

zx+z+1=zx+z+xyz=z(xy+x+1)=0

and

yz+y+1=yz+y+xyz=y(zx+z+1)=0

so that x(y+1)=y(x+1)=z(x+1)=-1 as desired.
Solution 3. As before, we can check that (x,y,z)=(0,0,0) is the only solution in which any variable vanishes. Henceforth, suppose that xyz0. Let z=vx. Then y+1=v(x+1), whence y=vx+v-1. Therefore

x(vx+v)=x(y+1)=y(z+1)=(vx+v-1)(vx+1)

so that

v(v-1) x2 +v(v-1)x+(v-1)=0.

Either v=1 and we are led to x=y=z, which works, or

vx2 +vx+1=0.

Hence

(x,y,z)= ( -v± v2 -4v 2v , (v-2)± v2 -4v 2 , -v± v2 -4v 2 ).

where v<0 or v4. It can be checked that these values satisfy the equations. (Exercise: Check that this colution is consistent with the other solutions.)
Solution 4. As in the foregoing solutions, we can check that (x,y,z)=(0,0,0),(-1,-1,-1) are the only solutions in which any variable assumes either of the values 0 or -1. Henceforth, suppose x,y,z all differ from 0 and -1.
Let x(y+1)=y(z+1)=z(x+1)=k. Then z=k/(x+1) and y=(k/x)-1=(k-x)/x. Therefore,

k =y(z+1)= ( k-x x ) ( k+x+1 x+1 ) k( x2 +x)= k2 - x2 +k-x=k(k+1)-( x2 +x) (k+1)( x2 +x-k)=0 k=-1or x2 +x=k.

Suppose that x2 +x=k. Then x(x+1)=z(x+1). Since x-1, x=z, and so y+1=x+1. Thus, x=y=z. Suppose that k=-1. Then z=-1/(x+1) and y=-(x+1)/x. It can be checked that this works.
Comment. It is not hard to check independently that the only nonzero solution in which x, y, z have the same sign is in fact given by x=y=z. For in this case, the ratio of any pair is positive, and the system can be rewritten

1 x - 1 y =1- z x


1 z - 1 x =1- y z


1 y - 1 z =1- x y

whence 3=(x/y)+(y/z)+(z/x). By the Arithmetic-Geometric Means Inequality (applicable since the three summands are positive), (x/y)+(y/z)+(z/x)3 with equality if and only if x/y=y/z=z/x or x=y=z.


16.
Suppose that ABCDEZ is a regular octahedron whose pairs of opposite vertices are (A,Z), (B,D) and (C,E). The points F,G,H are chosen on the segments AB, AC, AD respectively such that AF=AG=AH.
(a) Show that EF and DG must intersect in a point K, and that BG and EH must intersect in a point L.
(b) Let EG meet the plane of AKL in M. Show that AKML is a square.
Comment. Many students had complicated arguments involving similar triangles. You should try to envisage the situation in terms of transformations, as this gives you a better sense of what is going on. Of course, if a synthetic argument cannot be found, you always have recourse to the ``refuge of the destitute'', coordinate geometry and the hope that the computations will not be too horrendous. In this case, they are not bad at all.
Solution 1. (a) Since AF:AB=AG:GC, it follows that FGBCED, while FG<BC=ED. Hence, FGDE is a coplanar isosceles trapezoid and so EF and DG must intersect in a point K. A 90ˆ rotation about the axis AZ takes BC, FG, CD, GH, DE, EB. Hence EFBG and DGEH, so that BG and EH must intersect in a point L, which is the image of K under the rotation.
(b) KE and AB intersect in F, so that the two lines are coplanar. Also KF:KE=FG:ED=FG:BC=AF:FB so that ΔKAF~ΔEFB and AKEB. Hence K lies in a plane through A parallel to BCDE. Because the 90ˆ rotation about the axis AZ (which is perpendicular to the planes BCDE and AKL takes KL, AK=AL and KAL= 90ˆ .
Consider a dilation with centre E and factor AB/FB. Let I be on AE with AI=AF. The the dilation takes FK, HL, IA and the plane of FGHI to the parallel plane AKL. The image of G under this dilation is the intersection of EG and the plane of AKL, namely M. Thus the square FGHI goes to KMLA which must also be a square.
Solution 2. The dilation-reflection perpendicular to a plane through FG perpendicular to BE and CD with factor AF/FB takes BE, CD, and fixes F and G. The lines BF and CG with intersection A gets carried to lines EF and DG which intersect in a point K for which AK is perpendicular to the plane and so parallel to BE and CD, and the distance from K to the plane is AF/FB times the distance from A to the plane.
Similarly, considering a dilation-reflection to a plane through GH perpendicular to BC and DE with the same factor produces the point L with AL perpendicular to this plane and so parallel to BC and ED. Thus KAL= 90ˆ .
The reflection in the plane AECZ fixes A,C,E,G and interchanges the points in each of the pairs (B,D) and (F,H). Hence the line pairs (EF,DG) and (EH,BG) are interchanged as is the pair K and L. Thus AK=AL and KL is perpendicular to AECZ. The triangle AKL is in a plane through A parallel to BCDE. The proof that AKML is a square can be completed as in Solution 1.
Solution 3. Assign solid coordinates: A~(0,0,1), B~(0,-1,0), C~(1,0,0), D~(0,1,0), E~(-1,0,0). For some t with 0<t<1, F~(0,-(1-t),t), G~(1-t,0,t), H~(0,1-t,t). The line EF consists of points (-u,-(1-u)(1-t),(1-u)t), with real u and the line DG consists of points ((1-v)(1-t),v,(1-v)t) with real v. They meet in K~((1-t)/t,(t-1)/t,1). Similarly, L~((1-t)/t,(1-t)/t,1), so A,K,L lie on the plane z=1. The line EG consists of points (-w+(1-t)(1-w),0,t(1-w)) with real w, and this intersects the plane z=1 in the point (2(1-t)/t,0,1). The desired result can now be verified.


17.
Suppose that r is a real number. Define the sequence xn recursively by x0 =0, x1 =1, xn+2 = rxn+1 - xn for n0. For which values of r is it true that

x1 + x3 + x5 ++ x2m-1 = xm 2

for m=1,2,3,4,.
Answer. The property holds for all values of r.
Solution 1. Define x-1 =-1; the recurrence still holds with this extension of the index. Note that, for n0,

( xn+1 2 - xn 2 ) -( xn xn+2 - xn-1 xn+1 )= xn+1 ( xn+1 + xn-1 )- xn ( xn + xn+2 ) = xn+1 ( rxn )- xn ( rxn+1 )=0

so that xn+1 2 - xn 2 = xn xn+2 - xn-1 xn+1 .
We prove by induction that for each nonnegative integer m,

x2m = xm ( xm+1 - xm-1 )


x2m+1 = xm+1 2 - xm 2 = xm xm+2 - xm-1 xm+1 .

These equations check out for m=0. Suppose they hold for m=k. Then

x2k+2 = rx2k+1 - x2k =r( xk+1 2 - xk 2 )- xk ( xk+1 - xk-1 ) = xk+1 ( rxk+1 - xk )- xk ( rxk - xk-1 ) = xk+1 xk+2 - xk xk+1 = xk+1 ( xk+2 - xk )


x2k+3 = rx2k+2 - x2k+1 =r( xk+1 xk+2 - xk+1 xk )-( xk+1 2 - xk 2 ) = xk+1 ( rxk+2 - xk+1 )- xk ( rxk+1 - xk ) = xk+1 xk+3 - xk xk+2 = xk+2 2 - xk+1 2

so the result holds for m=k+1.
Hence

x1 + x3 ++ x2m-1 =( x1 2 - x0 2 )+( x2 2 - x1 2 )++( xm 2 - xm-1 2 )= xm 2

as desired.
Solution 2. [R. Mong] We prove by induction that, for m1,

x1 + x3 ++ x2m-1 = xm 2


x2 + x4 ++ x2m = xm xm+1 .

These hold for m=1. Assume they hold for 1km. Then

x1 + x3 ++ x2k+1 =1+( rx2 - x1 )+( rx4 - x3 )++( rx2k - x2k-1 ) =1+r[ x2 + x4 ++ x2k ]-[1+r( x2 + x4 ++ x2k-2 )-( x1 + x3 ++ x2k-3 )] =r( xk xk+1 - xk-1 xk )+ xk-1 2 = rxk xk+1 - xk-1 ( rxk - xk-1 ) = rxk xk+1 - xk-1 xk+1 = xk+1 ( rxk - xk-1 )= xk+1 2


x2 + x4 ++ x2k+2 =( rx1 - x0 )+( rx3 - x2 )++( rx2k+1 - x2k ) = rxk+1 2 - xk xk+1 = xk+1 ( rxk+1 - xk )= xk+1 xk+2 .

Hence the result holds for all m and the result follows.
Solution 3. The recursion xn+2 = rxn+1 - xn has characteristic polynomial t2 -rt+1 with discriminant r2 -4. Its roots are distinct as long as r±2, so we deal with r=±2 separately.
The solution for r=2 is xn =n and for r=-2 is xn =(-1)n-1 n, and it is straightforward to establish the desired relation in these cases. When r±2, the characteristic polynomial has distinct roots σ and 1/σ, where σ+1/σ=r, i.e. σ2 =rσ-1. Note that σ±1 since r±2. The solution of the recursion is

xn = σ σ2 -1 ( σn - σ-n ).

Then

x1 + x3 ++ x2m-1 = σ σ2 -1 (σ+ σ3 ++ σ2m-1 )- σ σ2 -1 ( σ-1 + σ-3 ++ σ-(2m-1) ) = σ2 σ2 -1 [ σ2m -1 σ2 -1 ]- 1 σ2 -1 [ σ-2m -1 σ-2 -1 ] = σ2 ( σ2 -1)2 [ σ2m -1-1+ σ-2m ]= σ2 ( σ2 -1)2 ( σm - σ-m )2 = xm 2 .

Comment. Solvers who used the approach of Solution 3 failed to consider the case in which the characteristic polynomial had a double root.


18.
Let a and b be integers. How many solutions in real pairs (x,y) does the system

x+2y=a


y+2x=b

have?
Comments. Several of the solvers got all mixed up with the status of the variables in the problem, and, for example, found infinitely many solutions to the equations. a and b are fixed in advance; they are parameters, and your final answer will be conditioned by the the characteristics of various pairs (a,b). Rather than rush blindly into the problem, it is a good strategy to gain some understanding of the situation by looking at particular cases. For example, if one takes (a,b)=(0,0), it is not too hard to see that (x,y)=(0,0) is the only solution. Similarly, if (a,b)=(1,1), one arrives at the sole solution (x,y)=( 1 2 , 1 2 ). However, if (a,b)=(1,0), we find two distinct solutions, (x,y)=(- 1 2 ,1),(0, 1 2 ). This not only clarifies the situation, but gives you a couple of examples against which you can check your final answer. Get in the habit of using examples to help understanding. It is an excellent exercise to plot, on the same axes, the graphs of the two equations for various values of a and b.
Solution 1. Since 2x and 2y are the difference of two integers, x and y must have the form m+ u 2 and n+ v 2 respectively, where m and n are integers and u and v each take one of the values 0 and 1. Plugging these in yields

m+2n+v=a


n+2m+u=b.

Solving for m and n gives

3m=2b-a+v-2u


3n=2a-b+u-2v.

For a viable solution, u and v must be such that the right side of each equation is a multiple of 3 (and this is where the characteristics of the parameters a and b enter in). We consider three cases:
(i) Let a+b0 (mod 3). Then, for a solution, we must have

02b-a+v-2u=3b-(a+b)+v-2uv-2u

and

02a-b+u-2vu-2v

modulo 3. Since {u,v}{0,1}, we must have u=v=0, and we obtain the solution

(x,y)= ( 2b-a 3 , 2a-b 3 ).

This checks out.
(ii) Let a+b1 (mod 3). Then, for a solution, we must have

02b-a+v-2u-1+v-2u

and

02a-b+u-2v-1+u-2v

modulo 3. The only solutions of u-2vv-2u0 (mod 3) with u and v equal to 0 or 1 are given by (u,v)=(1,0),(0,1), so, either

(x,y)=(m+ 1 2 ,n)with3m=2b-a-2,3n=2a-b+1

or

(x,y)=(m,n+ 1 2 )with3m=2b-a+1,3n=2a-b-2.

Thus, we get two solutions

(x,y)= ( 4b-2a-1 6 , 2a-b+1 3 ), ( 2b-a+1 3 , 4a-2b-1 6 ).

These check out.
(iii) Let a+b2 (mod 3). Then

02b-a+v-2u-2+v-2u

and

02a-b+u-2v-2+u-2v

modulo 3. For a solution, we must have v-2uu-2v2 (mod 3), so that (u,v)=(1,1) and (x,y)=(m+ 1 2 ,n+ 1 2 ) with 3m=2b-a-1 and 3n=2a-b-1. Hence there is a unique solution

(x,y)= ( 4a-2a+1 6 , 4a-2b+1 6 ).

This checks out.
Hence, when a+b0 or a+b2 (mod 3), there is one solution to the system, while when a+b1 (mod 3), there are two solutions.

Solution 2. Observe that x and y must be half integers. Since

x+y+2x+2y=a+b

and x- 1 2 xx, y- 1 2 yy, we must have that

a+b3(x+y)a+b+1.

Hence, x+y, being a half integer, must have exactly one of the values

a+b 3 , a+b+ 1 2 3 , a+b+1 3

depending on the divisibility of the numerator of the fractions by 3. Consider cases:
(i) Let a+b0 (mod 3). Then x+y is the integer (a+b)/3. If x and y are not themselves integers, then

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

so that

3(x+y)-1a+b0

modulo 3, a contradiction. Hence, x and y are both integers and

(x,y)= ( 2b-a 3 , 2a-b 3 ).

This checks out.
(ii) Let a+b1 (mod 3). Then 2(a+b)+10 (mod 3), and so

x+y= a+b+ 1 2 3 = 2(a+b)+1 6 ,

a half-integer. Hence there are integers m and n for which

(x,y)=(m+ 1 2 ,n)or(m+1,n- 1 2 )

where m+n=(a+b-1)/3. We find that

(x,y)= ( 4b-2a-1 6 , 2a-b+1 3 ), ( 2b-a+1 3 , 4a-2b-1 6 ).

These check out.
(iii) a+b2 (mod 3). Then x+y=(a+b+1)/3, an integer. In this case, we can check that x and y cannot be integers, so that x=x+1/2 and y=y+1/2, and so

(x,y)= ( 4a-2a+1 6 , 4a-2b+1 6 ).

This checks out.

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