Track / Stage 4 / 179 of 340 #919 of 2444

Problem 919

AMC 12 late, AIME early

Number theory Difficulty 4.7 Find the answer HMMT November

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. Fractions can be typed as 3/2, and spacing doesn't matter.

Official 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\}$ .

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.