1990 AMC 12 Problem 29

Question

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

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

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.

Problem 29 in other years