Question

Sea

\mathcal{S}

el conjunto de enteros entre

1

y

2^{40}

cuyas expansiones binarias tienen exactamente dos dígitos

1

. Si se elige un número al azar de

\mathcal{S},

la probabilidad de que sea divisible por

9

es

\frac{p}{q},

donde

p

y

q

son enteros positivos primos entre sí. Halla

p + q.

Let

\mathcal{S}

be the set of integers between

1

and

2^{40}

whose binary expansions have exactly two

1

’s. If a number is chosen at random from

\mathcal{S},

the probability that it is divisible by

9

is

\frac{p}{q},

where

p

and

q

are relatively prime positive integers. Find

p + q.

Respuesta

Respuesta: 913

Conceptos:base numérica exponenciación modular orden multiplicativo conteo de pares

Nivel de dificultad: 2920

Pista pequeña:

Los elementos de

\mathcal{S}

son

2^a + 2^b = 2^a(2^{b-a} + 1)

con

a \lt b,

así que la divisibilidad por

9

depende solo de

b - a

.

Elements of

\mathcal{S}

are

2^a + 2^b = 2^a(2^{b-a} + 1)

with

a \lt b,

so divisibility by

9

depends only on

b - a

Pista grande:

Las potencias de

2

se repiten módulo

9

con periodo

6,

y

2^d \equiv 8

exactamente cuando

d \equiv 3 \pmod{6};

cuenta los pares con cada una de esas diferencias.

Powers of

2

repeat mod

9

with period

6,

and

2^d \equiv 8

exactly when

d \equiv 3 \pmod{6};

count the pairs with each such difference

Solución:

El conjunto

\mathcal{S}

consta de los

\binom{40}{2} = 780

números

2^a + 2^b

con

0 \le a \lt b \le 39.

Como

2^a

es coprimo con

9,

tenemos

2^a(2^{b-a} + 1)

divisible por

9

exactamente cuando

2^{b-a} \equiv -1 \pmod{9}.

Las potencias de

2

módulo

9

recorren

2, 4, 8, 7, 5, 1

con periodo

6,

así que

2^d \equiv 8 \equiv -1

exactamente cuando

d \equiv 3 \pmod{6}.

Para cada diferencia

d = b - a

hay

40 - d

pares, así que el número de múltiplos de

9

en

\mathcal{S}

es

\begin{aligned} &\sum_{d = 3, 9, \ldots, 39} (40 - d) \\ &= 37 + 31 + 25 \\ &\quad {}+ 19 + 13 + 7 + 1 \\ &= 133. \end{aligned}

La probabilidad es

\frac{133}{780},

y como

133 = 7 \cdot 19

mientras que

780 = 2^2 \cdot 3 \cdot 5 \cdot 13,

está en su forma más simple. Por tanto

p + q = 133 + 780 = 913.

The set

\mathcal{S}

consists of the

\binom{40}{2} = 780

numbers

2^a + 2^b

with

0 \le a \lt b \le 39.

Since

2^a

is coprime to

9,

we have

2^a(2^{b-a} + 1)

divisible by

9

exactly when

2^{b-a} \equiv -1 \pmod{9}.

The powers of

2

modulo

9

cycle through

2, 4, 8, 7, 5, 1

with period

6,

so

2^d \equiv 8 \equiv -1

exactly when

d \equiv 3 \pmod{6}.

For each difference

d = b - a

there are

40 - d

pairs, so the number of multiples of

9

in

\mathcal{S}

is

\begin{aligned} &\sum_{d = 3, 9, \ldots, 39} (40 - d) \\ &= 37 + 31 + 25 \\ &\quad {}+ 19 + 13 + 7 + 1 \\ &= 133. \end{aligned}

The probability is

\frac{133}{780},

and since

133 = 7 \cdot 19

while

780 = 2^2 \cdot 3 \cdot 5 \cdot 13,

it is in lowest terms. Thus

p + q = 133 + 780 = 913.

2004 AIME II Problema 10

Respuesta: 913

Nivel de dificultad: 2920

Pista pequeña:

Pista grande:

Solución:

El Problema 10 en otros años