Question

设 $S$ 是从 $\{1, 2, \ldots, 12\}$ 中选出的 $6$ 个整数的集合，且满足：若 $a$ 和 $b$ 是 $S$ 的元素且 $a \lt b$ ，则 $b$ 不是 $a$ 的倍数。 $S$ 中元素的最小可能值是多少？

Let $S$ be a set of $6$ integers taken from $\{1, 2, \ldots, 12\}$ with the property that if $a$ and $b$ are elements of $S$ with $a \lt b,$ then $b$ is not a multiple of $a.$ What is the least possible value of an element of $S?$

$2$

$3$

$4$

$5$

$7$

答案：C

知识点：整除性抽屉原理极端原理

难度评级：1630

小提示：

把 $\{1, \ldots, 12\}$ 分成若干链，每条链中前一个数整除后一个数： $\{1,2,4,8\}$ ， $\{3,6,12\}$ ， $\{5,10\}$ ， $\{7\}$ ， $\{9\}$ ， $\{11\}$ 。

Group $\{1, \ldots, 12\}$ into chains where each number divides the next: $\{1,2,4,8\},$ $\{3,6,12\},$ $\{5,10\},$ $\{7\},$ $\{9\},$ $\{11\}$

大提示：

每条链至多取一个元素；共有 $6$ 条链， $S$ 必须每条链正好取一个元素，迫使 $7, 9, 11 \in S$ 。

At most one element comes from each chain; with $6$ chains, $S$ must use exactly one from each, forcing $7, 9, 11 \in S$

解答：

将 $\{1, \ldots, 12\}$ 分成六条整除链 $\{1,2,4,8\}$ ， $\{3,6,12\}$ ， $\{5,10\}$ ， $\{7\}$ ， $\{9\}$ ， $\{11\}$ 。因为 $S$ 中不能有一个元素整除另一个元素，所以每条链至多贡献一个元素；需要 $6$ 个元素就迫使每条链正好取一个，因此 $7, 9, 11 \in S$ 。

因为 $9 \in S$ ，所以 $3 \notin S$ ，第二条链贡献 $6$ 或 $12$ ，于是第一条链中既不能选 $1$ 也不能选 $2$ （它们会整除 $6$ 和 $12$ ）。从第一条链取 $4$ 可以做到： $S = \{4, 5, 6, 7, 9, 11\}$ 满足条件。因此最小可能元素是 $4$ 。

所以正确答案是 C。

Partition $\{1, \ldots, 12\}$ into the six divisibility chains $\{1,2,4,8\},$ $\{3,6,12\},$ $\{5,10\},$ $\{7\},$ $\{9\},$ $\{11\}.$ Since no element of $S$ may divide another, at most one comes from each chain; needing $6$ elements forces exactly one from each, so $7, 9, 11 \in S.$

Because $9 \in S,$ $3 \notin S,$ so the second chain contributes $6$ or $12,$ and then neither $1$ nor $2$ can be chosen from the first chain (they divide $6$ and $12$ ). Taking $4$ from the first chain works: $S = \{4, 5, 6, 7, 9, 11\}$ has the property. Hence the least possible element is $4.$

Thus, the correct answer is C.

2018 AMC 12A 第 12 题

答案：C

难度评级：1630

小提示：

大提示：

解答：

其他年份的第 12 题