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.

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?

(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 = d₁ < d₂ < ¼ < d₁₆ = N;

(ii) the divisor with the index d₅ (namely, d_d5) is equal to (d₂ + d₄)×d₆ (the product of the two).

(1) Since N has exactly sixteen positive divisors and d₅ is an index, d₅ £ 16. On the other hand, d₆ is a proper divisor of d_d5, so d₆ £ d_d5. Thus 6 < d₅ £ 16.

(2) If N were odd, all its factors would be odd. But, by (ii), the factor d_d5 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 = Õp_i^k_i is the prime factor decomposition, then the number of all divisors, including 1 and N is Õ(1 + k_i). [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 p_i there are (1 + k_i) possibility for the exponent (from 0 to k_i inclusive). In particular, the factor 1 corresponds to taking all exponents 0, and N to taking all exponents to be the maximum k_i.] It can be checked that there are five cases for the prime factorization of N; (i) N = p¹⁵, N = p₁⁷p₂; (iii) N = p₁³p₂p₃; (iv) N = p₁³ p₂³; (v) N = p₁p₂p₃p₄.

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

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

Hence, d₄ must be a prime number, and so one of 3, 5, 7, 11, 13. Since d₃ ³ 3, d₄ ¹ 3.

Suppose that d₄ = 5. Then d₂ + d₄ = 7 must divide N. Thus d₅ or d₆ must be 7. If d₅ = 7, then d₃ ¹ 3, for otherwise 6 would be a factor between d₄ and d₅. But then d₃ = 4, so that N = 2² ·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 2³ rather than 2² in the factorization. Thus, d₆ = 8 and d₇ = 10. But then d_d5 = d₇ ¹ (d₂ + d₄)d₆. So d₅ = 7 is rejected and we must have d₆ = 7. This entails that d₅ = 6. But this denies the equality of d₆ = d_d5 and (d₂ +d₄)d₆. We conclude that d₄ ¹ 5.

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

Suppose that d₄ = 11. Then d₂ + d₄ = 13 divides N, and is either d₅ (when 12 is not a factor) or d₆ (when 12 is a factor). If d₅ = 13, then d₃ 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 d₃ = 4, then N = 2² ·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 d₅ = 5, there is no room for 10.

Finally (with d₄ = 11, d₅ = 13), if d₃ = 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 d₄ = 11, d₆ = 13, then d₅ = 12, so that 3, 4, 6 are all factors of N; but there is no room for them between d₂ and d₄.

The remaining case is that d₄ = 13, which makes d₂ + d₄ = 15 a factor of N; but there is no room for both 3 and 5 between d₂ and d₄. 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  .

---

237.

The sequence { a_n : 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 + 5a_n a_n+1 is a perfect square.

Now, 1 + 5a_na_n+1 = 501 - 500 + 5a_na_n+1 = 501 + (a_n+1 + a_n)² for each n ³ 1. Since 1 + 5a_na_n+1 = k² is equivalent to

---

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.

Solution. Denote the circumcentres of the triangles ABC, ANC and BMN by O, O₁ and O₂ respectively. Denote also their circumcircles by \frak K, \frak K₁ and \frak K₂ respectively, and the radii of these circles by R, R₁ and R₂ respectively. (See figure 1.) The common chord CD of \frak K₁ and \frak K₂ is perpendicular to O₁O₂. Thus, O Î CD Û CO ^O₁O₂.

We prove two lemmata.

Lemma 1. Let M₁ be the perpendicular projection of the point M onto AB and N₁ the projection of the point N onto AB. The right bisector of AB, the line S_AB, passes through the midpoint of MN if and only if AN₁ = BM₁. (See figure 2.)

Proof. Note that MM₁N₁N is a trapezoid with bases parallel to S_AB. 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 S_AB passes through the midpoint of MN if and only if S_AB passes through the midpoint of M₁N₁. Since S_AB intersects AB at its midpoint, this is equivalent to S_AB passes through the midpoint of M₁N₁ Û AB and M₁N₁ have the same midpoint, which is equivalent to AM₁ = BN₁ or AN₁ = BM₁ ª.

Lemma 2. The diagonals d₁ and d₂ of the quadrilateral PQRS are perpendicular if and only if its sides a, b, c, d satisfy the relationship a² + c² = b² + d². ((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 d₁ and d₂ intersect at I, and let

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

· CD passes through O Û CO ^O₁O₂;

· CO ^O₁O₂ Û O₁C² + OO₂² = O₂C² + OO₁²;

· AN₁ = BM₁ Û S_AB passes through the midpoint of MN.

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

From the Law of Cosines,

We need to establish that (i) ÐO₁CO = ÐNAB and (ii) ÐO₂CO = ÐMBA. (See figure 3.) Ad (i), ÐAO₁N = 2ÐACN = 2a and ÐCO₁N = 2ÐCAN = 2b, say, so that ÐCO₁A = 2(a+ b). The common chord CA of \frak K₁ and \frak K is right bisected by O₁O, so that ÐCO₁A = 2ÐCO₁O and ÐCO₁O = a+ b. On the other hand, ÐCOO₁ = ¹/₂ÐCOA = ÐCBA = g, say. Hence, ÐO₁CO = 180^° - (a+ b+g). Also, ÐANB = a+ b and ÐNAB = 180^° - (a+ b+ g) = ÐO₁CO. Similarly, (ii) can be shown.

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

---

239.

Find all natural numbers n for which the diophantine equation

(x + y + z)2 = nxyz

has positive integer solutions 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)² = nr² or 1 = r(nr - 4r - 4), whence (n; r) = (9, 1). The second leads to 4(r + 1)² = 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

Suppose x ³ 2. Then

---

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?

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 a_i 0s in the ith row. Then å_i=1⁸ a_i = 8 ×4 = 32 and å_i=2⁸ a_i = 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 a_i 0s. We can choose two of them in ((a_i) || 2) ways, so the number of possible pairs in all rows is å_i=1⁸ ((a_i) || 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,

We have that

0	0	0	0	0	0	0
0	1	1	1	1	0	0
0	1	1	0	0	1	1
0	0	0	1	1	1	1
1	0	1	0	1	0	1
1	0	1	1	0	1	0
1	1	0	0	1	1	0
1	1	0	1	0	0	1