2017 AIME I Problem 12

Attempt Problem 12 of the 2017 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2017 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

12.

Call a set SS product-free if there do not exist a,a, b,b, cSc \in S (not necessarily distinct) such that ab=c.ab = c. For example, the empty set and the set {16,20}\{16, 20\} are product-free, whereas the sets {4,16}\{4, 16\} and {2,8,16}\{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}.\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}.

Answer: 252
Concepts:subsetscasework
Difficulty rating: 3060
Small Hint:

11 can never appear (since 11=11 \cdot 1 = 1), and if the least element is at least 4,4, every product of two elements exceeds 1010

Big Hint:

With least element 22 or 3,3, only a few conflicts matter: 22=4,2 \cdot 2 = 4, 23=6,2 \cdot 3 = 6, 25=10,2 \cdot 5 = 10, and 33=9.3 \cdot 3 = 9. Handle {3,6,9}\{3, 6, 9\} and {5,10}\{5, 10\} separately.

Solution:

Since 11=1,1 \cdot 1 = 1, no product-free set contains 1.1. Split by the least element t.t. If t4,t \ge 4, any product of two elements is at least 16>10,16 \gt 10, so every subset of {4,5,,10}\{4, 5, \ldots, 10\} works: 27=1282^7 = 128 subsets, including the empty set.

If t=2:t = 2: then 4S4 \notin S (as 22=42 \cdot 2 = 4), while 77 and 88 are unrestricted (22 choices each). Among {3,6,9},\{3, 6, 9\}, the constraints 23=62 \cdot 3 = 6 and 33=93 \cdot 3 = 9 leave exactly ,\varnothing, {3},\{3\}, {6},\{6\}, {9},\{9\}, {6,9}\{6, 9\}55 choices. Among {5,10},\{5, 10\}, the constraint 25=102 \cdot 5 = 10 leaves 33 choices. That gives 2253=602 \cdot 2 \cdot 5 \cdot 3 = 60 sets. If t=3:t = 3: then 9S9 \notin S (as 33=93 \cdot 3 = 9), and any subset of {4,5,6,7,8,10}\{4, 5, 6, 7, 8, 10\} may be added since all other products exceed 10:10: 26=642^6 = 64 sets.

In total there are 128+60+64=252128 + 60 + 64 = 252 product-free subsets.

Problem 11#11
Full Exam

Problem 12 in Other Years