2017 AIME I Problem 12

Below is the professionally curated solution for Problem 12 of the 2017 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:subsetscasework

Difficulty rating: 3060

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

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 11Full ExamProblem 13

Problem 12 in Other Years