2020 AMC 10A Problem 17

P16-20~6 minPrint

Absolute Value & Inequalities Number Properties Polynomials Use an invariant, parity, or coloring argument Compute small cases, spot the pattern, generalize

Define $P(x) =(x-1^2)(x-2^2)\cdots(x-100^2).$ How many integers $n$ are there such that $P(n)\leq 0$ ?

Show solution without answering

Key insight

P(n) is zero at the 100 squares. Between squares its sign flips each time, so it is negative in every other gap, starting with the gap from 1 to 4.

Solution

" $P(n) \le 0$ " means $P(n) = 0$ or $P(n) < 0$ . Count the two kinds separately.

1. Where $P(n) = 0$ . A product is zero when a factor is zero, so $n$ is one of $1^2, 2^2, \ldots, 100^2$ . That is $100$ numbers.
2. The sign of a product. A product of nonzero numbers is negative when it has an odd number of negative factors.
3. Try some values of $n$ .
- $n = 0$ : all $100$ factors are negative. $100$ is even, so $P(0) > 0$ .
- $n = 2$ (between $1$ and $4$ ): the factor $n - 1$ is positive and the other $99$ are negative. $99$ is odd, so $P(2) < 0$ .
- $n = 5$ (between $4$ and $9$ ): two factors are positive and $98$ are negative. Even, so $P(5) > 0$ .
- In general, each time $n$ passes a square, one more factor turns positive and the sign flips.
4. So $P(n) < 0$ in the gaps between $1$ and $4$ , between $9$ and $16$ , between $25$ and $36$ , and so on: the gap from $k^2$ to $(k+1)^2$ for $k = 1, 3, 5, \ldots, 99$ . (Past $100^2$ every factor is positive.)
5. How many whole numbers are in a gap? Strictly between $k^2$ and $(k+1)^2$ there are $(k+1)^2 - k^2 - 1 = 2k$ numbers. For example, between $1$ and $4$ there are $2$ (namely $2, 3$ ), and between $9$ and $16$ there are $6$ .
6. Add these for $k = 1, 3, 5, \ldots, 99$ :
$2 + 6 + 10 + \cdots + 198 = 2(1 + 3 + 5 + \cdots + 99) = 2 \times 50^2 = 5000.$
(The first $50$ odd numbers add up to $50^2$ .)
7. Total. $5000 + 100 = 5100$ .

The answer is $\boxed{\textbf{(E)}\ 5100}$ .

Why this works

A product of factors like $(x - r)$ switches sign every time $x$ passes one of the $r$ values. So the signs alternate from gap to gap, and you only need to find the sign in one gap to know them all. Watch for " $\le$ ": the zeros count too.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

$P(n) = 0$ exactly when $n$ is one of the $100$ squares $1^2, 2^2, \dots, 100^2$ .

For other integers, $P(n) < 0$ when an odd number of the factors $n - k^2$ are negative. If $k^2 < n < (k+1)^2$ , the negative factors are those with roots above $n$ , namely $(k+1)^2, \dots, 100^2$ : that is $100 - k$ factors. This is odd exactly when $k$ is odd. For $n < 1$ all $100$ factors are negative (even, positive product), and for $n > 100^2$ none are.

So $P(n) < 0$ precisely for integers strictly between $k^2$ and $(k+1)^2$ with $k \in \{1, 3, 5, \dots, 99\}$ . Each such open gap contains $(k+1)^2 - k^2 - 1 = 2k$ integers, giving
$\sum_{k \text{ odd},\ 1 \le k \le 99} 2k = 2(1 + 3 + \cdots + 99) = 2 \cdot 50^2 = 5000.$

Adding the $100$ zeros: $5000 + 100 = 5100$ .

The answer is $\boxed{\textbf{(E)}\ 5100}$ .

Review in the AoPS books

Introduction to Algebra, Chapter 20: Special Functions (§20.2, §20.5)
Introduction to Number Theory, Chapter 1: Integers: The Basics
Intermediate Algebra, Chapter 6: Polynomial Division (§6.2, §6.4)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)