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$

Respuesta: D

Conceptos:extremal combinatorics powers independent set

Nivel de dificultad: 2340

Pista pequeña:

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$

Pista grande:

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

Solución:

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.

1990 AMC 12 Problema 29

Respuesta: D

Nivel de dificultad: 2340

Pista pequeña:

Pista grande:

Solución:

El Problema 29 en otros años