location:

# Solutions

Notes. A partition of the positive integer n is a representation (up to order) of n as a sum of not necessarily distinct positive integers, i.e., n = a1 + a2 + ¼+ ak with a1 ³ a2 ³ ¼ ³ ak ³ 1. The number of distinct partitions is denoted by p(n). Thus, p(6) = 11 since 6 can be written as 6 = 5 + 1 = 4 + 2 = 4 + 1 + 1 = 3 + 3 = 3 + 2 + 1 = 3 + 1 + 1 +1 = 2 + 2 + 2 = 2 + 2 + 1 + 1 = 2 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1+ 1 + 1.

241.
Determine sec40° + sec80°+ sec160°.
Solution 1. The values 40°, 80° and 160° all satisfy cos3q = -1/2, or 8 cos3 q- 6cosq+ 1 = 0. Thus, cos40°. cos80° and cos160° are the roots of the cubic equation 8x3 - 6x + 1 = 0, so that their reciprocals sec40°, sec80° and sec160° are the roots of the cubic equation x3 - 6x2 + 8 = 0. The sum of the roots of this cubic is
 sec40° + sec80° + sec160° = 6 .

Solution 2. Let z = cos40° + i sin40°. Then z9 = 1. In fact, since z9 - 1 = (z - 1)(z2 + z + 1)(z6 + z3 + 1) and the first two factors fail to vanish, z6 + z3 + 1 = 0. Also 1 + z + z2 + ¼+ z8 = (1 + z + z2)(1 + z3 + z6) = 0. Observe that cos40° = 1/2(z + 1/z), cos80° = 1/2(z2 + [ 1/(z2)]) and cos160° = 1/2(z4 + [ 1/(z4)]), so that the given sum is equal to

 2 éë z 1 + z2 + z2 1 + z4 + z4 1 + z8 ùû
 = 2 éë z 1 + z2 + z2 1 + z4 + z5 1 + z ùû
 = 2 éë z(1 + z + z4 + z5) + z2(1 + z + z2 + z3) + z5(1 + z2 +z4 + z6) (1 + z)(1 + z2)(1 + z4) ùû
 = 2 éë z7 + z6 + 3z5 + z4 + z3 + 3z2 + z + 1 (1 + z)(1 + z2)(1 + z4) ùû
 = 2 éë (z+1)(z6 + z3 + 1) + 3z2 (z3 + 1) (1 + z)(1 + z2)(1 + z4) ùû
 = 2 éë 0 - 3z8 1 + z + z2 + z3 + z4 + z5 + z6 + z7 ùû = 2 éë -3z8 -z8 ùû = 6 .

Solution 3. [T. Liu]

 sec40° + sec80° + sec160°
 = cos40° + cos80° cos40°cos80° + 1 cos160°
 = 2cos60° cos20° cos40°cos80° + 1 cos160°
 = cos20° cos160° + cos40° cos80° cos40° cos80° cos160°
 = cos180° + cos140° + cos120°+ cos40° cos40° (cos240° + cos80°)
 = -1 - 1/2 (1/2)(-cos40° + cos120°+ cos40°) = -3/2 -1/4 = 6 .

Solution 4. Let x = cos40°, y = cos80° and z = cos160°. Then

 x + y + z = 2cos60°cos20° - cos20° = 0
and
 xy + yz + zx
 = 1 2 [cos120° + cos140° + cos240° + cos80°+ cos200° + cos120°]
 = 1 2 éë - 3 2 + x + y + z ùû = - 3 4 .
Now
 8 sin40° cos40° cos80°cos160°
 = 4 sin80° cos80° cos160°
 = 2 sin160° cos160° = sin320° = -sin40°
so that xyz = -1/8. Then the sum of the problem is equal to (xy + yz + zx)/(xyz) = 6.

242.
Let ABC be a triangle with sides of length a, b, c oppposite respective angles A, B, C. What is the radius of the circle that passes through the points A, B and the incentre of triangle ABC when angle C is equal to (a) 90°; (b) 120°; (c) 60°. (With thanks to Jean Turgeon, Université de Montréal.)
Solution. ÐAIB = 180° - 1/2(ÐBAC + ÐABC) = 90° + 1/2ÐC, an obtuse angle. Hence, the side AB of the circle through A, I, B subtends an angle of 180° - ÐC at the centre of the circle, so that its radius has length c/(2sin(90° - C/2)) = c/(2 cosC/2). The radius is equal to c/Ö2, c and c/Ö3 when ÐC = 90°, 120°, 60° respectively.

Comment. a diameter of the circumcircle of ABI is the line joining I to the centre of the escribed circle on side AB.

243.
The inscribed circle, with centre I, of the triangle ABC touches the sides BC, CA and AB at the respective points D, E and F. The line through A parallel to BC meets DE and DF produced at the respective points M and N. The midpoints of DM and DN are P and Q respectively. Prove that A, E, F, I, P, Q lie on a common circle.
Solution 1. Since AF ^FI and AE ^EI, AEIF is concyclic. Since DANF ~ DBDF and BD = BF, then AF = AN, Similarly, AE = AM, and so A is the midpoint of NM. Thus, AP || ND and so
 ÐAPE = ÐAPM = ÐNDM = ÐFDE = 1 2 ÐFIE = ÐAIE
and AEPI is concyclic. Similarly AFQI is concyclic. Thus P, Q, I all lie on the circle (with diameter AI) through A, E and F.

Solution 2. [T. Yue] Let AQ produced meet CB at R. Then AQ = QR and NQ = QD, so that RD = AN = AEÞ CR = CD + DR = CE + AE = CA. Therefore DCAR is isosceles with median CQ. Hence CQ ^AR and Q lies on the angle bisector of ÐACR. Thus, I, Q, C are collinear with ÐIQA = ÐIFA = 90°. Hence AFQIE is concyclic. Also AFPIE is conclyclic and the result follows.

Solution 3. Recall that the nine-point circle of a triangle is that circle that contains the midpoints of the sides, the pedal points (feet of altitudes) and the midpoints of the segments joining the orthocentre to the vertices. We show that the six points in question lie on the nine-point circle of triangle MND; indeed, that A, P, Q are the midpoints of the sides, F, E are pedal points and I is the midpoint of the segment joining the orthocentre and D.

ID ^AM, AF ^IF, AF = AM, FI = ID and ÐFAM = 180° - ÐNAF = 180°- ÐFBD = ÐFID. Hence DFAM ~ DFID and we can transform DFAM to DFID by a composite of a rotation about F through 90° and a dilation with factor |IF |/|FA |. Hence MF ^ND and so F is a pedal point of DDMN. Similarly, E is a pedal point. [An alternative argument can be had by noting that A, M, F, E lie on a circle with centre A and diameter NM, so that right angles are subtended at E and F by NM.]

Produce DI to meet the incircle again at H. Since ÐDFH = 90°, H lies on FM. Similarly, H lies on EN, so that H is the orthocentre of DAMN, and I is the midpoint of DH. The result follows.

244.
Let x0 = 4, x1 = x2 = 0, x3 = 3, and, for n ³ 4, xn+4 = xn+1 + xn. Prove that, for each prime p, xp is a multiple of p.
Solution. The recursion is satisfied by the sequences whose nth terms are any of an, bn, cn, dn, where a, b, c, d are the roots of the quartic equation t4 - t - 1 = 0, and so it is satisfied by un = an + bn + cn + dn. Observe that u0 = 4, u1 = a + b + c + d = 0 (the sum of the roots), u2 = a2 + b2 + c2 + d2 = (a + b + c + d)2 -2(ab + ac + ad + bc + bd + cd) = 0 - 0 = 0 and
 u3
 = (a3 + b3 + c3 + d3)
 = (a + b + c + d)3 - 3(a + b + c + d)(ab + ac + ad + bc + bd +cd)+ 3(abc + abd + acd + bcd)
 = 0 - 0 + 3 = 3 .
[To check the last, begin with the easier observation that
 (x3 + y3 + z3) - (x + y + z)3 + 3(x + y + z)(xy + yz + zx)- 3xyz º 0
and note that
 (a3 + b3 + c3 + d3) -(a + b + c + d)3 + 3(a + b + c + d)(ab + ac + ad + bc + bd +cd)- 3(abc + abd + acd + bcd)
is a polynomial of degree 3 in four variables that vanishes when any of a, b, c, dequals 0; by the factor theorem, it is divisible by abcd. This can happen only if it is identically 0.] Thus, the sequences { xn } and { un } agree for n = 0, 1, 2, 3 and so agree at every index n.

Let p be a prime. Then

 0 = (a + b + c + d)p = ap + bp + cp + dp+ pf(a, b, c, d)
from the multinomial expansion, where f(a, b, c, d) is a symmetric polynomial that can be written as a polynomial in the symmetric functions s1 = a + b + c +d, s2 = ab + ac + ad + bc + bd + cd, s3 = abc + abd + acd +bcd, s4 = abcd, each of which is an integer. Thus, ap + bp + cp + dp = -pf(a, b, c, d), where f(a, b, c, d) is an integer and the result follows.

245.
Determine all pairs (m, n) of positive integers with m £ n for which an m ×n rectangle can be tiled with congruent pieces formed by removing a 1 ×1 square from a 2 ×2 square.
Solution 1. The tiling can be done for all pairs (m, n) of positive integers for which m ³ 2, n ³ 2, and either (1) (m, n) = (2, 3k), (3k, 2), (3, 2k), (2k, 3) for some positive integer k, or (2) m ³ 4, n ³ 4, provided mn is a multiple of 3.

Since each tile is made up of three unit squares, the area of each rectangle must be a multiple of 3, so that 3 |mn. The tiling is impossible if either m or n is equal to 1. If m or n equals 2, then the other variable must be a multiple of 3. Suppose, say, the number of rows m equals 3, and let n = 2k + 1. Colour the k + 1 odd unit squares (counting from the end) in each of the top and bottom rows. It is impossible for a tile to cover more than one coloured square, so that at least 2(k + 1) tiles are necessary. But since the area of the rectangle is 3(2k + 1), we do not have room for this many tiles. Thus, if m or n equals 3, the other variable must be even.

We show that the tiling is possible in each of the cases cited. Note that two tiles can be combined to form a 3 ×2 or 2 ×3 rectangle, so any rectangle that has one dimension divisible by 3 and the other even can be tiled. In particular, 6 ×3, 6 ×2, 2 ×6, 3 ×6 rectangles can be tiled, and by combining these, we can tile any rectangle one of whose dimensions is a multiple of 6 and the other dimension exceeds 1.

Suppose that m = 6k + 3 where k ³ 1. If we can tile a 9 ×n rectangle, then by appending tiled 6 ×n rectangles, we can tile a (6k + 3) ×n rectangle. A 9 ×n rectangle can be tiled when n is even; a 9 ×3 rectangle cannot be tiled, but a 9 ×5 rectangle can be tiled (exercise: do it!). It can be deduced that a 9 ×n rectangle can be tiled when n = 2 or n ³ 4. By symmetry, we see that an m ×(6k + 3) rectangle can be tiled whenever m ³ 4 and k ³ 1.

246.
Let p(n) be the number of partitions of the positive integer n, and let q(n) denote the number of finite sets { u1, u2, u3, ¼, uk } of positive integers that satisfy u1 > u2 > u3 > ¼ > uk such that n = u1 + u3 + u5 + ¼ (the sum of the ones with odd indices). Prove that p(n) = q(n) for each positive integer n.
For example, q(6) counts the sets { 6 }, { 6, 5 }, { 6, 4 }, { 6, 3 }, { 6, 2 }, { 6, 1}, { 5, 4, 1 }, { 5, 3, 1 }, { 5, 2, 1 }, { 4, 3, 2}, { 4, 3, 2, 1 }.
Solution. A partition of the natural number n can be illustrated by a Ferrars diagram, in which there are several rows of symbols, left justified, each row containing no more symbols than the row above it and the numbers of symbols in each row giving a number in the partition, ordered from largest to smallest. For example, if n = 15, the partition 15 = 7 + 4 + 3 + 1 is represented by the diagram

 x x x x x x x x x x x x x x x

There is a one-one correspondence between partitions of n and diagrams of n symbols in which each row contains no more symbols than its predecessor. We can also get n symbols by counting the symbols in each gnomon (indicated by a, b, c in the diagram below), so that in the present example 15 = 10 + 4 + 1.

 a a a a a a a a b b b a b c a

The difficulty is that, if we specify the lengths of the gnomons, there are several possibilities for placing the gnomons to give us a Ferrars diagram. So we need a way of specifying exactly which element of the gnomon is at the turning point. One way to do this is to get a measure of the number of vertical elements in the gnomon, which, we achieve by counting for each gnomon after the first, the elements in the vertical shaft along with the elements above and to the right in the horizontal shaft of the previous gnomon; this is indicated by the symbols y and z in the diagram:

 x y y y y y y x y z z x y z x

So we insert in the sum 10 + 4 + 1 the lengths of these hybrid gnomons to get 10 + 8 + 4 + 3 + 1 where the even terms count the number of y's and z's. On the other hand, given such a sum, we can reconstruct the diagram uniquely.

In the general situation, given a partition of n, construct its Ferrars diagram. To construct a sum counted by q(n), the first term counts the number of symbols in the upper left gnomon, the second the number of symbols in the gnomon formed by the second column and the top row to the right of the first column, the third the number of symbols in the gnomon formed by the second column below the first row and the second row to the right of the first column, and so on. On the other hand, given a sum counted by q(n), we can construct a Ferrars diagram as follows. If the last term is an evenly indexed term, make a horizontal row of that number of symbols; if it is oddly indexed, make a vertical column of that number of symbols to form the lowest rightmost gnomon of the diagram. Now work along the sum from right to left. At each evenly indexed summand, to get the gnomon for the next term to the left, extend the top row by one symbol to the left and make it part of a gnomon with the number of terms of the next summand to the left; at each oddly indexed summand, to get the gnomon for the next term to the left, extend the lect column by one symbol up and make it part of a gnomon with the number of terms of the next summand to the left. In this way, we obtain a one-one correspondence between partitions counted by p(n) and finite sequences counted by q(n).

In the example of the problem, we get the correspondence [6; { 6, 5 }], [5 + 1; { 6, 4 }]; [4 + 2; { 5, 4, 1 }], [4 + 1 + 1; { 6, 3 }]; [3 + 3; { 4, 3, 2 }], [3 + 2 + 1; { 5, 3, 1 }]; [3 + 1 + 1 + 1; { 6, 2 }]; [2 + 2 + 2; { 4, 3, 2 }]; [2 + 2 + 1 + 1; { 5, 2, 1 }]; [2 + 1 + 1 + 1 + 1; { 6, 1}]; [1 + 1 + 1 + 1 + 1 + 1; { 6 }].

247.
Let ABCD be a convex quadrilateral with no pairs of parallel sides. Associate to side AB a point T as follows. Draw lines through A and B parallel to the opposite side CD. Let these lines meet CB produced at B¢ and DA produced at A¢, and let T be the intersection of AB and B¢A¢. Let U, V, W be points similarly constructed with respect to sides BC, CD, DA, respectively. Prove that TUVW is a parallelogram.
Solution. [T. Yin] Let AB and CD produced intersect at Y. Suppose A¢ and B¢ are defined as in the problem. Let the line through C parallel to AD meet AB produced at B" and the lines through B parallel to AD meet CD produced at C¢, so that U is the intersection of BC and B"C¢. Let P be the intersection of AB¢ and BC¢ and Q the intersection of A¢B and B"C. Then A¢B || AB¢|| CD and AD || BC¢|| B"C, so that APBA¢ and CQBC¢ are parallelograms. Hence
 BT:TA = A¢B:AB¢ = AP:AB¢ = YC¢:YC
and
 BU:UC = BC¢:B"C = YB:YB¢ .
Since also YB:YB" = YC¢:YC, BT:TA = BU:UC and TU || AC. Similarly, VW || AC, TU || BD, UW || BD and so TUVW is a parallelogram.

 top of page | contact us | privacy | site map |