1  Solutions to ZMO Round 2, 2002

1.   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:

3.   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(x+y+z) and 1(u+v+w) .Since xyz=1