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