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 = a₁ + a₂ + ¼+ a_k with a₁ ³ a₂ ³ ¼ ³ a_k ³ 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 2. Let z = cos40^° + i sin40^°. Then z⁹ = 1. In fact, since z⁹ - 1 = (z - 1)(z² + z + 1)(z⁶ + z³ + 1) and the first two factors fail to vanish, z⁶ + z³ + 1 = 0. Also 1 + z + z² + ¼+ z⁸ = (1 + z + z²)(1 + z³ + z⁶) = 0. Observe that cos40^° = ¹/₂(z + ¹/_z), cos80^° = ¹/₂(z² + [ 1/(z²)]) and cos160^° = ¹/₂(z⁴ + [ 1/(z⁴)]), so that the given sum is equal to

Solution 3. [T. Liu]

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

---

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.)

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 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 x₀ = 4, x₁ = x₂ = 0, x₃ = 3, and, for n ³ 4, x_n+4 = x_n+1 + x_n. Prove that, for each prime p, x_p is a multiple of p.

Let p be a prime. Then

---

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.

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 { u₁, u₂, u₃, ¼, u_k } of positive integers that satisfy u₁ > u₂ > u₃ > ¼ > u_k such that n = u₁ + u₃ + u₅ + ¼ (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 }.

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.

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:

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.