Is it possible to choose 1983 distinct positive integers, all less than or equal to 105, no three of which are consecutive terms of an arithmetic progression?
Solution
We may notice that an efficient way to build up a set with no APs length 3 is as follows. Having found 2n numbers in {1, 2, ... , un} we add the same pattern starting at 2un, thus giving 2n+1 numbers in {1, 2, ... , 3un-1}. If x is in the first part and y, z in the second part, then 2y is at least 4un, whereas x + z is less than 4un, so x, y, z cannot be an AP length 3. If x and y are in the first part, and z in the second part, then 2y is at most 2un, but x + z is more than 2un, so x, y, z cannot be an AP length 3. To start the process off, we have the 4 numbers 1, 2, 4, 5 in {1, 2, 3, 4, 5}. So u2 = 5. This gives u11 = 88574, in other words we can find 2048 numbers in the first 88574 with no AP length 3.
If we are lucky, we may notice that if we reduce each number in the set we have constructed by 1 we get the numbers which have no 2 when written base 3. This provides a neater approach. Take x, y, z with no 2 when written in base 3. Then 2y has only 0s and 2s when written base 3. But x + z only has no 1s if x = z. So x, y, z cannot form an AP length 3. Also there are 211 = 2048 numbers of this type with 11 digits or less and hence ≤ 111111111113 = 88573.
Solutions are also available in Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
14 Oct 1998