Question

Sea

S

el número de pares ordenados de enteros

(a, b),

con

1 \le a \le 100

y

b \ge 0,

tales que el polinomio

x^2 + ax + b

puede factorizarse como producto de dos factores lineales (no necesariamente distintos) con coeficientes enteros. Halle el residuo cuando

S

se divide entre

1000.

Let

S

be the number of ordered pairs of integers

(a, b),

with

1 \le a \le 100

and

b \ge 0,

such that the polynomial

x^2 + ax + b

can be factored into the product of two (not necessarily distinct) linear factors with integer coefficients. Find the remainder when

S

is divided by

1000.

Respuesta

Respuesta: 600

Conceptos:cuadrática cuadrado perfecto paridad

Nivel de dificultad: 2260

Pista pequeña:

La cuadrática se factoriza sobre los enteros exactamente cuando el discriminante

a^2 - 4b

es un cuadrado perfecto

The quadratic factors over the integers exactly when the discriminant

a^2 - 4b

is a perfect square

Pista grande:

Para cada

a,

los

b

válidos provienen de

4b = a^2 - c^2

con

0 \le c \le a

y

c \equiv a \pmod 2;

cuente esos

c

y sume sobre

a

For each

a,

the valid

b

come from

4b = a^2 - c^2

with

0 \le c \le a

and

c \equiv a \pmod 2;

count those

c

and sum over

a

Solución:

El polinomio se factoriza en factores lineales enteros exactamente cuando sus raíces son enteras, es decir, cuando el discriminante

a^2 - 4b

es igual a

c^2

para algún entero

c \ge 0.

Dado

a,

tal

b \ge 0

existe exactamente cuando

4b = a^2 - c^2 = (a-c)(a+c)

para algún

c

con

0 \le c \le a

y

c \equiv a \pmod 2,

y valores distintos de

c

dan valores distintos

b = \frac{a^2 - c^2}{4}.

Para

a

impar los

c

válidos son

1, 3, \ldots, a,

que son

\frac{a+1}{2}

opciones; para

a

par son

0, 2, \ldots, a,

que son

\frac{a}{2} + 1

opciones.

Sumando sobre

a = 1, \ldots, 100:

los

a

impares aportan

1 + 2 + \cdots + 50 = 1275,

y los

a

pares aportan

2 + 3 + \cdots + 51 = 1325.

Así

S = 2600,

y el residuo es

600.

The polynomial factors into integer linear factors exactly when its roots are integers, that is, when the discriminant

a^2 - 4b

equals

c^2

for some integer

c \ge 0.

Given

a,

such a

b \ge 0

exists exactly when

4b = a^2 - c^2 = (a-c)(a+c)

for some

c

with

0 \le c \le a

and

c \equiv a \pmod 2,

and distinct such

c

give distinct values

b = \frac{a^2 - c^2}{4}.

For odd

a

the valid

c

are

1, 3, \ldots, a,

which is

\frac{a+1}{2}

choices; for even

a

they are

0, 2, \ldots, a,

which is

\frac{a}{2} + 1

choices.

Summing over

a = 1, \ldots, 100:

the odd

a

contribute

1 + 2 + \cdots + 50 = 1275,

and the even

a

contribute

2 + 3 + \cdots + 51 = 1325.

Thus

S = 2600,

and the remainder is

600.

2018 AIME I Problema 1

Respuesta: 600

Nivel de dificultad: 2260

Pista pequeña:

Pista grande:

Solución:

El Problema 1 en otros años