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,b,cSa, b, c \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
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 ,{3},{6},{9},{6,9}\varnothing, \{3\}, \{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