Competition problem — Combinatorics

Library / /12 of 105

Combinatorics Difficulty 4.9 AIME Prove it JBMO

Problem:
Find the largest number of distinct integers that can be chosen from the set $\{1,2, \ldots, 2013\}$ so that the difference of no two of them is equal to $17$ .

Solution

Solution:
Consider the sets $A_{mn} = \{34m + n - 34, 34m + n - 17\}$ for $1 \leq m \leq 59$ and $1 \leq n \leq 17$ , and $B_k = \{2006 + k\}$ for $1 \leq k \leq 7$ . As we cannot choose more than one number from each of these sets, we can choose at most $59 \cdot 17 + 7 = 1010$ numbers. On the other hand, choosing the smaller element of each of these sets gives exactly $1010$ numbers satisfying the condition.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.