1990 AMC 12 Problema 29

Question

Un subconjunto de los enteros

1,

2,

\ldots,

100

tiene la propiedad de que ninguno de sus elementos es

3

veces otro. ¿Cuál es la mayor cantidad de elementos que puede tener ese subconjunto?

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

Agrupa los enteros en cadenas

m,3m,9m,\ldots

donde

m

no es múltiplo de

3

Group integers into chains

m,3m,9m,\ldots

where

m

is not a multiple of

3

Dentro de cada cadena, elegir términos alternos produce una selección máxima permitida

Within each chain, alternating entries give a largest allowed selection

Divide los enteros en cadenas

m,3m,9m,\ldots,

donde

m

no es múltiplo de

3.

En cada cadena no se pueden elegir dos términos adyacentes, de modo que una selección máxima toma términos alternos comenzando con

m.

De manera equivalente, elige los enteros cuyo exponente de

3

es par. Hay

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

El argumento de las cadenas también demuestra que no es posible una selección mayor.

Por tanto, la respuesta correcta es 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.

El Problema 29 en otros años