2024 AMC 12A Problems/Problem 16

Problem

How many subsets $S$ of $\{1, 2, 3, \cdots, 15\}$ with at least two elements satisfy the property that if $a$ and $b$ are distinct elements of $S$ , then $|a - b|$ is also an element of $S$ ?

$\textbf{(A)}~30 \qquad \textbf{(B)}~32 \qquad \textbf{(C)}~34 \qquad \textbf{(D)}~36 \qquad \textbf{(E)}~38$

Solution

We claim that the subset $S$ must be of the form $\{d, 2d, \dots, nd\}$ for some $n \geq 2$ such that $nd \leq 15$ .

To see this, suppose the greatest common divisor of all elements in the set $S$ is $d$ . We can generate $d$ into the subset by the Euclidean algorithm. Then, letting $a$ be the largest number and $b = d$ generates all the multiples of $d$ up to the largest number. The least possible number of elements in such a subset is $2$ and the largest is $\left\lfloor\frac{15}{d}\right\rfloor$ . The answer is therefore $\sum_{d=1}^{\lfloor 15/2 \rfloor} \left\lfloor \frac{15}{d} - 1 \right\rfloor = 14 + 6 + 4 + 2 + 2 + 1 + 1 = \boxed{\textbf{(A)}~30}.$

~plang2008

2024 AMC 12A (Problems • Answer Key • Resources)
Preceded by Problem 15	Followed by Problem 17
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions.

Page

Toolbox

Search

2024 AMC 12A Problems/Problem 16

Problem

Solution

See also