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_{1} + a_{2} + ¼+ a_{k} with a_{1} ³ a_{2} ³ ¼ ³ 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 1. The values 40
^{°}, 80
^{°} and
160
^{°} all satisfy cos3
q =
1/2, or
8 cos
^{3} q 6cos
q+ 1 = 0. Thus,
cos40
^{°}. cos80
^{°} and cos160
^{°}
are the roots of the cubic equation 8x
^{3}  6x + 1 = 0,
so that their reciprocals sec40
^{°},
sec80
^{°} and sec160
^{°} are the roots of
the cubic equation x
^{3}  6x
^{2} + 8 = 0. The sum of the roots
of this cubic is
sec40^{°} + sec80^{°} + sec160^{°} = 6 . 

Solution 2. Let z = cos40^{°} + i sin40^{°}.
Then z^{9} = 1. In fact, since z^{9}  1 = (z  1)(z^{2} + z + 1)(z^{6} + z^{3} + 1) and the first two factors fail to vanish,
z^{6} + z^{3} + 1 = 0. Also 1 + z + z^{2} + ¼+ z^{8} = (1 + z + z^{2})(1 + z^{3} + z^{6}) = 0. Observe that
cos40^{°} = ^{1}/_{2}(z + ^{1}/_{z}),
cos80^{°} = ^{1}/_{2}(z^{2} + [ 1/(z^{2})])
and cos160^{°} = ^{1}/_{2}(z^{4} + [ 1/(z^{4})]),
so that the given sum is equal to

2 
é ë


z
1 + z^{2}

+ 
z^{2}
1 + z^{4}

+ 
z^{4}
1 + z^{8}


ù û



= 2 
é ë


z
1 + z^{2}

+ 
z^{2}
1 + z^{4}

+ 
z^{5}
1 + z


ù û


 
 
= 2 
é ë


z(1 + z + z^{4} + z^{5}) + z^{2}(1 + z + z^{2} + z^{3}) + z^{5}(1 + z^{2} +z^{4} + z^{6})
(1 + z)(1 + z^{2})(1 + z^{4})


ù û


 
 
= 2 
é ë


z^{7} + z^{6} + 3z^{5} + z^{4} + z^{3} + 3z^{2} + z + 1
(1 + z)(1 + z^{2})(1 + z^{4})


ù û


 
 
= 2 
é ë


(z+1)(z^{6} + z^{3} + 1) + 3z^{2} (z^{3} + 1)
(1 + z)(1 + z^{2})(1 + z^{4})


ù û


 
 
= 2 
é ë


0  3z^{8}
1 + z + z^{2} + z^{3} + z^{4} + z^{5} + z^{6} + z^{7}


ù û

= 2 
é ë


3z^{8}
z^{8}


ù û

= 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


= 
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 ninepoint 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
ninepoint 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_{0} = 4, x_{1} = x_{2} = 0, x_{3} = 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.
Solution. The recursion is satisfied by the sequences
whose nth terms are any of a
^{n}, b
^{n}, c
^{n}, d
^{n},
where a, b, c, d are the roots of the quartic equation
t
^{4}  t
 1 = 0, and so it is satisfied by
u
_{n} = a
^{n} + b
^{n} + c
^{n} + d
^{n}. Observe that
u
_{0} = 4, u
_{1} = a + b + c + d = 0 (the sum of the roots),
u
_{2} = a
^{2} + b
^{2} + c
^{2} + d
^{2} = (a + b + c + d)
^{2} 2(ab + ac + ad + bc + bd + cd) = 0
 0 = 0 and


= (a^{3} + b^{3} + c^{3} + d^{3}) 
 
 
= (a + b + c + d)^{3}  3(a + b + c + d)(ab + ac + ad + bc + bd +cd)+ 3(abc + abd + acd + bcd) 
 
 

[To check the last, begin with the easier observation that
(x^{3} + y^{3} + z^{3})  (x + y + z)^{3} + 3(x + y + z)(xy + yz + zx) 3xyz º 0 

and note that
(a^{3} + b^{3} + c^{3} + d^{3}) (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 { x
_{n} } and { u
_{n} } 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} = a^{p} + b^{p} + c^{p} + d^{p}+ 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 s
_{1} = a + b + c +d,
s
_{2} = ab + ac + ad + bc + bd + cd, s
_{3} = abc + abd + acd +bcd, s
_{4} = abcd, each of which is an integer. Thus,
a
^{p} + b
^{p} + c
^{p} + d
^{p} =
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
{ u_{1}, u_{2}, u_{3}, ¼, u_{k} } of positive integers that
satisfy u_{1} > u_{2} > u_{3} > ¼ > u_{k} such that
n = u_{1} + u_{3} + u_{5} + ¼ (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 oneone 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 oneone 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.