CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  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.

Sources. 234. Bulgarian math competitions - selected problems, Tonov I. et al, Regalia-6, Sofia, 2001. 235, 236. Junior Balkan Math Olympiad, 2002. 237. Balkan Math Olympiad, 2002. 238, 239. Mathematics Plus, issues 3, 4, 2002, Sofia, 240. National Mathematical Olympiad, 1999, Bulgaria, Regional Round.


234.
A square of side length 100 is divided into 10000 smaller unit squares. Two squares sharing a common side are called neighbours.
(a) Is it possible to colour an even number of squares so that each coloured square has an even number of coloured neighbours?
(b) Is it possible to colour an odd number of squares so that each coloured square has an odd number of coloured neighbours?
Solution. [Y. Zhao] (a) Yes, it is possible in many ways to perform the task. For example, colour any two nonadjacent squares, and both of them will have zero coloured neighbours. So there are evenly many (2) coloured squares, each with an even number (0) of coloured neighbours.

(b) Suppose, if possible, we could colour an odd number of squares so that each has an odd number of coloured neighbours. Let us count the number of segments or edges that connect two coloured neighbours. Since for each coloured square there is an odd number of coloured neighbours, then the total number of their common sides is the sum of an odd number of odd terms, and so is odd. However, two coloured neighbours share each of these common edges, therefore each coloured neighbour is counted twice in the sum; thus, the sum should be even. This is a contradiction. So, it is impossible to colour an odd number of squares so that each has an odd number of coloured neighbours.



235.
Find all positive integers, N, for which:
(i) N has exactly sixteen positive divisors: 1 = d1 < d2 < < d16 = N;
(ii) the divisor with the index d5 (namely, dd5) is equal to (d2 + d4)×d6 (the product of the two).
Solution. There are some preliminary easy observations:

(1) Since N has exactly sixteen positive divisors and d5 is an index, d5 16. On the other hand, d6 is a proper divisor of dd5, so d6 dd5. Thus 6 < d5 16.

(2) If N were odd, all its factors would be odd. But, by (ii), the factor dd5 would be the product of an even and an odd number, and so be even. But this would given N an even divisor and lead to a contradiction.

(3) Recall that, if N = piki is the prime factor decomposition, then the number of all divisors, including 1 and N is (1 + ki). [To understand this formula, think how we can form any of the divisors of N; we have to choose its prime factors, each to any of the possible exponents. For an arbitrary prime factor pi there are (1 + ki) possibility for the exponent (from 0 to ki inclusive). In particular, the factor 1 corresponds to taking all exponents 0, and N to taking all exponents to be the maximum ki.] It can be checked that there are five cases for the prime factorization of N; (i) N = p15, N = p17p2; (iii) N = p13p2p3; (iv) N = p13 p23; (v) N = p1p2p3p4.

We now put all of this together, and follow the solution of K.-C. R. Tseng. From (1), d2 = 2.

If d4 is composite (i.e. not a square), then d4 = 2d3 is even. Since d2 + d4 divides a factor dd5 of N, it divides N. Since d2 + d4 = 2(1 + d3), 1 + d3 divides N. But then 1 + d3 would equal d4 = 2d3, which is impossible. If d4 were a perfect square, then it must equal either 4 or 9 (since d4 < d5 16). In either case, d3 = 3, and 6 must be one of the factors. This excludes the possibility that d4 = 9, since 6 should preceded 9 in the list of divisors. On the other hand, if d4 = 4, then d5 must be equal to either 5 or 6, which is not possible by (1).

Hence, d4 must be a prime number, and so one of 3, 5, 7, 11, 13. Since d3 3, d4 3.

Suppose that d4 = 5. Then d2 + d4 = 7 must divide N. Thus d5 or d6 must be 7. If d5 = 7, then d3 3, for otherwise 6 would be a factor between d4 and d5. But then d3 = 4, so that N = 22 ·5 ·7 ·K where K is a natural number. But N must have 16 divisors, and the only way to obtain this is to have 23 rather than 22 in the factorization. Thus, d6 = 8 and d7 = 10. But then dd5 = d7 (d2 + d4)d6. So d5 = 7 is rejected and we must have d6 = 7. This entails that d5 = 6. But this denies the equality of d6 = dd5 and (d2 +d4)d6. We conclude that d4 5.

Suppose that d4 = 7. Then d2 + d4 = 9 is a factor of N, so d3 = 3. Then 6 must be a factor of N; but there is not room for 6, and this case is impossible.

Suppose that d4 = 11. Then d2 + d4 = 13 divides N, and is either d5 (when 12 is not a factor) or d6 (when 12 is a factor). If d5 = 13, then d3 is either a prime number less than 11 or 4. It cannot be 3, as there is no room to fit the divisor 6. If d3 = 4, then N = 22 ·11 ·13 ·K and the only way to get 16 divisors is for the exponent of 2 to be 3. Thus, 8 divides N, but there is no room for this divisor. Similarly, if d5 = 5, there is no room for 10.

Finally (with d4 = 11, d5 = 13), if d3 = 7, we already have four prime divisor of N, and this forces N = 2 ·7 ·11 ·13 = 2002. We have that the divisors in increasing order are 1, 2, 7, 11, 13, 14, 22, 26, 77, 91, 143, 154, 182, 286, 1001, 2002, and all the conditions are satified.

When d4 = 11, d6 = 13, then d5 = 12, so that 3, 4, 6 are all factors of N; but there is no room for them between d2 and d4.

The remaining case is that d4 = 13, which makes d2 + d4 = 15 a factor of N; but there is no room for both 3 and 5 between d2 and d4. We conclude that N = 2002 is the only possibility.



236.
For any positive real numbers a, b, c, prove that
 1

b(a + b)
+  1

c(b + c)
+  1

a(c + a)
 27

2(a + b + c)2
 .
Solution. [G.N. Tai] Apply the AM-GM Inequality to get
 1

b(a + b)
+  1

c(b + c)
+  1

a(c + a)
3
3
 
 

 1

abc(a + b)(b + c)(c + a)
 

a + b + c 3
3
 

abc
 

a + b + c =  1

2
((a + b) + (b + c) + (c + a))  3

2
3
 

(a + b)(b + c)(c + a)
 
 .
Multiplying these inequalities together and dividing by (a + b + c)2 yields the result. Equality occurs if and only if a = b = c.



237.
The sequence { an : n = 1, 2, } is defined by the recursion
a1 = 20                a2 = 30

an+2 = 3an+1 - an         for  n 1 .
Find all natural numbers n for which 1 + 5an an+1 is a perfect square.
Solution. [R. Marinov] The first few terms of the sequence are 20, 30, 70, 180, 470, 1230. Observe that
0 = (an+1 - an-1)(an+1 + an-1 - 3an) an+12 - 3an+1an = an-12 - 3anan-1
so that
an+12 - 3anan+1 + an2 = an2 - 3an-1an + an-12
for n 2. Hence an+12 - 3an+1an + an2 is a constant for N 2, and its value is 302 - 2 ·30 ·20 + 202 = -500.

Now, 1 + 5anan+1 = 501 - 500 + 5anan+1 = 501 + (an+1 + an)2 for each n 1. Since 1 + 5anan+1 = k2 is equivalent to

3 ×167 = 501 = (k - (an+1 + an))(k + (an+1 - an) ,
we must have that either (i) A - (an+1 + an) = 1 and A + (an+1 + an) = 501 or (ii) A - (an+1 + an) = 3 and A + (an+1 + an) = 167. The second possibility leads to an+1 + an = 82 which is not divisible by 10 and so cannot occur. The first possibility leads to an+1 + an = 250, which occurs when n = 3. Since the sequence is increasing (prove this!), this is the only possibility.



238.
Let ABC be an acute-angled triangle, and let M be a point on the side AC and N a point on the side BC. The circumcircles of triangles CAN and BCM intersect at the two points C and D. Prove that the line CD passes through the circumcentre of triangle ABC if and only if the right bisector of AB passes through the midpoint of MN.
Note: Figures 1, 2, 3 accompany this solution.

Solution. Denote the circumcentres of the triangles ABC, ANC and BMN by O, O1 and O2 respectively. Denote also their circumcircles by \frak K, \frak K1 and \frak K2 respectively, and the radii of these circles by R, R1 and R2 respectively. (See figure 1.) The common chord CD of \frak K1 and \frak K2 is perpendicular to O1O2. Thus, O CD CO ^O1O2.

We prove two lemmata.

Lemma 1. Let M1 be the perpendicular projection of the point M onto AB and N1 the projection of the point N onto AB. The right bisector of AB, the line SAB, passes through the midpoint of MN if and only if AN1 = BM1. (See figure 2.)

Proof. Note that MM1N1N is a trapezoid with bases parallel to SAB. Recall that the midline of a trapezoid has the following property: the segment that connects the midpoints of the two nonparallel sides is parallel to the bases and its length is the average of the lengths of the two parallel sides. As a direct consequence, a line passing through one of the midpoints of the two nonparallel sides and is parallel to the bases must pass through the midpoint of the other side. Applying this yields that SAB passes through the midpoint of MN if and only if SAB passes through the midpoint of M1N1. Since SAB intersects AB at its midpoint, this is equivalent to SAB passes through the midpoint of M1N1 AB and M1N1 have the same midpoint, which is equivalent to AM1 = BN1 or AN1 = BM1 .

Lemma 2. The diagonals d1 and d2 of the quadrilateral PQRS are perpendicular if and only if its sides a, b, c, d satisfy the relationship a2 + c2 = b2 + d2. ((a, c) and (b, d) are pairs of opposite sides.)

Proof. (To follow the steps of the proof, please draw an arbitrary convex quadrilateral PQRS with the respective lengths of SR, RQ, QP and PS given by a, b, c and d.) Let d1 and d2 intersect at I, and let

PIQ = q ,   |IP | = t ,  |IQ | = z ,  |IR | = y ,  |IS | = x .
The Law of Cosines applied to triangles PQI, QRI, RSI and SPI yields
a2 = x2 + y2 - 2xy cosq

c2 = z2 + t2 - 2zt cosq

b2 = y2 + z2 + 2yz cosq

d2 = x2 + t2 + 2xt cosq .
As a2 + c2 = b2 + d2 is equivalent to (xy + zt + yz + xt)cosq = 0, or cosq = 0, the result follows.

Let us return to the problem. Consider (in figure 1) the quadrilateral CO1OO2. We already know from the foregoing that

CD passes through O CO ^O1O2;

CO ^O1O2 O1C2 + OO22 = O2C2 + OO12;

AN1 = BM1 SAB passes through the midpoint of MN.

So to complete the solution, it is necessary to prove that

O1C2 + OO22 = O2C2 + OO12 AN1 = BM1 .

From the Law of Cosines,

OO12 = O1C2 + OC2 - 2O1C ·OC ·cosO1CO
and
OO22 = O2C2 + OC2 - 2O2C ·OC ·cosO2CO
from which
O1C2 + OO22 = O2C2 + OO12 - 2OC ·(O2C cosO2CO) - O1C cosO1CO) .

We need to establish that (i) O1CO = NAB and (ii) O2CO = MBA. (See figure 3.) Ad (i), AO1N = 2ACN = 2a and CO1N = 2CAN = 2b, say, so that CO1A = 2(a+ b). The common chord CA of \frak K1 and \frak K is right bisected by O1O, so that CO1A = 2CO1O and CO1O = a+ b. On the other hand, COO1 = 1/2COA = CBA = g, say. Hence, O1CO = 180 - (a+ b+g). Also, ANB = a+ b and NAB = 180 - (a+ b+ g) = O1CO. Similarly, (ii) can be shown.

From the extended Law of Sines involving the circumradius, we have that 2R1 = AN/sinC and 2R2 = MB/sinC. It follows that

O2C cosO2CO - O1C cosO1CO = 0

R2 ·cosMBA - R1 ·cosNAB = 0

MB cosMBA = AN cosNAB .
However, MB cosMBA = BM1 and AN cosNAB = AN1 (the lengths of the projections on AB). The result now follows, that CD passes through O if and only if SAB passes through the midpoint of MN.



239.
Find all natural numbers n for which the diophantine equation
(x + y + z)2 = nxyz
has positive integer solutions x, y, z.
Solution. Let (n; x, y, z) = (n; u, v, w) be a solution of the equation. Then the quadratic equation
t2 + (2u + 2v - nuv)t + (u + v)2 = 0
has two solutions, w and a second one w for which ww = (u + v)2 > 0 (product of the roots). Since w + w = -(2u + 2v - nuv), an integer, w must be a positive integer, and so (n; x, y, z) = (n; u, v, w) is a solution of the equation. If w > (u + v), then w < (u + v). It follows that, if there is a solution, we can repeat the process long enough using any two of the three variables as fixed to always find solutions (n; x, y, z) of the equation for which z x + y, y x + z and x x + y. So we impose this additional restriction in our search. Wolog, we can also suppose that 1 x y z.

Suppose x = 1. Since z x + y = 1 + y, (x, y, z) = (1, r, r) or (1, r, r+1). The first leads to (2r + 1)2 = nr2 or 1 = r(nr - 4r - 4), whence (n; r) = (9, 1). The second leads to 4(r + 1)2 = nr(r + 1), or 4 = (n - 4)r; this yields (n; r) = (8; 1), (6; 2), (5; 4). Thus, the four solutions with x = 1 are

(n; x, y, z) = (5; 1, 4, 5), (6; 1, 2, 3); (8; 1, 1, 2);(9; 1, 1, 1) .

Suppose x 2. Then

nxyz = (x + y + z)(x + y + z) (z + z + z)(x + y + x + y) = 6z(x + y)
so that nxy 6(x + y). Rearranging the terms and adding 36 to both sides yields
(nx - 6)(ny - 6) 36 .
Since 2 x y, we find that (2n - 6)(2n - 6) 36 so that 0 n 6. Checking turns up the additional solutions
(n; x, y, z) = (1; 9, 9, 9), (2; 4, 4, 8); (3; 3, 3, 3);(4; 2, 2, 4) .
Thus, the only natural numbers n for which a solution exists are 1, 2, 3, 4, 5, 6, 8, 9.



240.
In a competition, 8 judges rate each contestant "yes" or "no". After the competition, it turned out, that for any two contestants, two judges marked the first one by "yes" and the second one also by "yes"; two judges have marked the first one by "yes" and the second one by "no"; two judges have marked the first one by "no" and the second one by "yes"; and, finally, two judges have marked the first one by "no" and the second one by "no". What is the greatest number of contestants?
Solution. Let n be the number of contestants. Then, the marks of the judges for each of them can be recorded in a column of eight zeros or ones, as follows: there is a 1 on the ith position of the number if the ith judge has marked this contestant by "yes" and there is a 0 in this position if the ith judge has marked this contestant by "no". This way, the information about the marks of the contestants will be recorded in an n ×8 table. Now, the given condition implies that the 2 ×8 table formed by any two columns of the above table has exactly two rows of each of 00, 01, 10, 11. Denote this property by (*). We will now show that eight columns with any pair having this property do not exist.

Suppose the contrary, and consider a table with eight columns. Interchanging 1 and 0 in any column does not change the property (*), so, wolog, we can assume that the first row consists solely of 0s. Let there be ai 0s in the ith row. Then i=18 ai = 8 ×4 = 32 and i=28 ai = 32 - 8 = 24. Next, we will count the number of pairs of two 0s that can appear in the lines of the table in two different ways.

(i) In the ith row, there are ai 0s. We can choose two of them in ((ai) || 2) ways, so the number of possible pairs in all rows is i=18 ((ai) || 2).

(ii) There are 8 columns. We can choose two of them in (8 || 2) = 28 ways. In each selection, there are exactly two rows with 00, so that all the ways to get combinations of two 0s is 2 ×28 = 56. Thus,

8

i=1 

ai
2

= 56 .

We have that

8

i=1 

ai
2

=  a1(a1 - 1)

2
+ 8

i=2 
 ai(ai - 1)

2
= 28 -  1

2
8

i=2 
ai +  1

2
8

i=2 
ai2 = 28 - 12 +  1

2
8

i=2 
ai2 ,
from which i=28 ai2 = 2(56 - 28 + 12) = 80. From the ineqaulity of the root mean square and the arithmetic mean, we have that
 a22 + + a82

7

 a2 + + a8

7

2

 
=  576

49
 .
whence 80 = i=28 ai2 576/7 > 82, which is false. Therefore, we must conclude that there cannot be eight columns with condition (*). However, we can realize this condition with a table of seven columns:

Thanks to Emil Kolev, Sofia, Bulgaria for this problem.

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