Question

整数 $1$ 、 $2$ 、 $\ldots$ 、 $100$ 的一个子集满足：其中没有一个元素是另一个元素的 $3$ 倍。这样的子集最多可以有多少个元素？

A subset of the integers $1,$ $2,$ $\ldots,$ $100$ has the property that none of its members is $3$ times another. What is the largest number of members such a subset can have?

$50$

$66$

$67$

$76$

$78$

答案：D

知识点：extremal combinatorics powers independent set

难度评级：2340

小提示：

将整数分成形如 $m,3m,9m,\ldots$ 的链，其中 $m$ 不是 $3$ 的倍数

Group integers into chains $m,3m,9m,\ldots$ where $m$ is not a multiple of $3$

大提示：

在每条链中交替选取元素，即可得到允许的最大选择数

Within each chain, alternating entries give a largest allowed selection

解答：

将这些整数分成形如 $m,3m,9m,\ldots$ 的链，其中 $m$ 不是 $3$ 的倍数。在每条链中，两个相邻项不能同时选取，所以最大选择方案是从 $m$ 开始隔项选取。等价地，选择质因数 $3$ 的指数为偶数的整数。这样的整数有 $\begin{aligned} &\left(100-\left\lfloor\frac{100}{3}\right\rfloor\right)\\ &\quad+\left(\left\lfloor\frac{100}{9}\right\rfloor -\left\lfloor\frac{100}{27}\right\rfloor\right)\\ &\quad+\left\lfloor\frac{100}{81}\right\rfloor\\ &=67+8+1=76 \end{aligned}\text{。}$ 上述链的论证也证明了不可能选取更多元素。

所以正确答案是 D。

Partition the integers into chains $m,3m,9m,\ldots,$ with $m$ not a multiple of $3.$ In each chain, no two adjacent terms may both be selected, so a maximum selection takes alternating terms starting with $m.$ Equivalently, select the integers whose exponent of $3$ is even. There are $\begin{aligned} &\left(100-\left\lfloor\frac{100}{3}\right\rfloor\right)\\ &\quad+\left(\left\lfloor\frac{100}{9}\right\rfloor -\left\lfloor\frac{100}{27}\right\rfloor\right)\\ &\quad+\left\lfloor\frac{100}{81}\right\rfloor\\ &=67+8+1=76. \end{aligned}$ The chain argument also proves no larger selection is possible.

Thus the correct answer is D.

1990 AMC 12 第 29 题

答案：D

难度评级：2340

小提示：

大提示：

解答：

其他年份的第 29 题