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

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

Solución:

El Problema 12 en otros años