2013 AIME I Problema 15

Question

Sea

N

el número de ternas ordenadas

(A, B, C)

de enteros que satisfacen las condiciones:

•

0 \le A \lt B \lt C \le 99,

• existen enteros

a,

b,

y

c,

y un primo

p

donde

0 \le b \lt a \lt c \lt p,

•

p

divide a

A - a,

B - b,

y

C - c,

y

• cada terna ordenada

(A, B, C)

y cada terna ordenada

(b, a, c)

forman sucesiones aritméticas.

Halla

N.

Let

N

be the number of ordered triples

(A, B, C)

of integers satisfying the conditions

•

0 \le A \lt B \lt C \le 99,

• there exist integers

a,

b,

and

c,

and prime

p

where

0 \le b \lt a \lt c \lt p,

•

p

divides

A - a,

B - b,

and

C - c,

and

• each ordered triple

(A, B, C)

and each ordered triple

(b, a, c)

form arithmetic sequences.

Find

N.

Respuesta

Respuesta: 272

Conceptos:sucesión aritmética aritmética modular conteo de pares

Nivel de dificultad: 3270

Pista pequeña:

Si

D

y

d

son las diferencias comunes de

(A,B,C)

y

(b,a,c),

entonces módulo

p

se cumple a la vez

D \equiv -d

y

D \equiv 2d,

así que

3d

es divisible por

p

.

If

D

and

d

are the common differences of

(A,B,C)

and

(b,a,c),

then mod

p

both

D \equiv -d

and

D \equiv 2d,

so

3d

is divisible by

p

Pista grande:

Como

0 \lt 2d \lt p,

eso obliga a

p = 3

y

(b,a,c) = (0,1,2);

cuenta las ternas con

A \equiv 1,

B \equiv 0,

C \equiv 2 \pmod 3

.

Since

0 \lt 2d \lt p,

that forces

p = 3

and

(b,a,c) = (0,1,2);

count triples with

A \equiv 1,

B \equiv 0,

C \equiv 2 \pmod 3

Solución:

Sea

d

la diferencia común de

(b, a, c),

de modo que

a - b = c - a = d \gt 0

y

c = b + 2d \lt p,

de donde

0 \lt 2d \lt p.

Sea

D \gt 0

la diferencia común de

(A, B, C).

Reduciendo módulo

p,

obtenemos

D = B - A \equiv b - a = -d

y

D = C - B \equiv c - b = 2d,

así que

3d

es divisible por

p.

Como

0 \lt d \lt p,

el primo

p

no puede dividir a

d,

así que

p = 3;

entonces

2d \lt 3

da

d = 1

y

(b, a, c) = (0, 1, 2).

Así que las ternas válidas son exactamente las progresiones aritméticas crecientes en

[0, 99]

con

A \equiv 1,

B \equiv 0,

C \equiv 2 \pmod 3.

Escribe

A = 1 + 3j

con

j \ge 0;

la diferencia satisface

D \equiv -1 \equiv 2 \pmod 3,

así que

D = 2 + 3k

con

k \ge 0.

La restricción es

C = A + 2D

= 5 + 3j + 6k \le 99,

es decir

j + 2k \le 31,

y todo par

(j, k)

de este tipo funciona.

Para cada

k = 0, 1, \ldots, 15

hay

32 - 2k

elecciones de

j,

así que

\begin{aligned} &N = \sum_{k=0}^{15} (32 - 2k) \\ &= 16 \cdot 32 - 2 \cdot \frac{15 \cdot 16}{2} \\ &= 512 - 240 = 272. \end{aligned}

Let

d

be the common difference of

(b, a, c),

so

a - b = c - a = d \gt 0

and

c = b + 2d \lt p,

whence

0 \lt 2d \lt p.

Let

D \gt 0

be the common difference of

(A, B, C).

Reducing mod

p,

we get

D = B - A \equiv b - a = -d

and

D = C - B \equiv c - b = 2d,

so

3d

is divisible by

p.

Since

0 \lt d \lt p,

the prime

p

cannot divide

d,

so

p = 3;

then

2d \lt 3

gives

d = 1

and

(b, a, c) = (0, 1, 2).

So the valid triples are exactly the increasing arithmetic progressions in

[0, 99]

with

A \equiv 1,

B \equiv 0,

C \equiv 2 \pmod 3.

Write

A = 1 + 3j

with

j \ge 0;

the difference satisfies

D \equiv -1 \equiv 2 \pmod 3,

so

D = 2 + 3k

with

k \ge 0.

The constraint is

C = A + 2D

= 5 + 3j + 6k \le 99,

i.e.

j + 2k \le 31,

and every such pair

(j, k)

works.

For each

k = 0, 1, \ldots, 15

there are

32 - 2k

choices of

j,

so

\begin{aligned} &N = \sum_{k=0}^{15} (32 - 2k) \\ &= 16 \cdot 32 - 2 \cdot \frac{15 \cdot 16}{2} \\ &= 512 - 240 = 272. \end{aligned}

2013 AIME I Problema 15

Respuesta: 272

Nivel de dificultad: 3270

Pista pequeña:

Pista grande:

Solución:

El Problema 15 en otros años