Maths Olympiad Prep

Library / /6 of 11

Number theory Difficulty 5.8 AIME, harder Prove it Estonia

Given positive integers aa, bb, cc and dd and
(a+b)(a+c)(a+d)(b+c)(b+d)(c+d)=u, (a+b)(a+c)(a+d)(b+c)(b+d)(c+d) = u,
ab+ac+ad+bc+bd+cd=v, ab + ac + ad + bc + bd + cd = v,
prove that the product uvuv is divisible by 3.

Solution

If among numbers aa, bb, cc, dd there are two that give either remainders 00 and 00 or remainders 11 and 22 modulo 33, the sum of these two numbers is divisible by 33. Hence uu, as well as uvuv, is divisible by 33.

Now study the case where at most one among the numbers aa, bb, cc, dd is divisible by 33 and all numbers not divisible by 33 are congruent modulo 33. If exactly one among numbers aa, bb, cc, dd is divisible by 33 then the products of this number with all other numbers are divisible by 33. Other numbers form 33 pairs whose products of components are congruent modulo 33. Hence the sum vv of all six pairwise products is divisible by 33.

If none of aa, bb, cc, dd is divisible by 33 then the pairwise products are all congruent modulo 33. Again, as the number of pairs is divisible by 33, this implies that the sum vv of the products is divisible by 33. Consequently, uvuv is divisible by 33 in this case, too.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.