Question

Llamamos a un conjunto

S

libre de productos si no existen

a,

b,

c \in S

(no necesariamente distintos) tales que

ab = c.

Por ejemplo, el conjunto vacío y el conjunto

\{16, 20\}

son libres de productos, mientras que los conjuntos

\{4, 16\}

y

\{2, 8, 16\}

no son libres de productos. Halla el número de subconjuntos libres de productos del conjunto

\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}.

Call a set

S

product-free if there do not exist

a,

b,

c \in S

(not necessarily distinct) such that

ab = c.

For example, the empty set and the set

\{16, 20\}

are product-free, whereas the sets

\{4, 16\}

and

\{2, 8, 16\}

are not product-free. Find the number of product-free subsets of the set

\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}.

Respuesta

Respuesta: 252

Conceptos:subconjuntos análisis por casos

Nivel de dificultad: 3060

Pista pequeña:

1

nunca puede aparecer (ya que

1 \cdot 1 = 1

), y si el elemento más pequeño es al menos

4,

todo producto de dos elementos supera

10

1

can never appear (since

1 \cdot 1 = 1

), and if the least element is at least

4,

every product of two elements exceeds

10

Pista grande:

Con elemento más pequeño

2

o

3,

solo importan unos pocos conflictos:

2 \cdot 2 = 4,

2 \cdot 3 = 6,

2 \cdot 5 = 10,

y

3 \cdot 3 = 9.

Trata

\{3, 6, 9\}

y

\{5, 10\}

por separado.

With least element

2

or

3,

only a few conflicts matter:

2 \cdot 2 = 4,

2 \cdot 3 = 6,

2 \cdot 5 = 10,

and

3 \cdot 3 = 9.

Handle

\{3, 6, 9\}

and

\{5, 10\}

separately.

Solución:

Como

1 \cdot 1 = 1,

ningún conjunto libre de productos contiene a

1.

Separa según el elemento más pequeño

t.

Si

t \ge 4,

todo producto de dos elementos es al menos

16 \gt 10,

así que todo subconjunto de

\{4, 5, \ldots, 10\}

sirve:

2^7 = 128

subconjuntos, incluyendo el conjunto vacío.

Si

t = 2:

entonces

4 \notin S

(pues

2 \cdot 2 = 4

), mientras que

7

y

8

no tienen restricción (

2

opciones cada uno). Entre

\{3, 6, 9\},

las restricciones

2 \cdot 3 = 6

y

3 \cdot 3 = 9

dejan exactamente

\varnothing,

\{3\},

\{6\},

\{9\},

\{6, 9\}

, es decir,

5

opciones. Entre

\{5, 10\},

la restricción

2 \cdot 5 = 10

deja

3

opciones. Eso da

2 \cdot 2 \cdot 5 \cdot 3 = 60

conjuntos. Si

t = 3:

entonces

9 \notin S

(pues

3 \cdot 3 = 9

), y se puede añadir cualquier subconjunto de

\{4, 5, 6, 7, 8, 10\}

ya que todos los demás productos superan

10:

2^6 = 64

conjuntos.

En total hay

128 + 60 + 64 = 252

subconjuntos libres de productos.

Since

1 \cdot 1 = 1,

no product-free set contains

1.

Split by the least element

t.

If

t \ge 4,

any product of two elements is at least

16 \gt 10,

so every subset of

\{4, 5, \ldots, 10\}

works:

2^7 = 128

subsets, including the empty set.

If

t = 2:

then

4 \notin S

(as

2 \cdot 2 = 4

), while

7

and

8

are unrestricted (

2

choices each). Among

\{3, 6, 9\},

the constraints

2 \cdot 3 = 6

and

3 \cdot 3 = 9

leave exactly

\varnothing,

\{3\},

\{6\},

\{9\},

\{6, 9\}

—

5

choices. Among

\{5, 10\},

the constraint

2 \cdot 5 = 10

leaves

3

choices. That gives

2 \cdot 2 \cdot 5 \cdot 3 = 60

sets. If

t = 3:

then

9 \notin S

(as

3 \cdot 3 = 9

), and any subset of

\{4, 5, 6, 7, 8, 10\}

may be added since all other products exceed

10:

2^6 = 64

sets.

In total there are

128 + 60 + 64 = 252

product-free subsets.

2017 AIME I Problema 12

Respuesta: 252

Nivel de dificultad: 3060

Pista pequeña:

Pista grande:

Solución:

El Problema 12 en otros años