2007/08 AHSMC Part 1 Problem 7

Problem 7 of 16

We wish to choose some of the positive integers from $1$ to $1000$ inclusive, such that no two differ by $3$ or $5$ . The maximum number of positive integers we can choose is

Show solution

Solution

If we take all the even numbers, clearly no two will differ by $3$ or $5$ . Hence we can take at least $500$ numbers. Now partition the integers from $1$ to $1000$ into blocks of $10$ . From each of the following five pairs, we can take at most one number: $(10n + 1, 10n + 4)$ , $(10n + 2, 10n + 5)$ , $(10n + 3, 10n + 8)$ , $(10n + 6, 10n + 9)$ and $(10n + 7, 10n + 10)$ . Hence we can take no more than $500$ numbers. The answer is (D).

University of Alberta

Answer choices

Solution