1990 AMC 12 第 29 题

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

将整数分成形如

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.

其他年份的第 29 题