Competition problem — Number theory

Library / /79 of 348

Number theory Difficulty 4.7 AIME Find the answer

Let $S$ be a subset of the set $\{1,2,3, \ldots, 2015\}$ such that for any two elements $a, b \in S$ , the difference $a-b$ does not divide the sum $a+b$ . Find the maximum possible size of $S$ .

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

From each of the sets $\{1,2,3\},\{4,5,6\},\{7,8,9\}, \ldots$ at most 1 element can be in $S$ . This leads to an upper bound of $\left\lceil\frac{2015}{3}\right\rceil=672$ which we can obtain with the set $\{1,4,7, \ldots, 2014\}$ .

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.