Question

Write numbers out in a square grid with 1 in the top left, then move right 1 space and write 2. Write numbers on a down and left diagonal until coming to the side of the grid, then move down 1 space and write numbers in a right and up diagonal?

In what column and row is the number 2008?

Answer 1

And so 2008 is in row 9, column 55

Explanation:

We have a pattern of numbers in the form (the red digits are row and column numbers and not part of the pattern):

`((...,color(red)(1),color(red)2,color(red)3,color(red)4,color(red)5,color(red)6,"..."),(color(red)1,1,2,6,7,15,16,"..."),(color(red)2,3,5,8,14,17,...,...),(color(red)3,4,9,13,18,...,...,...),(color(red)4,10,12,19,...,...,...,...),(color(red)5,11,20,...,...,...,...,...),(color(red)6,21,...,...,...,...,...,...),(vdots,vdots,ddots,ddots,ddots,ddots,ddots,ddots))`

1. Find and describe the pattern

The pattern is a "snake" pattern where we start with 1 in the upper left, move 1 to the right, then go down the diagonal until aligned vertically with the 1, slides down 1, then goes back up the diagonal until horizontal with the 1 - and repeats.

Where does the number 2008 fit into this?

1a. Amending the pattern description - it's all about diagonals

The solution is all about "diagonals" - paths of consecutive, increasing numbers.

Look at the diagonal path for the numbers 2, 3. The path it describes runs from the top of column 2 to the 2nd number down in column 1.

And then look at the path described by the numbers 4, 5, 6. The path it describes runs from the 3rd number down in column 1 to the top of column 3.

And then the path described by the numbers 7, 8, 9, 10. That path runs from the top of column 4 down to the 4th digit down in column 1.

And so on.

Following this pattern, we can even describe the "first diagonal" as being within the number 1 - it runs up (if you run your finger over the numbers from 10 down to 1, your finger will want to sweep through the 1).

2. Working with the pattern

There are a couple of things we can notice about the diagonals - this first set of points refers to how the diagonals run:

• Defining diagonals: I'm going to call the first diagonal the one that is inside the digit 1, the second diagonal the one that sweeps through the digits 2, 3, the third that sweeps through 4, 5, 6, and so on.

• Seeing the direction the diagonal runs: The first, third, fifth,... all odd numbered diagonals run "up" from some point in column one to the top of a column.

• The second, fourth, sixth,... all even numbered diagonals run "down" from the top of a column to a point in column 1

• (The second diagonal runs from the top of column 2 down to a point in column 1, while the third runs from a point in column 1 to the top of column 3).

This next set of observations is concerned with the relationship between the nth diagonal and the number values in the chart:

• The first diagonal has as it's final value 1
• The second diagonal has as it's final value 3
• The third diagonal has as it's final value 6
• And so on

Notice that there is a relationship between the nth diagonal and the final value in that diagonal (the `sum` character means "the sum of" - I'm using it to sum up the numbers of diagonals we've had up to that particular one):

`(("nth diagonal", sumn"th diagonals", "final value in diagonal"),(1,1,1),(2,1+2=3,3), (3, 1+2+3=6,6), (4, 1+2+3+4=10,10),(vdots, vdots, vdots))`

And so the relationship is that the final value of a particular diagonal and the sum of diagonals up to that point is that they are equal. For example, the 4th diagonal has as it's final value 10. The sum of the numbers of diagonals is also 10. They are equal. And this is the key to solving this problem.

3. Finding 2008 within the pattern

Now that we know that the ending value of a diagonal equals the sum of all the diagonals up to and including it, we can now work to find arithmetic sums that just before 2008 and just after it - this will allow us to identify on which diagonal 2008 sits.

~~~~~

As an example, take the number 9.

We can find an arithmetic sum that sits before 9:
`1+2+3=6` - which is the third diagonal

and the one that sits after:
`1+2+3+4=10` - which is the fourth diagonal

So we can see that 9 sits on the 4th diagonal.

The 4th diagonal runs down - it starts with the number 7 in the top of column 4 and ends with the number 10, four places down in column 1. We can then count back and see that the number 9 sits in column 2, in the 3rd row.

~~~~~

4. Dealing with big sums

2008 is a big number - it will take a lot of adding to find a sum that even approaches the size of it. And so I'm going to use a concept that will help deal with it - summing an arithmetic series. The general formula for it is:

`sum_(k=0)^(n-1)(a+kd)=n/2(2a+(n-1)d)`

where

• n is the number in the series we're looking for (in this case - which numbered diagonal - and this is what we're looking for)
• a is the initial term (1 in this case)
• d is the common difference (also 1)

Ok - so what does it mean?

We can use this formula to add up a series of numbers where there is an arithmetic difference.

Let's look at our example from before where we were working with the number 9 and how we found the sums 6 and 10. We can use the formula to see that we can use it to find those sums, and then we can have trust that it works for bigger sums.

For the 3rd diagonal (which means `n=3`), the first number in our series is 1 (`a=1`), and the difference between each number is also 1 (`d=1`) (the series is 1, 2, 3 - the difference between 2 and 1 is 1, the difference between 3 and 2 is 1), which gives:

`"the sum"=sum=3/2(2(1)+(3-1)(1))`

`"the sum"=sum=3/2(2+(2))`

`"the sum"=sum=3/2(4)=6`

and we can do the same for the 4th diagonal, `n=4`. The first number is still 1, `a=1` and the difference is still 1, `d=1`:

`"the sum"=sum=4/2(2(1)+(4-1)(1))`

`"the sum"=sum=2(2+(3))`

`"the sum"=sum=2(5)=10`

The number 9 sits between 6 and 10.

We're going to use the same thing to find the sums surrounding 2008.

~~~~~

5. Actually finding 2008

From trial and error I've not included here (see below for a way to short cut the trial and error), I think we can start looking at diagonal 62:

`sum=62/2(2(1)+(62-1)(1))`

`sum=31(2+61)`

`sum=31(63)=1953`

And now let's do diagonal 63:

`sum=63/2(2+62)`

`sum=63/2(64)=2016`

And so 2008 is in the 63rd diagonal.

The 63rd diagonal, being odd, sweeps up.

That diagonal starts from the number 1954 (`1953+1=1954`), 63 rows down in column 1 and ends with 2016 at the top of column 63.

We can count down from 2016 (`2016-2008=8` places) or up from 1954 (`2008-1954=54` places) to find 2008:

Column:

From 2016 to 2008: `63-8=55`
Fro 1954 to 2008: `1+54=55`

Row:

From 2016 to 2008: `1+8=9`
From 1954 to 2008: `63-54=9`

~~~~~

Bonus info:

We can short-cut the trial and error by using the summation to find the diagonal number we want to focus on. We take:

`sum=n/2(2a+(n-1)d)`

and substitute in:

• `sum=2008`
• `a=1`
• `d=1`

and we're solving for `n`:

`2008=n/2(2(1)+(n-1)(1))`

`2008=n/2(2+(n-1))`

To make things a little less messy, I'll call `N=n-1`:

`2008=n/2(2+N)`

`2008=n/2(2)+n/2N`

`2008=n+n/2N`

Now I'll put the `n-1` back in:

`2008=n+n/2(n-1)`

`2008=n+(n^2-n)/2`

`4016/2=(2n)/2+(n^2-n)/2`

`4016=2n+n^2-n`

`4016=n^2+n`

`0=n^2+n-4016`

We can use the quadratic formula to solve this:

`x = (-b \pm sqrt(b^2-4ac)) / (2a)`

`x = (-1 \pm sqrt(1^2-4(1)(-4016))) / (2(1))`

`x = (-1 \pm sqrt(1+16064)) / 2`

`x = (-1 \pm sqrt(16065)) / 2`

`x ~= (-1 \pm 126.7) / 2 =125.7/2~=62.84`

(I took the square root to one decimal place - we don't need any more than that. I also ignored the solution `-127.2/2` since we aren't looking for a negative number).

The result of 62.84 means that 62 diagonals are done but the 63rd is still in progress - putting 2008 somewhere on the 63rd diagonal (the decimal .84 tells us it's closer to the end than the beginning).