4th APMC 1981 Problem 1 Find the smallest n for which we can find 15 distinct elements a 1 , a 2 , ... , a 15 of {16, 17, ... , n} such that a k is a multiple of k.
The following arrangement shows that n = 34 works: a 1 = 17, , a 2 = 34, a 3 = 33, a 4 = 32, a 5 = 25 a 6 = 18, a 7 = 21, a 8 = 16, a 9 = 27, a 10 = 20 a 11 = 22, a 12 = 24, a 13 = 26, a 14 = 28, a 15 = 30 If we could use all the numbers in the set, then n = 30 would be the smallest, but we can use at most one of 17, 19, 23, 29 (for a 1 ), so n ≥ 33. But if we use one of those primes, then we cannot use 31, so n ≥ 34. 4th APMC 1981 © John Scholes jscholes@kalva.demon.co.uk 14 February 2004 Last corrected/updated 14 Feb 04