Question

Sea $S$ un conjunto de $6$ enteros tomados de $\{1, 2, \ldots, 12\}$ con la propiedad de que si $a$ y $b$ son elementos de $S$ con $a \lt b,$ entonces $b$ no es múltiplo de $a.$ ¿Cuál es el menor valor posible de un elemento de $S$ ?

Let $S$ be a set of $6$ integers taken from $\{1, 2, \ldots, 12\}$ with the property that if $a$ and $b$ are elements of $S$ with $a \lt b,$ then $b$ is not a multiple of $a.$ What is the least possible value of an element of $S?$

$2$

$3$

$4$

$5$

$7$

Respuesta: C

Conceptos:divisibilidad principio del palomar argumento extremal

Nivel de dificultad: 1630

Pista pequeña:

Agrupa $\{1, \ldots, 12\}$ en cadenas donde cada número divide al siguiente: $\{1,2,4,8\},$ $\{3,6,12\},$ $\{5,10\},$ $\{7\},$ $\{9\},$ $\{11\}$

Group $\{1, \ldots, 12\}$ into chains where each number divides the next: $\{1,2,4,8\},$ $\{3,6,12\},$ $\{5,10\},$ $\{7\},$ $\{9\},$ $\{11\}$

Pista grande:

A lo sumo un elemento proviene de cada cadena; con $6$ cadenas, $S$ debe usar exactamente uno de cada una, lo que obliga a $7, 9, 11 \in S$

At most one element comes from each chain; with $6$ chains, $S$ must use exactly one from each, forcing $7, 9, 11 \in S$

Solución:

Divide $\{1, \ldots, 12\}$ en las seis cadenas de divisibilidad $\{1,2,4,8\},$ $\{3,6,12\},$ $\{5,10\},$ $\{7\},$ $\{9\},$ $\{11\}.$ Como ningún elemento de $S$ puede dividir a otro, a lo sumo uno proviene de cada cadena; necesitar $6$ elementos obliga a exactamente uno de cada una, así que $7, 9, 11 \in S.$

Como $9 \in S,$ $3 \notin S,$ así que la segunda cadena aporta $6$ o $12,$ y entonces ni $1$ ni $2$ pueden elegirse de la primera cadena (dividen a $6$ y $12$ ). Tomar $4$ de la primera cadena funciona: $S = \{4, 5, 6, 7, 9, 11\}$ tiene la propiedad. Por lo tanto el menor elemento posible es $4.$

Por lo tanto, la respuesta correcta es C.

Partition $\{1, \ldots, 12\}$ into the six divisibility chains $\{1,2,4,8\},$ $\{3,6,12\},$ $\{5,10\},$ $\{7\},$ $\{9\},$ $\{11\}.$ Since no element of $S$ may divide another, at most one comes from each chain; needing $6$ elements forces exactly one from each, so $7, 9, 11 \in S.$

Because $9 \in S,$ $3 \notin S,$ so the second chain contributes $6$ or $12,$ and then neither $1$ nor $2$ can be chosen from the first chain (they divide $6$ and $12$ ). Taking $4$ from the first chain works: $S = \{4, 5, 6, 7, 9, 11\}$ has the property. Hence the least possible element is $4.$

Thus, the correct answer is C.

2018 AMC 12A Problema 12

Respuesta: C

Nivel de dificultad: 1630

Pista pequeña:

Pista grande:

Solución:

El Problema 12 en otros años