In the triangle shown, the first diagonal line, $1,2,3,4, \ldots$, begins at 1 and each number after the first is one larger than the previous number. The second diagonal line, $2,4,6,8, \ldots$ begins at 2 and each number after the first is two larger than the previous number. The $n^{\text {th }}$ diagonal line begins at $n$ and each number after the first is $n$ larger than the previous number. In which horizontal row does the number 2016 first appear?
(A) 90
(B) 94
(C) 88
(D) 91
(E) 89

![](https://cdn.mathpix.com/cropped/2024_04_20_46ead6524a8d61e21c51g-034.jpg?height=185&width=522&top_left_y=2358&top_left_x=1211)
Consider the diagonal lines that begin on the left edge of the triangle and move downward to the right.

The first number in the $n^{\text {th }}$ diagonal line is $n$, and it lies in the $n^{\text {th }}$ horizontal row.

For example, the first number in the $3^{\text {rd }}$ diagonal line $(3,6,9,12, \ldots)$ is 3 and it lies in the $3^{r d}$ horizontal row $(3,4,3)$.

The second number in the $n^{\text {th }}$ diagonal line is $n+n$ or $2 n$ and it lies in the horizontal row numbered $n+1$.

The third number in the $n^{\text {th }}$ diagonal line is $n+n+n$ or $3 n$ and it lies in the horizontal row numbered $n+2$ (each number lies one row below the previous number in the diagonal line). Following this pattern, the $m^{\text {th }}$ number in the $n^{\text {th }}$ diagonal line is equal to $m \times n$ and it lies in the horizontal row numbered $n+(m-1)$.

The table below demonstrates this for $n=3$, the $3^{\text {rd }}$ diagonal line.

| $m$ | $m^{\text {th }}$ Diagonal Number | Horizontal Row Number |
| :---: | :---: | :---: |
| 1 | 3 | 3 |
| 2 | $2(3)=6$ | $3+1=4$ |
| 3 | $3(3)=9$ | $3+2=5$ |
| 4 | $4(3)=12$ | $3+3=6$ |
| 5 | $5(3)=15$ | $3+4=7$ |
| $\vdots$ | $\vdots$ | $\vdots$ |
| $m$ | $m \times n$ | $3+(m-1)$ |

The number 2016 lies in some diagonal line(s).

To determine which diagonal lines 2016 lies in, we express 2016 as a product $m \times n$ for positive integers $m$ and $n$.

Further, if $2016=m \times n$, then 2016 appears in the triangle in position $m$ in diagonal line $n$, and lies in the horizontal row numbered $n+m-1$.

We want the horizontal row in which 2016 first appears, and so we must find positive integers $m$ and $n$ so that $m \times n=2016$ and $n+m$ (and therefore $n+m-1$ ) is as small as possible. In the table below, we summarize the factor pairs $(m, n)$ of 2016 and the horizontal row number $n+m-1$ in which each occurence of 2016 appears.

| Factor Pair  $(m, n)$ | Horizontal Row Number  $n+m-1$ |
| :---: | :---: |
| $(1,2016)$ | 2016 |
| $(2,1008)$ | 1009 |
| $(3,672)$ | 674 |
| $(4,504)$ | 507 |
| $(6,336)$ | 341 |
| $(7,288)$ | 294 |
| $(8,252)$ | 259 |
| $(9,224)$ | 232 |
| $(12,168)$ | 179 |


| Factor Pair  $(m, n)$ | Horizontal Row Number  $n+m-1$ |
| :---: | :---: |
| $(14,144)$ | 157 |
| $(16,126)$ | 141 |
| $(18,112)$ | 129 |
| $(21,96)$ | 116 |
| $(24,84)$ | 107 |
| $(28,72)$ | 99 |
| $(32,63)$ | 94 |
| $(36,56)$ | 91 |
| $(42,48)$ | 89 |

(Note: By recognizing that when $m \times n=2016$, the sum $n+m$ is minimized when the positive difference between $m$ and $n$ is minimized, we may shorten the work shown above.)

We have included all possible pairs $(m, n)$ so that $m \times n=2016$ in the table above.

We see that 2016 will appear in 18 different locations in the triangle.

However, the first appearance of 2016 occurs in the horizontal row numbered 89.