Let A be a set of positive integers such that |m - n| ≥ mn/25 for any m, n in A. Show that A cannot have more than 9 elements. Give an example of such a set with 9 elements.
Solution
Solution by Demetres Christofides
It is easy to check that {1, 2, 3, 4, 6, 8, 12, 24, 600} satisfies the conditions. Clearly if m > n > k and mn/25 ≤ m - n, then mk/25 < mn/25 ≤ m - n < m - k. So it is sufficient to check the pairs (m, n) = (2, 1), (3, 2), (4, 3), (6, 4), (8, 6), (12, 8), (24, 12), (600, 24). The first four obviously work because mn < 25. For (8, 6), we have mn/25 = 48/25 < 2 = 8 - 6. For (12, 8) we have mn/25 = 96/25 < 4 = 12 - 8. For (24, 12) we have mn/25 = 288/25 < 12 = 24 - 12. For (600, 24) we have mn/25 = 242 = 600 - 24.
Now consider A = {n1, n2, ... , nk}. Obviously all ni must be distinct, so we may assume n1 > n2 > ... > nk. We have n1 - n2 = n1n2/25. But n1 - n2 < n1, so n2/25 < 1 and hence n2 ≤ 24.
Similarly, n2 - n3 = n2n3/25, so n3 = n2(1 - n3/25) ≤ 24(1 - n3/25). Hence n3 ≤ 24·25/49. So n3 ≤ 12.
Similarly, n4 ≤ 12(1 - n4/25), so n4 ≤ 12·25/37 = 8.1, so n4 ≤ 8.
Similarly, n5 ≤ 8(1 - n5/25), so n5 ≤ 8·25/33 = 6.1, so n5 ≤ 6.
Similarly, n6 ≤ 6(1 - n6/25), so n6 ≤ 6·25/31 = 4.8, so n6 ≤ 4. Hence n7 ≤ 3, n8 ≤ 2, n9 ≤ 1. All elements are required to be positive, so 9 is the largest possible number.
© John Scholes
jscholes@kalva.demon.co.uk
11 Sep 2002