Problem 721

A very useful and well-known formula allows us to determine the sum of the first $n$ positive integers, $1+2+3+4+\dots+(n-1)+n$.

The formula says that this sum, $1+2+3+4+\dots+(n-1)+n$, is equal to $\dfrac{n(n+1)}{2}$ (justification of this formula is included at the end of the solution).

For example, if $n=6$ then $1+2+3+4+5+6=\dfrac{6(6+1)}{2}=\frac{6\times7}{2}=\frac{42}{2}=21$.

You can check that this formula gives the correct sum, 21, by mentally adding the positive integers from 1 to 6.

In the table given, there is 1 number in Row 1, there are 2 numbers in Row 2, 3 numbers in Row 3, and so on, with $n$ numbers in Row $n$.

The numbers in the rows list the positive integers in order beginning at 1 in Row 1, with each new row containing one more integer than the previous row.

Thus, the last number in each row is equal to the sum of the number of numbers in the table up to that row.

For example, the last number in Row 4 is 10, which is equal to the sum of the number of numbers in rows $1,2,3,$ and 4.

But the number of numbers in each row is equal to the row number.

So 10 is equal to the sum $1+2+3+4$.

That is, the last number in Row $n$ is equal to the sum $1+2+3+4+\dots+(n-1)+n$, which is equal to $\dfrac{n(n+1)}{2}$.

We may now use this formula to determine in what row the number 2000 appears.

Using trial and error, we find that since $\dfrac{62(63)}{2}=1953$, then the last number in Row 62 is 1953.

Similarly, since $\dfrac{63(64)}{2}=2016$, then the last number in Row 63 is 2016.

Since 2000 is between 1953 and 2016, then 2000 must appear somewhere in Row 63.

To find how many integers less than 2000 are in the column that contains the number 2000, we must determine in which column the number 2000 appears.

Further, we must determine how many numbers there are in that column above the 2000 (since all numbers in that column in rows below the 63$^{rd}$ are larger than 2000).

We know that 2016 is the last number in Row 63 and since it is the last number, it will have no numbers in the column above it.

Moving backward (to the left) from 2016, the number 2015 will have 1 number in the column above it, 2014 will have 2 numbers in the column above it, and so on.

That is, if we move $k$ numbers to the left of 2016, that table entry will have $k$ numbers in the column above it.

In other words, if the number $2016-k$ appears in Row 63, then there are $k$ integers less than it in the column that contains it.

Since we know that 2000 appears in this 63$^{rd}$ row, then $2016-k=2000$ means that $k=16$.

Thus, there are 16 integers less than 2000 in the column that contains the number 2000.

Verification of the Formula: $1+2+3+4+\dots+(n-1)+n=\dfrac{n(n+1)}{2}$

If we let the sum of the first $n$ positive integers be $S$, then $S=1+2+3+4+\dots+(n-1)+n$.

If this same sum is written in the reverse order, then $S=n+(n-1)+(n-2)+(n-3)+\dots+2+1$.

Adding the right sides of these two equations,

[[IMAGE0]]

In this sum there are $n$ occurrences of $(n+1)$, hence the sum is $n(n+1)$.

However, this sum represents $S+S$ or $2S$, so if $2S=n(n+1)$ then $S=\dfrac{n(n+1)}{2}$.