2018 AMC 12A Problema 12

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.