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

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

Solución:

El Problema 1 en otros años