11th Chinese 1996 Problem A2 What is the smallest k such that any subset of {1, 2, ... , 50} with k elements must have two distinct elements m, n such that m + n divides mn.? Solution
: 39. Put m = m'd, n = n'd, with m' and n' coprime. Then m' + n' divides dm'n'. It cannot divide m' or n', so it must divide d. In particular, m' + n' <= d. We have m + n < 100, so (m' + n') 2 < 100, so m' + n' <= 9. So the possibilities are: m' = n' = 3, hence m' = 1, n' = 2, d = 3, 6, 9, 12, 15, 18, 21 or 24; m' + n' = 4, hence m' = 1, n' = 3, d = 4, 8, 12, 16; m' + n' = 5, hence m' = 1, n' = 4, d = 5, 10, or m' = 2, n' = 3, d = 5, 10 or 15; m' + n' = 6, hence m' = 1, n' = 5, d = 6; m' + n' = 7, hence m' = 1, n' = 6, d = 7, or m' = 2, n' = 5, d = 7, or m' = 3, n' = 4, d = 7; m' + n' = 8, hence m' = 3, n' = 5, d = 8; or m' + n' = 9, hence m' = 4, n' = 5, d = 9. Thus we get the following 23 pairs: 3, 6 6, 12 9, 18 12, 24 15, 30 18, 36 21, 42 24, 48 4, 12 8, 24 12, 36 16, 48 5, 20 10, 40 10, 15 20, 30 30, 45 6, 30 7, 42 14, 35 21, 28 24, 40 36, 45 The following 12 pairs are disjoint: 3, 6 4, 12 5, 20 7, 42 8, 24 9, 18 10, 40 14, 35 15, 30 16, 48 21, 28 36, 45 so any set with 39 elements must contain one of these pairs (to avoid it, its complement would have to have 12 elements, one from each pair). On the other hand, each of the 23 pairs contains at least one of 6, 10, 12, 14, 18, 20, 24, 28, 30, 36 42, 48, so the subset of the other 38 elements {1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 15, 16, 17, 19, 21, 22, 23, 25, 26, 27, 29, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 49, 50} does not contain any of the 23 pairs. 11th Chinese 1996 © John Scholes jscholes@kalva.demon.co.uk 22 June 2002