2017 AIME I 第 12 题

先试着解答 2017 AIME I 第 12 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2017 AIME I 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

12.

如果集合 SS 中不存在 a,b,cSa, b, c \in S(不要求互不相同)使得 ab=cab = c,就称 S 为无积集合。例如,空集和集合 {16,20}\{16, 20\} 是无积集合,而集合 {4,16}\{4, 16\}{2,8,16}\{2, 8, 16\} 不是无积集合。求集合 {1,2,3,4,5,6,7,8,9,10}\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} 的无积子集个数。

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

答案:252
知识点:子集分类讨论
难度评级:3060
解答:

因为 11=11 \cdot 1 = 1,任何无积集合都不能含有 11。按最小元素 tt 分类。如果 t4t \ge 4,任意两个元素的乘积至少为 16>1016 \gt 10,所以 {4,5,,10}\{4, 5, \ldots, 10\} 的每个子集都可行:共有 27=1282^7 = 128 个子集,包括空集。

t=2t = 2:则 4S4 \notin S(因为 22=42 \cdot 2 = 4),而 7788 不受限制 (各有 22 种选择)。在 {3,6,9}\{3, 6, 9\} 中,约束 23=62 \cdot 3 = 633=93 \cdot 3 = 9 只留下 ,{3},{6},{9},{6,9}\varnothing, \{3\}, \{6\}, \{9\}, \{6, 9\}55 种选择。在 {5,10}\{5, 10\} 中, 约束 25=102 \cdot 5 = 10 留下 33 种选择。因此得到 2253=602 \cdot 2 \cdot 5 \cdot 3 = 60 个集合。若 t=3t = 3:则 9S9 \notin S(因为 33=93 \cdot 3 = 9),并且可以任意加入 {4,5,6,7,8,10}\{4, 5, 6, 7, 8, 10\} 的子集,因为其他乘积都超过 1010:所以有 26=642^6 = 64 个集合。

总共有 128+60+64=252128 + 60 + 64 = 252 个无积子集。

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.

← 第 11 题#11
完整试卷

其他年份的第 12 题