1  Solutions to Zimbabwe Maths Olympiad Round 2, 2002

1.   Let b and c be integers such that bc + 1 is divisible by 3. Is b+ c also divisible by 3? Justify your answer.

Solution: Try a few obvious examples to see if you can come up with a counterexample - (a,b)=(2,4), (2,7), (4,5), (2,10), (2,13), - they all give a positive answer, suggesting that in general: Yes, b + c is also divisible by 3. Now to prove it.
The secret is what's known as ``congruence modulo 3'': two integers are said to be congruent modulo 3 if they give the same remainder when divided by 3. There being only three possible remainders, this partitions the integers into three disjoint subsets, called the congruence classes with respect to 3.

Defining these sets more precisely:
C₀ = {m Î \Z : m = 3p  for  some  p Î \Z};
C₁ = {m Î \Z : m = 3p+1  for  some  p Î \Z};
C₂ = {m Î \Z : m = 3p+2  for  some  p Î \Z}.
It is easy to see that the set of integers \Z is completely covered by the union of these three sets, and that they do not overlap.

Now, we are given that bc + 1 belongs to C₀, which is obviously equivalent to saying bc belongs to C₂. (If bc+1 leaves remainder 0 when divided by 3, bc will leave a remainder 2, and vice versa.) For their product to be in C₂, it is soon observed that one of b and c must belong to C₁ and the other to C₂. Then, checking their sum, we have b + c = (3p + 1) + (3p¢+ 2) = 3(p+p¢) + 3 = 3q, where q=p+p¢+1 Î \Z, and thus b + c belongs to C₀.

Before we go on to the next problem, it may be helpful and interesting to summarise the effects of adding or multiplying two numbers from two congruence classes. To see how it works, let x Î C₀, y Î C₁, z Î C₁, w Î C₂. Then x=3p₁, y=3p₂+1, z=3p₃+1, w=3p₄+2. Hence:

x+y=3p₁+3p₂+1=3(p₁+p₂)+1 Î C₁. More generally, we write: C₀+C₁=C₁.
y+z=3p₂+1+3p₃+1=3(p₂+p₃)+2 Î C₂. More generally, we write: C₁+C₁=C₂.
yz=(3p₂+1)·(3p₃+1)=9p₂p₃+ 3(p₂+p₃)+1 Î C₁. More generally, we write: C₁·C₁=C₁.
zw=(3p₃+1)·(3p₄+2)=9p₃p₄+ 6p₃+3p₄)+2 Î C₂. More generally, we write: C₁·C₂=C₂.
The last one is the one we used above - in addition to the observation that no other products will give C₂. Can you see the quick way to find sums and products? Just add or multiply the subscript (i.e. the remainder) and express the result modulo 3 (remainder when divided by 3). The neatest way to write this is to use the notation invented by Gauss for congruence modulo 3:
a(mod 3)+b(mod 3)=(a+b)(mod 3),  a(mod 3)×b(mod 3)=(a·b)(mod 3).
Here is the full set of results:

2.   Let [x] denote the greatest integer less than or equal to the real number x, for example [3.1] = 3 and [4.9] = 4. Show that, for any integer n, [(2+Ö3)ⁿ] is an odd number.

Solution: When you see two numbers in a bracket to some power, you think ``maybe expand by binomial theorem!'' Consider

an=(2+Ö3)n = n å k=0  æ ç è k n ö ÷ ø 2n-k(Ö3)k = 2n+n2n-1Ö3+  n(n-1) 2 2n-2(Ö3)2+¼+(Ö3)n.

Now the question is talking about integers, and the only way we will get this to be integral, is to take only the even powers of Ö3. How can we eliminate the odd powers? By expanding b_n=(2-Ö3)ⁿ and adding!

bn=(2-Ö3)n = n å k=0  æ ç è k n ö ÷ ø 2n-k(Ö3)k(-1)k = 2n-n2n-1Ö3+  n(n-1) 2 2n-2(Ö3)2+¼+(-Ö3)n.

Hence a_n+b_n=2(2ⁿ+[(n(n-1))/2]2^n-23+¼)=2t,
where t is an integer. Now observe that a_n=(a_n+b_n)-b_n=2t-b_n, and this ``remainder''b_n is small: 0 < 2-Ö3 < 1 Þ 0 < b_n < 1, and so we have [a_n]=[2t-b_n]=2t-1, an odd number, as required.

3.   Show that \ds[ 1/(u)]+[ 1/(v)]+[ 1/(w)] ³ 1, where
u=Ö{1+8x}, v=Ö{1+8y}, w=Ö{1+8z},  with x,  y,  z ³ 0  and  xyz = 1.

Hence conclude that

a Ö a2+8bc +  b Ö b2+8ca +  c Ö c2+8ab ³ 1

where a,  b, and c are positive real numbers.

Solution: The first thing to try is to simplify the inequality, which suggests multiplying across by uvw and then (to get rid of root signs) squaring both sides, which will yield an equivalent inequality (since numbers are positive):

(vw+uw+uv)2 ³ (uvw)2, Û  v2w2+u2w2+u2v2+2uvw(u+v+w) ³ u2v2w2,

Û  (1+8y)(1+8z)+(1+8x)(1+8z)+(1+8x)(1+8y)+2uvw(u+v+w)
                                        ³ (1+8x)(1+8y)(1+8z).

(It seems sensible to keep those nice symmetric terms in u,v,w rather than have ugly root signs messing things up.) Simplifying this, and using the given fact xyz=1, yields:

4(x+y+z)+uvw(u+v+w) ³ 255.

This is the inequality we set out to prove. There being two sums on the left, we are reminded of the AM-GM inequality - that the arithmetic mean of a set of numbers is equal to their geometric mean if they are all equal, otherwise is greater - which is what we want in our inequality.

Thus [ 1/3](x+y+z) ³ ³Ö{xyz} and [ 1/3](u+v+w) ³ ³Ö{uvw}.

Since xyz=1, we have

LHS ³ 4×3+3(uvw)[ 4/3]=12+3(u2v2w2)[ 2/3] ³ 12+3((1+8x)(1+8y)(1+8z))[ 2/3] ³ 12+3(1+8(x+y+z)+64(xy+yz+zx)+512)[ 2/3] ³ 12+3(1+8(3xyz)+64(3.x2y2z2)+512)[ 2/3] ³ 12+3(1+8(3)+82(3)+83)[ 2/3]=12+3((1+8)3)[ 2/3] = 12+3.92=255.

This is the required inequality. Note that we have equality when x = y = z=1,   u = v = w = 3.

The final conclusion easily follows by putting x=[(bc)/(a²)], y=[(ac)/(b²)], z=[(ab)/(c²)].

4.   Let M be a point in the interior of triangle ABC. Let X lie on BC and be such that MX is perpendicular to BC. Similarly, let Y lie on CA with MY perpendicular to CA and let Z lie on AB with MZ perpendicular to AB.

Let p(M)=\ds[(MX)/(MA)]·[(MY)/(MB)]·[(MZ)/(MC)]. Determine, with proof, the location of M such that the quantity p(M) is maximized.

Solution: Look at the diagram below, and ask yourself what angles have sines/cosines/tangents defined by those lengths involved in the expression p(M). Then label them, as well as the three angles of the triangle, in a sensible way:

a = B[^(A)]C, b = A[^(B)]C, g = A[^(C)]B,  a₁ = B[^(A)]M, b₁ = M[^(B)]C,  g₁ = A[^(C)]M, a₂ = M[^(A)]C, b₂ = A[^(B)]M, g₂ = M[^(C)]B.

Clearly

p(M)=  MX MA .  MY MB .  MZ MC =sina1sinb1sing1=sina2sinb2sing2.

so that p(M) is the product of all six sines! Now we naturally think of using known trigonometric formulas for products of sines:

sina1sina2=  1 2 (cos(a1-a2)- cos(a1+a2)) £  1 2 (1-cosa)=sin2  a 2 ,

since cos(a₁-a₂) £ 1,  a₁+a₂=a.

Similarly

sinb1sinb2 £ sin2  b 2 ,  sing1sing2 £ sin2  g 2 .

Thus p(M) £ sin[(a)/2]sin[(b)/2]sin[(g)/2], with the right-hand side the required maximum value of p(M), which it will attain if and only if a₁=a₂, b₁=b₂, g₁=g₂. That is, when M is the point where the three angle-bisectors meet, which is the centre of the inscribed circle of triangle ABC.

5.   Twenty-one girls and twenty-one boys took part in a mathematical competition. It turned out that

(a)   each contestant solved at most six problems, and
(b)   for each pair of a girl and a boy, there was at least one problem that was solved by both the girl and the boy.

Show that there is a problem that was solved by at least three girls and at least three boys.

(HINT: Think of putting an integer in each of the 441 squares of a 21×21 board; colour a square black if its integer appears in ³ 3 rows, and red if £ 2 rows. Find upper bounds for the number of red/black squares.)

Solution: (Slightly different to the method of the HINT.) Let P be the set of problems, G the set of girls and B the set of boys. Let G(p) be the set of girls that solve problem p and let B(p) be the set of boys that solve problem p. Let P(g) be the set of problems solved by girl g and let P(b) be the set of problems solved by boy b.

Suppose, in contradiction of the requirement, that for every p Î P either |G(p)| < 3 or |B(p)| < 3. For each problem p Î P, assign the colour red to p if |G(p)| < 3 and assign p the colour black if |B(p)| < 3.

Consider a chessboard with 21 rows, each representing one of the girls, and 21 columns, each one representing one of the boys. For each g Î G and for each b Î B, colour the square corresponding to (g, b) as follows:

Select p Î P(g)ÇP(b) (we are given (b) that there is at least one problem solved by both the girl g and the boy b), and assign p's colour to that square. By the Pigeonhole principle, one of the two colours is assigned to at least 221 squares, and thus some row has at least 11 black squares or some column has at least 11 red squares.

Suppose the row assigned to g Î G has at least 11 black squares. Then, for each of the 11 squares, the black problem that was chosen in assigning the colour was solved by at most 2 boys (that's what `black' means). Thus we account for at least [11/2]=6 distinct problems solved by girl g. Condition (a) tells us that g solved no more than these 6 problems. But then at most 12 boys solve a problem also solved by g, in violation of condition (b).

In exactly the same way, a contradiction is reached if we suppose that some column has at least 11 red squares. Hence there is some p Î P with |G(p)| ³ 3 and |B(p)| ³ 3.

It is interesting to observe that this result does not hold for 20 boys and 20 girls, with the same conditions (a), (b). Consider the 20-by-20 array below, divided into four 10-by-10 quadrants, each chopped up into five 2-by-10 rectangles.

They are placed in a special way, lying vertically in second and fourth quadrants, and horizontally in first and third quadrants. Label these rectangles 1,2, ... 20 (order doesn't matter), and fill each rectangle's little squares with the number of its label; we have done that for the first rectangle in the array. Now you can check that, because each row intersects 5 vertical rectangles and 1 horizontal rectangle, it contains exactly 6 numbers. The same is true for each column. But any one of those 20 numbers is either in 10 rows and 2 columns, or in 2 rows and 10 columns; thus it cannot be in 3 rows and 3 columns!

Generalizing what we have done: in a 4n+1 by 4n+1 array with at most n+1 different integers in each row and each column, there is some integer that appears in at least 3 rows and 3. But this is not true for a 4n by 4n array.

We are indebted to John Scholes for these remarks and the counterexample. The website is:
http://www.kalva.demon.co.uk/imo/isoln/isoln013.html
More IMO problems can be found at: http://www.imo.math.ca/Exams/