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.
Sources. 234. Bulgarian math competitions  selected
problems, Tonov I. et al, Regalia6, 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 = d_{1} < d_{2} < ¼ < d_{16} = N;


(ii) the divisor with the index d_{5} (namely,
d_{d5}) is equal to (d_{2} + d_{4})×d_{6} (the product of
the
two).
Solution. There are some preliminary easy observations:
(1) Since N has exactly sixteen positive divisors and
d_{5} is an index, d_{5} £ 16. On the other hand,
d_{6} is a proper divisor of d_{d5}, so d_{6} £ d_{d5}.
Thus 6 < d_{5} £ 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}^{ki}
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^{15}, N = p_{1}^{7}p_{2}; (iii) N = p_{1}^{3}p_{2}p_{3};
(iv) N = p_{1}^{3} p_{2}^{3}; (v) N = p_{1}p_{2}p_{3}p_{4}.
We now put all of this together, and follow the solution of
K.C. R. Tseng. From (1), d_{2} = 2.
If d_{4} is composite (i.e. not a square), then
d_{4} = 2d_{3} is even. Since d_{2} + d_{4} divides a factor
d_{d5} of N, it divides N. Since d_{2} + d_{4} = 2(1 + d_{3}), 1 + d_{3} divides N. But then
1 + d_{3} would equal d_{4} = 2d_{3}, which is impossible.
If d_{4} were a perfect square, then it must equal either
4 or 9 (since d_{4} < d_{5} £ 16). In either case, d_{3} = 3,
and 6 must be one of the factors. This excludes the possibility
that d_{4} = 9, since 6 should preceded 9 in the list of
divisors. On the other hand, if d_{4} = 4, then d_{5} must
be equal to either 5 or 6, which is not possible by (1).
Hence, d_{4} must be a prime number, and so one of 3, 5, 7, 11,
13.
Since d_{3} ³ 3, d_{4} ¹ 3.
Suppose that d_{4} = 5.
Then d_{2} + d_{4} = 7 must divide N. Thus d_{5} or d_{6} must
be 7. If d_{5} = 7, then d_{3} ¹ 3, for otherwise 6 would
be a factor between d_{4} and d_{5}. But then d_{3} = 4, so that
N = 2^{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^{3} rather than 2^{2} in the factorization.
Thus, d_{6} = 8 and d_{7} = 10. But then d_{d5} = d_{7} ¹ (d_{2} + d_{4})d_{6}. So d_{5} = 7 is rejected and we must have
d_{6} = 7. This entails that d_{5} = 6.
But this denies the equality of d_{6} = d_{d5} and (d_{2} +d_{4})d_{6}.
We conclude that d_{4} ¹ 5.
Suppose that d_{4} = 7. Then d_{2} + d_{4} = 9 is a factor of N,
so d_{3} = 3. Then 6 must be a factor of N; but there is not
room for 6, and this case is impossible.
Suppose that d_{4} = 11. Then d_{2} + d_{4} = 13 divides N, and
is either d_{5} (when 12 is not a factor) or d_{6} (when 12 is a
factor). If d_{5} = 13, then d_{3} 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_{3} = 4, then N = 2^{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} = 5, there is no room for 10.
Finally (with d_{4} = 11, d_{5} = 13),
if d_{3} = 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_{4} = 11, d_{6} = 13, then d_{5} = 12, so that 3, 4, 6
are all factors of N; but there is no room for them between
d_{2} and d_{4}.
The remaining case is that d_{4} = 13, which makes
d_{2} + d_{4} = 15 a factor of N; but there is no room for
both 3 and 5 between d_{2} and d_{4}. 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 AMGM 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 = 
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 { a_{n} : n = 1, 2, ¼} is
defined
by the recursion
a_{n+2} = 3a_{n+1}  a_{n} for n ³ 1 . 

Find all natural numbers n for which 1 + 5a_{n} a_{n+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 = (a_{n+1}  a_{n1})(a_{n+1} + a_{n1}  3a_{n})Û a_{n+1}^{2}  3a_{n+1}a_{n} = a_{n1}^{2}  3a_{n}a_{n1} 

so that
a_{n+1}^{2}  3a_{n}a_{n+1} + a_{n}^{2} = a_{n}^{2}  3a_{n1}a_{n} + a_{n1}^{2} 

for n
³ 2. Hence a
_{n+1}^{2}  3a
_{n+1}a
_{n} + a
_{n}^{2} is
a constant for N
³ 2, and its value is
30
^{2}  2 ·30 ·20 + 20
^{2} =
500.
Now, 1 + 5a_{n}a_{n+1} = 501  500 + 5a_{n}a_{n+1} = 501 + (a_{n+1} + a_{n})^{2} for each n ³ 1.
Since 1 + 5a_{n}a_{n+1} = k^{2} is equivalent to
3 ×167 = 501 = (k  (a_{n+1} + a_{n}))(k + (a_{n+1}  a_{n}) , 

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

238.

Let ABC be an acuteangled 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, O_{1} and O_{2} respectively.
Denote also their circumcircles by \frak K,
\frak K_{1} and \frak K_{2} respectively, and the
radii of these circles by R, R_{1} and R_{2} respectively.
(See figure 1.) The common chord CD of \frak K_{1} and
\frak K_{2} is perpendicular to O_{1}O_{2}. Thus,
O Î CD Û CO ^O_{1}O_{2}.
We prove two lemmata.
Lemma 1. Let M_{1} be the perpendicular projection
of the point M onto AB and N_{1} 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_{1} = BM_{1}. (See figure 2.)
Proof. Note that MM_{1}N_{1}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_{1}N_{1}. Since S_{AB} intersects AB at its midpoint, this
is equivalent to S_{AB} passes through the midpoint of
M_{1}N_{1}
Û AB and M_{1}N_{1} have the same midpoint,
which is equivalent to AM_{1} = BN_{1} or AN_{1} = BM_{1}
ª.
Lemma 2. The diagonals d_{1} and d_{2} of the
quadrilateral
PQRS are perpendicular if and only if its sides a, b, c, d
satisfy the relationship a^{2} + c^{2} = b^{2} + d^{2}. ((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_{1} and d_{2} 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
a^{2} = x^{2} + y^{2}  2xy cosq 

c^{2} = z^{2} + t^{2}  2zt cosq 

b^{2} = y^{2} + z^{2} + 2yz cosq 

d^{2} = x^{2} + t^{2} + 2xt cosq . 

As a
^{2} + c
^{2} = b
^{2} + d
^{2} is equivalent to
(xy + zt + yz + xt)cos
q = 0, or cos
q = 0,
the result follows.
ª
Let us return to the problem. Consider (in figure 1) the
quadrilateral CO_{1}OO_{2}. We already know from the foregoing
that
· CD passes through O Û CO ^O_{1}O_{2};
· CO ^O_{1}O_{2} Û O_{1}C^{2} + OO_{2}^{2} = O_{2}C^{2} + OO_{1}^{2};
· AN_{1} = BM_{1} Û S_{AB} passes
through
the midpoint of MN.
So to complete the solution, it is necessary to prove that
O_{1}C^{2} + OO_{2}^{2} = O_{2}C^{2} + OO_{1}^{2} ÛAN_{1} = BM_{1} . 

From the Law of Cosines,
OO_{1}^{2} = O_{1}C^{2} + OC^{2}  2O_{1}C ·OC ·cosÐO_{1}CO 

and
OO_{2}^{2} = O_{2}C^{2} + OC^{2}  2O_{2}C ·OC ·cosÐO_{2}CO 

from which
O_{1}C^{2} + OO_{2}^{2} = O_{2}C^{2} + OO_{1}^{2}  2OC ·(O_{2}C cosÐO_{2}CO)  O_{1}C cosÐO_{1}CO) . 

We need to establish that (i) ÐO_{1}CO = ÐNAB and
(ii) ÐO_{2}CO = ÐMBA. (See figure 3.)
Ad (i), ÐAO_{1}N = 2ÐACN = 2a and
ÐCO_{1}N = 2ÐCAN = 2b, say, so that
ÐCO_{1}A = 2(a+ b). The common chord
CA of \frak K_{1} and \frak K is right bisected by
O_{1}O, so that ÐCO_{1}A = 2ÐCO_{1}O and
ÐCO_{1}O = a+ b. On the other hand,
ÐCOO_{1} = ^{1}/_{2}ÐCOA = ÐCBA = g,
say. Hence, ÐO_{1}CO = 180^{°}  (a+ b+g). Also, ÐANB = a+ b and ÐNAB = 180^{°}  (a+ b+ g) = ÐO_{1}CO.
Similarly, (ii) can be shown.
From the extended Law of Sines involving the circumradius,
we have that 2R_{1} = AN/sinC and 2R_{2} = MB/sinC.
It follows that
O_{2}C cosÐO_{2}CO  O_{1}C cosÐO_{1}CO = 0 

Û R_{2} ·cosÐMBA  R_{1} ·cosÐNAB = 0 

Û MB cosÐMBA = AN cosÐNAB . 

However, MB cos
ÐMBA = BM
_{1} and
AN cos
ÐNAB = AN
_{1} (the lengths of the projections
on AB). The result now follows, that CD passes through
O if and only if S
_{AB} passes through the midpoint of
MN.

239.

Find all natural numbers n for which the
diophantine equation
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
t^{2} + (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} = nr^{2} 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
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 a_{i} 0s in the
ith row. Then å_{i=1}^{8} a_{i} = 8 ×4 = 32 and
å_{i=2}^{8} 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}^{8} ((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,

8 å
i=1


æ è

a_{i}
2

ö ø

= 56 . 

We have that


= 
a_{1}(a_{1}  1)
2

+ 
8 å
i=2


a_{i}(a_{i}  1)
2


 
 
= 28  
1
2


8 å
i=2

a_{i} + 
1
2


8 å
i=2

a_{i}^{2} = 28  12 + 
1
2


8 å
i=2

a_{i}^{2} , 

from which
å_{i=2}^{8} a
_{i}^{2} = 2(56
 28 + 12) = 80.
From the ineqaulity of the root mean square and the
arithmetic mean, we have that

a_{2}^{2} + ¼+ a_{8}^{2}
7

³ 
æ è


a_{2} + ¼+ a_{8}
7


ö ø

2

= 
576
49

. 

whence 80 =
å_{i=2}^{8} a
_{i}^{2} ³ 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:
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 
Thanks to Emil Kolev, Sofia, Bulgaria for this problem.