Question

Halle el número de subconjuntos de cuatro elementos de $\{1, 2, 3, 4, \ldots, 20\}$ con la propiedad de que dos elementos distintos del subconjunto tienen suma $16,$ y dos elementos distintos del subconjunto tienen suma $24.$ Por ejemplo, $\{3, 5, 13, 19\}$ y $\{6, 10, 20, 18\}$ son dos de tales subconjuntos.

Find the number of four-element subsets of $\{1, 2, 3, 4, \ldots, 20\}$ with the property that two distinct elements of the subset have a sum of $16,$ and two distinct elements of the subset have a sum of $24.$ For example, $\{3, 5, 13, 19\}$ and $\{6, 10, 20, 18\}$ are two such subsets.

Respuesta

Solución:

Los pares de elementos distintos que suman $16$ son $\{1,15\}, \{2,14\}, \ldots, \{7,9\}$ (siete pares), y los que suman $24$ son $\{4,20\}, \{5,19\}, \ldots, \{11,13\}$ (ocho pares). Primero contamos los subconjuntos que contienen un $16$ -par y un $24$ -par disjuntos. De las $7 \cdot 8 = 56$ combinaciones, las que comparten un elemento $x$ requieren que $16 - x,$ $x,$ y $24 - x$ sean todos válidos, lo que ocurre para los $10$ valores $x \in \{4, \ldots, 15\}$ distintos de $8$ y $12.$ Ningún conjunto de cuatro elementos surge de dos combinaciones disjuntas diferentes (una segunda descomposición obligaría a que un $16$ -par coincida con un $24$ -par), así que este caso da $56 - 10 = 46$ subconjuntos.

En los subconjuntos restantes cada $16$ -par corta a cada $24$ -par, así que algún centro $a$ tiene tanto $b = 16 - a$ como $c = 24 - a$ en el subconjunto. Hay $10$ centros posibles ( $a \in \{4, \ldots, 15\}$ con $a \ne 8, 12$ ), y el cuarto elemento puede ser cualquiera de los $17$ números restantes, dando $170$ conteos centro–subconjunto. Exactamente $6$ subconjuntos admiten dos centros y se cuentan dos veces: $\{1,7,9,15\},$ $\{2,6,10,14\},$ $\{3,5,11,13\},$ $\{5,11,13,19\},$ $\{6,10,14,18\},$ y $\{7,9,15,17\}.$ Este caso da $170 - 6 = 164$ subconjuntos, ninguno de los cuales contiene pares disjuntos.

El total es $46 + 164 = 210.$

The pairs of distinct elements summing to $16$ are $\{1,15\}, \{2,14\}, \ldots, \{7,9\}$ (seven pairs), and those summing to $24$ are $\{4,20\}, \{5,19\}, \ldots, \{11,13\}$ (eight pairs). First count subsets containing a $16$ -pair and a $24$ -pair that are disjoint. Of the $7 \cdot 8 = 56$ combinations, the ones sharing an element $x$ require $16 - x,$ $x,$ and $24 - x$ all to be valid, which happens for the $10$ values $x \in \{4, \ldots, 15\}$ other than $8$ and $12.$ No four-element set arises from two different disjoint combinations (a second decomposition would force a $16$ -pair to coincide with a $24$ -pair), so this case gives $56 - 10 = 46$ subsets.

In the remaining subsets every $16$ -pair meets every $24$ -pair, so some center $a$ has both $b = 16 - a$ and $c = 24 - a$ in the subset. There are $10$ possible centers ( $a \in \{4, \ldots, 15\}$ with $a \ne 8, 12$ ), and the fourth element can be any of the $17$ remaining numbers, giving $170$ center–subset counts. Exactly $6$ subsets admit two centers and are counted twice: $\{1,7,9,15\},$ $\{2,6,10,14\},$ $\{3,5,11,13\},$ $\{5,11,13,19\},$ $\{6,10,14,18\},$ and $\{7,9,15,17\}.$ This case gives $170 - 6 = 164$ subsets, none of which contain disjoint pairs.

The total is $46 + 164 = 210.$

2018 AIME I Problema 9

Solución:

El Problema 9 en otros años