Question

Para cada subconjunto $T$ de $U = \{1, 2, 3, \ldots, 18\},$ sea $s(T)$ la suma de los elementos de $T,$ con $s(\emptyset)$ definido como $0.$ Si $T$ se elige al azar entre todos los subconjuntos de $U,$ la probabilidad de que $s(T)$ sea divisible por $3$ es $\frac{m}{n},$ donde $m$ y $n$ son enteros positivos primos entre sí. Halle $m.$

For each subset $T$ of $U = \{1, 2, 3, \ldots, 18\},$ let $s(T)$ be the sum of the elements of $T,$ with $s(\emptyset)$ defined to be $0.$ If $T$ is chosen at random among all subsets of $U,$ the probability that $s(T)$ is divisible by $3$ is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m.$

Respuesta

Respuesta: 683

Conceptos:subconjuntos aritmética modular combinaciones Convolución de Vandermonde

Nivel de dificultad: 3060

Pista pequeña:

Cada clase de residuo módulo $3$ contiene exactamente seis elementos de $U,$ y solo importan las cantidades de elementos elegidos $\equiv 1$ y $\equiv 2$

Each residue class modulo $3$ contains exactly six elements of $U,$ and only the numbers of chosen elements $\equiv 1$ and $\equiv 2$ matter

Pista grande:

Con $a$ elementos elegidos $\equiv 1$ y $b$ elementos $\equiv 2,$ se necesita $a \equiv b \pmod 3;$ evalúe $\sum \binom{6}{a}\binom{6}{b}$ usando la identidad de Vandermonde

With $a$ chosen elements $\equiv 1$ and $b$ elements $\equiv 2,$ you need $a \equiv b \pmod 3;$ evaluate $\sum \binom{6}{a}\binom{6}{b}$ using Vandermonde’s identity

Solución:

El conjunto $U$ contiene seis elementos en cada clase de residuo módulo $3.$ Si $T$ contiene $a$ elementos $\equiv 1$ y $b$ elementos $\equiv 2 \pmod 3,$ entonces $s(T) \equiv a + 2b \equiv a - b \pmod 3,$ así que $s(T)$ es divisible por $3$ exactamente cuando $a \equiv b \pmod 3;$ los seis múltiplos de $3$ pueden incluirse libremente, aportando un factor $2^6$ tanto a los conteos favorables como a los totales.

Por la identidad de Vandermonde, el número de maneras de elegir los valores de $a$ y $b$ con $a - b = 0$ es $\sum_a \binom{6}{a}^2 = \binom{12}{6} = 924;$ con $a - b = \pm 3$ es $2\sum_a \binom{6}{a}\binom{6}{a - 3} = 2\binom{12}{9} = 440;$ y con $a - b = \pm 6$ es $2.$ Las elecciones favorables suman $924 + 440 + 2 = 1366$ de un total de $2^{12}.$

La probabilidad es $\frac{1366}{4096} = \frac{683}{2048},$ que está en su mínima expresión ya que $683$ es impar. Así $m = 683.$

The set $U$ contains six elements in each residue class modulo $3.$ If $T$ contains $a$ elements $\equiv 1$ and $b$ elements $\equiv 2 \pmod 3,$ then $s(T) \equiv a + 2b \equiv a - b \pmod 3,$ so $s(T)$ is divisible by $3$ exactly when $a \equiv b \pmod 3;$ the six multiples of $3$ may be included freely, contributing a factor $2^6$ to both the favorable and total counts.

By Vandermonde’s identity, the number of ways to choose the $a$ s and $b$ s with $a - b = 0$ is $\sum_a \binom{6}{a}^2 = \binom{12}{6} = 924;$ with $a - b = \pm 3$ it is $2\sum_a \binom{6}{a}\binom{6}{a - 3} = 2\binom{12}{9} = 440;$ and with $a - b = \pm 6$ it is $2.$ The favorable choices number $924 + 440 + 2 = 1366$ out of $2^{12}.$

The probability is $\frac{1366}{4096} = \frac{683}{2048},$ which is in lowest terms since $683$ is odd. Thus $m = 683.$

2018 AIME I Problema 12

Respuesta: 683

Nivel de dificultad: 3060

Pista pequeña:

Pista grande:

Solución:

El Problema 12 en otros años