16th Mexico 2002 Problem B2 A trio is a set of three distinct integers such that two of the numbers are divisors or multiples of the third. Which trio contained in {1, 2, ... , 2002} has the largest possible sum? Find all trios with the maximum sum.
(a, 2002-a, 2002), where a = 1, 2, 7, 11, 13, 14, 22, 26, 77, 91, 143, 154, 182, 286. Solution Let the numbers be a < b < c. There are 3 possibilities: (1) a and b are divisors/multiples of c; (2) a and c are divisors/multiples of b, so a must divide b and b must divide c; (3) b and c are both divisors/multiples of a. In case (1) a and b must both divide c, so b ≤ c/2 and a ≤ c/3, so a + b + c ≤ 11c/6 < 4004. In case (2), a and b both divide c, so this is a special case of (1). In this case (3) b and c must both be multiples of a. Hence b ≤ c - a, so a + b + c ≤ 2c ≤ 4004. We can achieve 4004 by, for example, (a,b,c) = (1,2001,2002). So 4004 is the maximum sum. Evidently it can only be achieved in case (3) and only by taking c = 2002, a + b = 2002, and a a divisor of 2002. There are 14 divisors of 2002 (apart from 2002 and 1001, which do not work, since a, b, c must be distinct), and each gives a solution. For example, (1,2001,2002), (2,2000,2002), (7,1995,2002). 16th Mexican 2002 © John Scholes jscholes@kalva.demon.co.uk 5 March 2004 Last corrected/updated 5 Mar 04