2017 AIME I Problems/Problem 12

Problem 12

Call a set $S$ product-free if there do not exist $a, b, c \in S$ (not necessarily distinct) such that $a b = c$ . For example, the empty set and the set $\{16, 20\}$ are product-free, whereas the sets $\{4, 16\}$ and $\{2, 8, 16\}$ are not product-free. Find the number of product-free subsets of the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ .

Solution

We shall solve this problem by doing casework on the lowest element of the subset. Note that the number $1$ cannot be in the subset because $1*1=1$ . Let $S$ be a product-free set. If the lowest element of $S$ is $2$ , we consider the set $\{3, 6, 9\}$ . We see that 5 of these subsets can be a subset of $S$ ( $\{3\}$ , $\{6\}$ , $\{9\}$ , $\{6, 9\}$ , and the empty set). Now consider the set $\{5, 10\}$ . We see that 3 of these subsets can be a subset of $S$ ( $\{5\}$ , $\{10\}$ , and the empty set). Note that $4$ cannot be an element of $S$ , because $2$ is. Now consider the set $\{7, 8\}$ . All four of these subsets can be a subset of $S$ . So if the smallest element of $S$ is $2$ , there are $5*3*4=60$ possible such sets.

If the smallest element of $S$ is $3$ , the only restriction we have is that $9$ is not in $S$ . This leaves us $2^6=64$ such sets.

If the smallest element of $S$ is not $2$ or $3$ , then $S$ can be any subset of $\{4, 5, 6, 7, 8, 9, 10\}$ , including the empty set. This gives us $2^7=128$ such subsets.

So our answer is $60+64+128=\boxed{252}$ .

2017 AIME I (Problems • Answer Key • Resources)
Preceded by Problem 11	Followed by Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2017 AIME I Problems/Problem 12

Problem 12

Solution

See Also